Expressiveness of streaming string transducers

DOI10.4230/LIPICS.FSTTCS.2010.1MaRDI QIDQ2908833zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Nondeterministic Streaming String Transducers
• Aperiodic string transducers

Cited in

(36)

• Register Transducers Are Marble Transducers
• scientific article; zbMATH DE number 7561353 (Why is no real title available?)
• Minimizing resources of sweeping and streaming string transducers
• Aperiodic string transducers
• On the containment and equivalence problems for two-way transducers
• Normality and two-way automata
• One-way resynchronizability of word 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
• Aperiodic string transducers
• Regular model checking with regular relations
• Weak cost register automata are still powerful
• Robustness analysis of string transducers
• The many facets of string transducers (invited talk)
• From two-way transducers to regular function expressions
• On polynomial recursive sequences
• Optimizing term rewriting with creeper trace transducers
• Copyful streaming string transducers
• Streamable regular transductions
• Kleenex: compiling nondeterministic transducers to deterministic streaming transducers
• FO-definable transformations of infinite strings
• Transducers of polynomial growth
• Copyful streaming string transducers
• Nondeterministic Streaming String Transducers
• On Synthesis of Resynchronizers for Transducers
• Origin-equivalence of two-way word transducers is in PSPACE
• scientific article; zbMATH DE number 7559429 (Why is no real title available?)
• Sequentiality of string-to-context transducers
• On the decomposition of finite-valued streaming string transducers
• On deterministic 1-limited \(5' \rightarrow 3'\) sensing Watson-Crick finite-state transducers
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)
• Regular Transformations of Data Words Through Origin Information
• scientific article; zbMATH DE number 7003194 (Why is no real title available?)
• Complexity of regular functions

This page was built for publication: Expressiveness of streaming string transducers

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