Finite automata with advice tapes
From MaRDI portal
Publication:5300849
DOI10.1007/978-3-642-38771-5_27zbMATH Open1381.68124arXiv1312.2268OpenAlexW2157199437MaRDI QIDQ5300849FDOQ5300849
Authors: Uğur Küçük, A. C. Cem Say, Abuzer Yakaryılmaz 
Publication date: 28 June 2013
Published in: Developments in Language Theory (Search for Journal in Brave)
Abstract: We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Full work available at URL: https://arxiv.org/abs/1312.2268
Recommendations
Cited In (11)
- Polynomial time quantum computation with advice
- Determinism and Nondeterminism in Finite Automata with Advice
- Automata that take advice
- Finite automata with advice tapes
- Title not available (Why is that?)
- Limited two-way deterministic finite automata with advice
- On the complexity of infinite advice strings
- The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
- A Myhill-Nerode theorem for automata with advice
- Advice hierarchies among finite automata
- Two-way and one-way quantum and classical automata with advice for online minimization problems
This page was built for publication: Finite automata with advice tapes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300849)
