THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
From MaRDI portal
Publication:3069734
DOI10.1142/S0129054110007659zbMath1206.68120arXiv1007.3021MaRDI QIDQ3069734
Publication date: 19 January 2011
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.3021
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Multiple Usage of Random Bits in Finite Automata ⋮ Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Advice hierarchies among finite automata ⋮ FINITE AUTOMATA WITH ADVICE TAPES
Cites Work
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- An NP-complete language accepted in linear time by a one-tape Turing machine
- A context-free language which is not acceptable by a probabilistic automaton
- One-tape, off-line Turing machine computations
- On a Class of Stochastic Languages
This page was built for publication: THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA