Automata that take advice

DOI10.1007/3-540-60246-1_121MaRDI QIDQ3569007zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Markus Holzer

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60246-1_121

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Finite automata with advice tapes
• Finite automata with advice tapes
• A Myhill-Nerode theorem for automata with advice
• The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA

Cited in

(17)

• A Myhill-Nerode theorem for automata with advice
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• On the amount of nonconstructivity in learning recursive functions
• Advice hierarchies among finite automata
• On the amount of nonconstructivity in learning formal languages from text
• On the complexity of infinite advice strings
• Determinism and Nondeterminism in Finite Automata with Advice
• Two-way non-uniform finite automata
• Question answering by humans and machines: a complexity-theoretic view
• Quantum state complexity of formal languages
• Two-Way Non-Uniform Finite Automata
• scientific article; zbMATH DE number 7559401 (Why is no real title available?)
• Turing machines with one-sided advice and acceptance of the co-RE languages
• Multi-head finite automata: Data-independent versus data-dependent computations
• Amount of Nonconstructivity in Finite Automata
• Amount of nonconstructivity in deterministic finite automata
• Theory of one-tape linear-time Turing machines

This page was built for publication: Automata that take advice

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