Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Converting Nondeterministic Two-Way Automata into Small Deterministic
  Linear-Time Machines   In 1978 Sakoda and Sipser raised the question of the cost, in terms of size
of representations, of the transformation of two-way and one-way
nondeterministic automata into equivalent two-way deterministic automata.
Despite all the attempts, the question has been answered only for particular
cases (e.g., restrictions of the class of simulated automata or of the class of
simulating automata). However the problem remains open in the general case, the
best-known upper bound being exponential. We present a new approach in which
unrestricted nondeterministic finite automata are simulated by deterministic
models extending two-way deterministic finite automata, paying a polynomial
increase of size only. Indeed, we study the costs of the conversions of
nondeterministic finite automata into some variants of one-tape deterministic
Turing machines working in linear time, namely Hennie machines, weight-reducing
Turing machines, and weight-reducing Hennie machines. All these variants are
known to share the same computational power: they characterize the class of
regular languages.

5
The categories of this paper are: gr-qc
3
The categories of this paper are: physics
30
The categories of this paper are: q-alg
26
The categories of this paper are: bayes-an
17
The categories of this paper are: q-fin
2
The categories of this paper are: math
35
The categories of this paper are: mtrl-th
4
The categories of this paper are: cond-mat
37
The categories of this paper are: supr-con
7
The categories of this paper are: hep-th
10
The categories of this paper are: q-bio
16
The categories of this paper are: stat
13
The categories of this paper are: quant-ph
32
The categories of this paper are: atom-ph
12
The categories of this paper are: nucl-th
27
The categories of this paper are: comp-gas