Add to ORKGWe investigate the relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded Turing machines and the relationship between the classes of languages accepted by deterministic polynomial time bounded and by nondeterministic polynomial tape bounded Turing machines. In both cases we study generators of the nondeterministic class that generate it by operations that the deterministic class is closed under
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a determin...
AbstractWe consider one-tape nondeterministic Turing machines, i.e. with a unique worktape on which ...
AbstractIn this paper we study diagonal processes over time bounded computations of one-tape Turing ...
We investigate the following: (1) the relationship between the classes of languages accepted by det...
It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Con...
The following statements are shown to be equivalent:(i)Every language accepted by a nondeterministic...
Abstract. Deterministic k-tape and multitape Turing machines with one-way, twoway and without a sepa...
AbstractDeterministic k-tape and multitape Turing machines with one-way, two-way and without a separ...
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity...
The tape complexity of context-free languages is investigated. It is shown that all the members of t...
A condition on a class of languages is developed. This condition is such that every tally language i...
ARSTRAcr. It is shown that every deterministic multltape Turlng machine of time complexity t(n) can ...
In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equival...
AbstractThe time separation results concerning classes of languages over a single-letter alphabet ac...
In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turin...
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a determin...
AbstractWe consider one-tape nondeterministic Turing machines, i.e. with a unique worktape on which ...
AbstractIn this paper we study diagonal processes over time bounded computations of one-tape Turing ...
We investigate the following: (1) the relationship between the classes of languages accepted by det...
It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Con...
The following statements are shown to be equivalent:(i)Every language accepted by a nondeterministic...
Abstract. Deterministic k-tape and multitape Turing machines with one-way, twoway and without a sepa...
AbstractDeterministic k-tape and multitape Turing machines with one-way, two-way and without a separ...
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity...
The tape complexity of context-free languages is investigated. It is shown that all the members of t...
A condition on a class of languages is developed. This condition is such that every tally language i...
ARSTRAcr. It is shown that every deterministic multltape Turlng machine of time complexity t(n) can ...
In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equival...
AbstractThe time separation results concerning classes of languages over a single-letter alphabet ac...
In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turin...
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a determin...
AbstractWe consider one-tape nondeterministic Turing machines, i.e. with a unique worktape on which ...
AbstractIn this paper we study diagonal processes over time bounded computations of one-tape Turing ...