Which classes of origin graphs are generated by transducers

DOI10.4230/LIPICS.ICALP.2017.114MaRDI QIDQ5111446zbMATH OpenFDO

Authors Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2017.114

zbMATH Keywords

MSO-definabilityorigin semanticsstreaming string transducersstring-to-string transductions

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• Transducers with Origin Information
• Decision problems of tree transducers with origin
• Decision problems of tree transducers with origin
• scientific article; zbMATH DE number 3952037
• Regular Transformations of Data Words Through Origin Information

Cited in

(11)

• One-way resynchronizability of word transducers
• Computability by monadic second-order logic
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• scientific article; zbMATH DE number 7559429 (Why is no real title available?)
• The many facets of string transducers (invited talk)
• Origin-equivalence of two-way word transducers is in PSPACE
• On Synthesis of Resynchronizers for Transducers
• Linear-time limited automata
• Resynchronized uniformization and definability problems for rational relations
• Nondeterminism makes unary 1-limited automata concise
• A logical characterization of weak determinism as simultaneous application

This page was built for publication: Which classes of origin graphs are generated by transducers

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