English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper we consider a nondeterministic computation by deterministic multi- head 2-way automata having a read-only access to an auxiliary memory. The memory contains additional data (a guess) and computation is successful iff it is successful for some memory content. Also we consider the case of restricted guesses in which a guess should satisfy some constraint. We show that the standard complexity classes such as L, NL, P, NP, PSPACE can be characterized in terms of these models of nondeterministic computation. These characterizations differ from the well-known ones by absence of alternation. Keywords: automaton, nondeterminism, language, complexity class. The standard way to define a nondeterministic computation by an automaton or a Turing machine is to change a transition function by a transition re lation. In a nondeterministic state of a computational device a computation branches into several computation paths. There is another way to introduce a nondeterminism. Suppose that a computational device has an additional data (a guess or a certificate or a proof of correctness) and performs a deterministic computation operating with an input data and a guess data. Sometimes these variants of introducing nondeterminism lead to equivalent compu- tational models. The class NP, for example, can be defined in both ways using Turing machines. If we restrict computational power of a computational device these variants may differ drastically. The aim of this paper is to investigate models o f nondeterminism based on the second variant for multi-head 2-way automata. It is well-known1 that computation abilities of multi-head 2-way automata are equiv- alent to Turing machines with a logarithmically bounded memory. So, they recognize languages from the class L. Nondeterministic (in the sense of transition relation) mul ti-head 2-way automata rec- ognize languages from the class NL. One can rewrite a definition of a nondeterministic au- tomaton using the second way of introducing nondeterminism. Let's imagine that a guess data are written on an auxiliary tape, which is 1-way read-only. It is easy to see that using an 1-way guess tape leads to an equivalent definition of a nond eterministic automaton. In this paper we consider a more general model of an auxiliary read-only memory (see definitions in Section 1). Guess data are stored in cells of a memory and at each moment of time an automaton has an access to the exactly one memory cell. Possible transitions between memory cells form a directed graph (the memory graph). An automaton can choose between finite number of variants only. So, the nat ural condition on the memory graph is a finite fan-out in each vertex (i.e. a memory cell). Dorodnitsyn Computing Center of RAS, Vavilova, 40, Moscow, 119991, Russia. The work is supported by

On Models of a Nondeterministic Computation