Uniform simulations of nondeterministic real time multitape Turing machines
A new uniform technique is developed for the simulation of nondeterministic multitape Turing machines by simpler machines. For many types of restricted nondeterministic Turing machines it can now be proved that both linear time is no more powerful than real time, and multitape machines are no more powerful than machines with two tapes, one of which is a simple and normalized comparison type. This is an improvement over all previously known simulations in terms of weaker machines. As an application we obtain that, for all such machines, the class of languages accepted in real time by multitape machines is principal and has a simple trio generator. Moreover, multitape machines with different types of tapes are hierarchically related, contrasting with the case of one-tape machines, and some important families of languages are characterized in a new way.
- A relation between space, return and dual return complexities
- Checking automata and one-way stack languages
- Counter machines and counter languages
- Equality Sets and Complexity Classes
- scientific article; zbMATH DE number 3936519 (Why is no real title available?)
- scientific article; zbMATH DE number 3980489 (Why is no real title available?)
- scientific article; zbMATH DE number 3509706 (Why is no real title available?)
- scientific article; zbMATH DE number 3540370 (Why is no real title available?)
- scientific article; zbMATH DE number 3640873 (Why is no real title available?)
- Linear Languages and the Intersection Closures of Classes of Languages
- Multiple equality sets and Post machines
- One way finite visit automata
- One-way nondeterministic real-time list-storage languages
- One-way stack automata
- Quasi-real-time languages
- Real-Time Simulation of Multihead Tape Units
- Remarks on blind and partially blind one-way multicounter machines
- Reset machines
- Reversal-Bounded Acceptors and Intersections of Linear Languages
- Reversal-bounded multipushdown machines
- Simple Representations of Certain Classes of Languages
- Visits, crosses, and reversals for nondeterministic off-line machines
- A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers)
- Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
- scientific article; zbMATH DE number 2068877 (Why is no real title available?)
This page was built for publication: Uniform simulations of nondeterministic real time multitape Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771615)