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

DOI10.1142/S0129054110007659MaRDI QIDQ3069734zbMATH OpenFDO

Authors Tomoyuki Yamakami

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

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)

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.

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

Cites work

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

Cited in

(14)

• Linear Advice for Randomized Logarithmic Space
• A generic time hierarchy with one bit of advice
• Automata that take advice
• Finite automata with advice tapes
• From logarithmic advice to single-bit advice
• A note on the advice complexity of multipass randomized logspace
• Turing machines with one-sided advice and acceptance of the co-RE languages
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• Multi-head two-way finite automata with advice
• The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
• Multiple usage of random bits in finite automata
• Advice hierarchies among finite automata
• Finite automata with advice tapes
• Power of counting by nonuniform families of polynomial-size finite automata

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)