On the complexity of infinite advice strings

DOI10.4230/LIPICS.ICALP.2018.122MaRDI QIDQ5002808zbMATH OpenOpenAlexFDO

Authors 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

advice automataautomatic structuresinfinite wordstransducers

Mathematics Subject Classification ID

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

Recommendations

• A Myhill-Nerode theorem for automata with advice
• Finite automata with advice tapes
• Advice Automatic Structures and Uniformly Automatic Classes
• Finite automata with advice tapes
• Automata that take advice

Cites work

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

Cited in

(3)

• A Myhill-Nerode theorem for automata with advice
• Large scale geometries of infinite strings
• The string guessing problem as a method to prove lower bounds on the advice complexity

This page was built for publication: On the complexity of infinite advice strings

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