A Myhill-Nerode theorem for automata with advice

MaRDI QIDQ4986519zbMATH OpenFDO

Authors Alex Kruckman, Sasha Rubin, J. Sheridan, Ben Zax

Publication date 27 April 2021

Full work available at URL https://arxiv.org/abs/1210.2462, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2012.18

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Finite automata with advice tapes
• Finite automata with advice tapes
• Determinism and Nondeterminism in Finite Automata with Advice
• Automata that take advice
• On the complexity of infinite advice strings

Cited in

(6)

• Determinism and Nondeterminism in Finite Automata with Advice
• Automata that take advice
• On the width of regular classes of finite structures
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• On the complexity of infinite advice strings
• Advice hierarchies among finite automata

This page was built for publication: A Myhill-Nerode theorem for automata with advice

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