Copyful Streaming String Transducers

DOI10.3233/FI-2021-1998zbMath1478.68125MaRDI QIDQ4989167

Pierre-Alain Reynier, Emmanuel Filiot

Publication date: 21 May 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

wordstransducersequivalence problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• The equivalence problem for deterministic MSO tree transducers is decidable
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On finite semigroups of matrices
• A short solution for the HDT0L sequence equivalence problem
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Aperiodic String Transducers
• Expressiveness of Streaming String Transducers
• First-order definable string transformations
• Regular Transformations of Infinite Strings
• Nondeterministic Streaming String Transducers
• Streaming Tree Transducers
• MSO definable string transductions and two-way finite-state transducers
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable
• Two-Way Visibly Pushdown Automata and Transducers
• Regular Functions and Cost Register Automata
• 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: Copyful Streaming String Transducers