Nondeterministic Streaming String Transducers

DOI10.1007/978-3-642-22012-8_1MaRDI QIDQ3012906zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Expressiveness of streaming string transducers
• On the decomposition of finite-valued streaming string transducers
• Copyful streaming string transducers
• Copyful streaming string transducers
• Streaming ranked-tree-to-string transducers
• Streaming ranked-tree-to-string transducers
• Minimizing resources of sweeping and streaming string transducers
• Streamability of nested word transductions
• Streamability of nested word transductions

Cites work

• A note on finite-valued and finitely ambiguous transducers
• Algorithms on Strings, Trees and Sequences
• Expressiveness of streaming string transducers
• Graph operations, graph transformations and monadic second-order logic: a survey
• MSO definable string transductions and two-way finite-state transducers
• On the Decidability of Bounded Valuedness for Transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the valuedness of finite transducers
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Sur les rélations rationnelles entre monoides libres
• The complexity of decision problems for finite-turn multicounter machines
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

Cited in

(21)

• Minimizing resources of sweeping and streaming string transducers
• Finite-valued streaming string transducers
• On the containment and equivalence problems for two-way transducers
• Non-deterministic transducer models of retransmission protocols over noisy channels
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Streaming ranked-tree-to-string transducers
• Streaming ranked-tree-to-string transducers
• scientific article; zbMATH DE number 6665209 (Why is no real title available?)
• Finite-valued streaming string transducers
• Regular model checking with regular relations
• The many facets of string transducers (invited talk)
• Copyful streaming string transducers
• Checking regular invariance under tightly-controlled string modifications
• Minimal synthesis of string to string functions from examples
• Kleenex: compiling nondeterministic transducers to deterministic streaming transducers
• Expressiveness of streaming string transducers
• Copyful streaming string transducers
• Origin-equivalence of two-way word transducers is in PSPACE
• Sequentiality of string-to-context transducers
• On the decomposition of finite-valued streaming string transducers
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)

This page was built for publication: Nondeterministic Streaming String Transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012906)