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

zbMATH Keywords

streaming string transducersorigin semanticsMSO-definabilitystring-to-string transductions

Mathematics Subject Classification ID

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

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

(9)

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

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)