Expressiveness of Streaming String Transducers

DOI10.4230/LIPIcs.FSTTCS.2010.1zbMath1245.68115OpenAlexW1529428897MaRDI QIDQ2908833

Pavol Černý, Rajeev Alur

Publication date: 29 August 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_6b0a.html

zbMATH Keywords

heap manipulationlist processingmonadic second-order transductionstreaming string transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Regular model checking with regular relations ⋮ Complexity of regular functions ⋮ On the containment and equivalence problems for two-way transducers ⋮ Aperiodic String Transducers ⋮ One-way resynchronizability of word transducers ⋮ Nondeterministic Streaming String Transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Streamable regular transductions ⋮ Streaming ranked-tree-to-string transducers ⋮ Regular Transformations of Data Words Through Origin Information ⋮ Aperiodic String Transducers ⋮ Register Transducers Are Marble Transducers ⋮ Origin-equivalence of two-way word transducers is in PSPACE ⋮ On Synthesis of Resynchronizers for Transducers ⋮ Regular transducer expressions for regular transformations ⋮ Copyful Streaming String Transducers ⋮ Unnamed Item ⋮ Weak Cost Register Automata are Still Powerful ⋮ From Two-Way Transducers to Regular Function Expressions ⋮ Normality and two-way automata ⋮ Non-deterministic transducer models of retransmission protocols over noisy channels ⋮ On deterministic 1-limited 5′ → 3′ sensing Watson–Crick finite-state transducers