On the Complexity of Infinite Advice Strings

DOI10.4230/LIPIcs.ICALP.2018.122zbMath1499.68173OpenAlexW2886490229MaRDI QIDQ5002808

Gaëtan Douéneau-Tabot

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9126/pdf/LIPIcs-ICALP-2018-122.pdf/

zbMATH Keywords

infinite wordstransducersautomatic structuresadvice automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57)

Cites Work

• Unnamed Item
• Some definitional suggestions for automata theory
• Referenced automata and metaregular families
• Regular Transformations of Infinite Strings
• The additive group of the rationals does not have an automatic presentation
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Degrees of Transducibility
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• Some Algebraic Properties of Machine Poset of Infinite Words
• MSO definable string transductions and two-way finite-state transducers
• Automatic Sequences
• Advice Automatic Structures and Uniformly Automatic Classes
• Transforming structures by set interpretations
• A Proof of Kamp's theorem
• On finite automata with a time-variant structure

This page was built for publication: On the Complexity of Infinite Advice Strings