THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA

DOI10.1142/S0129054110007659zbMATH Open1206.68120arXiv1007.3021MaRDI QIDQ3069734FDOQ3069734

Tomoyuki Yamakami

Publication date: 19 January 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.

Full work available at URL: https://arxiv.org/abs/1007.3021

Recommendations

• scientific article; zbMATH DE number 2214054
• Conditional formulae for Gibbs-type exchangeable random partitions
• Marginals of multivariate Gibbs distributions with applications in Bayesian species sampling
• Looking-backward probabilities for Gibbs-type exchangeable random partitions
• Review of the stirling numbers, their generalizations and Statistical Applications

zbMATH Keywords

advicezero-sum gamepseudorandomfinite automatonrandomized adviceone-tape linear-time Turing machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• An NP-complete language accepted in linear time by a one-tape Turing machine
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• One-tape, off-line Turing machine computations
• A context-free language which is not acceptable by a probabilistic automaton
• On a Class of Stochastic Languages

Cited In (9)

• Linear Advice for Randomized Logarithmic Space
• A generic time hierarchy with one bit of advice
• Multiple Usage of Random Bits in Finite Automata
• Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
• Advice hierarchies among finite automata
• Power of counting by nonuniform families of polynomial-size finite automata
• FINITE AUTOMATA WITH ADVICE TAPES

This page was built for publication: THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA

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