Copyful streaming string transducers

DOI10.3233/FI-2021-1998MaRDI QIDQ4989167zbMATH OpenFDO

Authors Emmanuel Filiot, Pierre-Alain Reynier

Publication date 21 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2021-1998

zbMATH Keywords

equivalence problemtransducerswords

Mathematics Subject Classification ID

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

Recommendations

• Copyful streaming string transducers
• Nondeterministic Streaming String Transducers
• Expressiveness of streaming string transducers
• Aperiodic string transducers
• Aperiodic string transducers

Cites work

• A short solution for the HDT0L sequence equivalence problem
• Aperiodic string transducers
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• Expressiveness of streaming string transducers
• First-order definable string transformations
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Macro Tree Translations of Linear Size Increase are MSO Definable
• MSO definable string transductions and two-way finite-state transducers
• Nondeterministic Streaming String Transducers
• On finite semigroups of matrices
• Polynomial automata: zeroness and applications
• Regular functions and cost register automata (invited paper)
• Regular transformations of infinite strings
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The equivalence problem for deterministic MSO tree transducers is decidable
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Two-way visibly pushdown automata and transducers

Cited in

(7)

• Copyful streaming string transducers
• Nondeterministic Streaming String Transducers
• Finite-valued streaming string transducers
• Finite-valued streaming string transducers
• Comparison-free polyregular functions
• Lexicographic transductions of finite words
• Minimizing streaming string transducers: an algebraic approach

This page was built for publication: Copyful streaming string transducers

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