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

advicefinite automatonone-tape linear-time Turing machinepseudorandomrandomized advicezero-sum game

Mathematics Subject Classification ID

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

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)

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

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)