Nondeterministic Streaming String Transducers
From MaRDI portal
Publication:3012906
DOI10.1007/978-3-642-22012-8_1zbMath1333.68157OpenAlexW93433526MaRDI QIDQ3012906
Jyotirmoy V. Deshmukh, Rajeev Alur
Publication date: 7 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22012-8_1
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (11)
Regular model checking with regular relations ⋮ Checking regular invariance under tightly-controlled string modifications ⋮ Deletion operations on deterministic families of automata ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ On the containment and equivalence problems for two-way transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Origin-equivalence of two-way word transducers is in PSPACE ⋮ Copyful Streaming String Transducers ⋮ Non-deterministic transducer models of retransmission protocols over noisy channels
Cites Work
- The equivalence of finite valued transducers (on HDT0L languages) is decidable
- On the valuedness of finite transducers
- The complexity of decision problems for finite-turn multicounter machines
- Sur les rélations rationnelles entre monoides libres
- Expressiveness of Streaming String Transducers
- On the Decidability of the Equivalence for k-Valued Transducers
- On the Decidability of Bounded Valuedness for Transducers
- A note on finite-valued and finitely ambiguous transducers
- Algorithms on Strings, Trees and Sequences
- MSO definable string transductions and two-way finite-state transducers
- Graph Operations, Graph Transformations and Monadic Second-Order Logic:
- Streaming transducers for algorithmic verification of single-pass list-processing programs
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
This page was built for publication: Nondeterministic Streaming String Transducers
