# A Computation Model with Automatic Functions and Relations as Primitive
Operations111Ziyuan Gao, Sanjay Jain, and Frank Stephan were supported in part
by the Singapore Ministry of Education Academic Research Fund Tier 2 grant
MOE2019-T2-2-121 / R146-000-304-112; furthermore, Sanjay Jain was also
supported in part by the NUS Provost Chair grant C252-000-087-001.

Ziyuan Gao<EMAIL_ADDRESS>Sanjay Jain<EMAIL_ADDRESS>Zeyong Li
<EMAIL_ADDRESS>Ammar Fathin Sabili<EMAIL_ADDRESS>Frank Stephan
<EMAIL_ADDRESS>Department of Mathematics, National University of
Singapore, 10 Lower Kent Ridge Road, S17, Singapore 119076, Republic of
Singapore  Department of Computer Science, National University of Singapore,
13 Computing Drive, COM1, Singapore 117417, Republic of Singapore  Center for
Quantum Technologies, National University of Singapore, 3 Science Drive 2,
S15, Singapore 117543, Republic of Singapore

###### Abstract

Prior work of Hartmanis and Simon [16] and Floyd and Knuth [11] investigated
what happens if a device uses primitive steps more natural than single updates
of a Turing tape. One finding was that in the numerical setting, addition,
subtraction, comparisons and bit-wise Boolean operations of numbers preserve
polynomial time while incorporating concatenation or multiplication allows to
solve all PSPACE problems in polynomially many steps. Therefore we propose to
use updates and comparisons with automatic functions as primitive operations
and use constantly many registers; the resulting model covers all primitive
operations of Hartmanis and Simon as well as Floyd and Knuth, but the model
remains in polynomial time. The present work investigates in particular the
deterministic complexity of various natural problems and also gives an
overview on the nondeterministic complexity of this model.

###### keywords:

Theory of Computation , Model of Computation , Automatic Function , Register
Machine , Computational Complexity

##  1 Introduction

Sequential models of computation such as finite state machines, register
machines and Turing machines typically carry out primitive operations at each
computation step. For example, Turing machines have a finite number of rules
for manipulating symbols on a tape and can only process symbols one at a time.
Register machines, in particular random-access machines (RAM’s), can store
numbers of arbitrary size in an unlimited number of registers and have basic
arithmetic operators such as increment and decrement; a RAM may also be
augmented with instructions for performing advanced operations such as
multiplication, division, concatenation as well as number comparison [16, 38].
A fairly common theme in the study of these machines is the analysis of
whether, and if so to what extent, computational power is boosted by allowing
extra types of instructions. In the case of RAM’s, Hartmanis and Simon [16]
showed that adding logical operations on bit vectors in parallel and either
multiplication or concatenation allows polynomial time decidability of all
languages in PSPACE, where the instructions use all counts as constant time
operations. Schönhage [38] proved that incorporating the arithmetic operations
of addition, multiplication and division as primitive steps allows polynomial
time decidability of all languages in NP; if RAM’s only incorporate addition
and multiplication as primitive steps, then the languages they decide in
polynomial time are also decidable in polynomial time by probabilistic Turing
machines.

A natural question is whether the computational power of register machines can
be enhanced with primitive operators that generalise bit-wise operations,
addition, subtraction and comparison, but do not lead to an “unreasonable”
speedup in computational time. For the purpose of the current work, we define
a “reasonable” primitive operator as one that can be simulated by an
appropriate type of Turing machine or register machine with at most a
polynomial increase in time complexity. As mentioned earlier, RAM’s that are
equipped with bit operations as well as the multiplication or concatenation
operator can decide languages in PSPACE in polynomial time; if one allows the
addition, multiplication and division operators, then RAM’s can decide
languages in NP in polynomial time. Motivated by the common assumption that
neither PSPACE nor NPis equal to P, the present work does not regard
multiplication or concatenation as a reasonable primitive operator. In this
work, we propose the use of automatic functions or, more generally, bounded
automatic relations as primitive steps in a register machine. We call such
machines Deterministic Automatic Register Machines (DARM’s) in the case that
automatic functions are used, and Non-deterministic Automatic Register
Machines (NARM’s) in the case that bounded automatic relations are used.
Automatic functions and relations belong to the wider class of automatic
structures, which are relational structures whose domain and atomic relations
can be realised by finite automata operating synchronously on their input. The
idea of using automata to study structures was originally conceived by Büchi,
who applied this notion to prove the decidability of a fragment of second-
order arithmetic known as S1S [5, 6]. The definition of an automatic structure
first appeared in Hodgson’s doctoral thesis [21], parts of which were
published later [19]. Khoussainov and Nerode [26] rediscovered the concept of
an automatic structure and defined various notions of automatic presentations.
They then studied the problem of characterising structures that have automatic
presentations and analysed the complexity of problems formulated over
automatic structures. A large body of work on automatic structures has since
emerged, covering themes ranging from the model checking problem to the
problem of characterising definable relations [13, 25, 32, 37].

The key link between automatic functions and one-tape deterministic Turing
machines, which forms the basis for the DARM model, is that each computation
of an automatic function can be simulated by a one-tape deterministic Turing
machine in linear time [8]. Using a proof technique very similar to that for
establishing the latter result, one can show that each computation of a
bounded automatic relation can be simulated by a one-tape nondeterministic
Turing machine in linear time; this means there is a one-tape nondeterministic
Turing machine such that for any pair $(x,y)$ in the automatic relation, there
is a computational path that starts with the input $x$ (with the tape head
starting at the first position of the input) and eventually reaches an accept
state with the final tape content $y$, where the first position of $y$ matches
that of the input. Thus a computation by an automatic function or bounded
automatic relation fulfills our criterion for a reasonable primitive step. In
particular, while automatic functions can perform bit-wise operations,
addition, subtraction and comparison, they are not powerful enough to carry
out multiplication or concatenation.

Automatic register machines (ARM’s) may be viewed as a generalisation of
addition machines, a class of register machines introduced by Floyd and Knuth
[11]. Addition machines are limited to six types of operations, each carried
out in constant time: reading input, writing output, adding, subtracting,
copying the contents of one register to another register and comparing the
contents of any two registers. It turns out that many natural operations like
multiplication can be done by addition machines in linear time [11]. These
nice results carry over to automatic function complexity, as the natural
numbers with addition and comparison is an automatic structure. Moreover, as
mentioned earlier, an ARM can also perform each bit-wise Boolean operation in
a single step [16, 17]. Another class of devices closely related to ARM’s is
that of the finite-state transducers. It may seem reasonable to use the class
of rational relations – relations recognised by finite-state transducers – as
a primitive operator in register machines. However, as mentioned earlier,
Hartmanis and Simon [16, Theorem 2] showed that bitwise operations together
with addition, subtraction, comparisons and concatenation allow to decide in
polynomially many steps sets from PSPACE; as all these primitive functions and
relations can be implemented using transducers, it follows that transducers as
primitive steps are too powerful, see Section 4.1 for more explanations and
related results. For this reason, we have chosen not to implement rational
relations as primitive operators.

One might also propose combining register machines with transducers that are
limited by the constraint that for every update function which is computed by
the transducer, there is a constant $c$ such that for all inputs $x$ the
output $y$ is at most $c$ symbols longer than $x$; such a transducer would
therefore satisfy a size constraint property similar to that of the automatic
functions. But such transducers might still be regarded as being too powerful,
for they allow nonregular sets to be recognised in constantly many steps. One
such example is the set of all words that have as many $0$’s as $1$’s: for
each $a,b\in\\{0,1\\}$, let $f_{a,b}(x)$ be the output of a transducer $T$
which reads a word $x$ and outputs a symbol $b$ whenever it reads the symbol
$a$ and which discards all other symbols without replacement; $T$, which
evidently satisfies the required size constraint property, accepts an input
$x$ if and only if $f_{0,1}(x)=f_{1,1}(x)$. On the other hand, as we will show
in this work, the class of languages recognised in constantly many steps by
DARM’s belongs to the class of regular languages, see Theorem 5.1 below. Thus,
the computational power of register machines with primitive steps computed by
transducers whose output has length bounded by the input length plus an
additive constant already exceeds that of register machines combined with
automatic functions.

An alternative model of transducers that can indeed be simulated by
deterministic Turing machines in polynomial time is that recently proposed by
Kutrib, Malcher, Mereghetti, and Palano [30], where transducers are restricted
to be length-preserving. Although this transducer model yields interesting
results, it might not be adequate for modelling primitive steps in a register
machine since length-preserving transductions are a real restriction and allow
recognition of only a subclass of P. Automatic functions are more robust in
that they can output a string longer than the input by an additive constant,
and cover the full class P in polynomially many steps. For all these reasons,
we believe that automatic functions and bounded automatic relations are an
appropriate choice of primitive operators in register machines.

We also mention a few other models of computation whose computational powers
appear to be similar to that of ARM’s. First, a $d$-dimensional array
automaton consists of an 1-way input tape and a $d$-dimensional regular array
of cells, each of which contains a finite-state machine, and each step of
computation consists of an input head move and an array head move together
with a state transformation for each finite-state machine in a cell. Kosaraju
[27] showed that context-free languages can be recognised by 1-dimensional
arrays in $n^{2}$ time; using a similar algorithm, we show the same time
complexity can be achieved by a deterministic ARM (Theorem 5.4). Kutrib and
Malcher [28, 29] also investigated one-dimensional arrays of interconnecting
finite automata (known as cellular automata or cells), showing in particular
that cellular automaton transducers enjoy better time complexities compared to
iterative array transducers, where the input is processed in real time and the
output is computed in linear time. We note that any computation of an
automatic function can be simulated by one computation step of a cellular
automaton; it would therefore appear that cellular automata are just as
powerful as deterministic ARM’s.

The contributions of this work are as follows. First, we lay out the general
definition of an ARM, and then define two specific types of such machines,
namely DARM’s and NARM’s, as well as their respective complexity classes for
arbitrary functions. Next, we compare the computational power of ARM’s to that
of other models of computation including transducers, Generative systems
(g-systems) [36] and Iterated Uniform Finite-State Transducers [30]. The main
goal of these comparisons is to justify the use of automatic functions and
bounded automatic relations in combination with register machines; we wish to
show, in particular, that it yields a sufficiently expressive model that does
not give an unrealistic speed-up. Furthermore, we show that an open question
of Kutrib, Malcher, Mereghetti, and Palano [30] on whether their model of
Iterated Uniform Finite-State Transducers covers the whole class of context-
sensitive languages has a positive answer; this can be shown using a proof
quite similar to that for establishing that context-sensitive languages are in
nondeterministic linear space.

We then proceed to the main results concerning DARM’s, first establishing that
those languages recognised by such machines in constant time and polynomial
time coincide with the regular languages and P respectively. It is shown that
various problems such as recognising context-free languages, recognising
Boolean languages and the multi-sources connectivity problem have a lower time
complexity in the DARM model in comparison to plain RAM models. We obtain
almost tight complexity bounds for some of these problems. Owing to the tight
connection between automatic functions and deterministic one-tape Turing
machines, traditional crossing sequence arguments used to establish lower
bounds on the running time of one-tape Turing machines apply to DARM’s as
well.

The paper then moves on to NARM’s, in particular showing that the class of
languages recognised by NARM’s in polynomial time coincides with NP. The time
complexity of various problems in the NARM model, including that of
recognising non-palindromes, 3SAT and context-free languages are then studied.
The key observation for results concerning NARM’s is similar to that in the
case of DARM’s, that is, one often gets a speedup in time complexity that is
nonetheless not too unreasonable.

We conclude by examining more powerful variants of ARM’s – first, by allowing
unbounded automatic relations; second, by padding the input at the start of
the computation with “working space” that is larger than the original input
length. In the second variant, if the input is padded with a string that is at
least polynomially longer than the original input length, then one obtains a
Polynomial-Size Padded Automatic Register Machine (PARM), and if the padding
string is at least exponentially longer than the original input length, then
an Exponential-Size Padded Automatic Register Machine (ExpARM) is obtained.
The increase in computational power as a result of padding the input is
illustrated by the fact that QSAT – the Quantified Boolean Formula
Satisfaction problem – can be decided by an ExpARM in linear time (as we will
show in Section 7), as well as the fact that the class of languages decidable
in polynomial time by ExpARM’s is equal to PSPACE. Moreover, even a
polynomial-size padding can boost computational power: one can show that a
$(c\log(n))$-variable version of 3SAT can be decided by a PARM in
polylogarithmic time. Finally, we prove that under the Exponential Time
Hypothesis (ETH), the class of languages decided by PARM’s in sublinear time
is strictly greater than that decided by DARM’s in sublinear time. Many
results in this paper build on prior work on automatic functions and relations
[8, 31, 39].

##  2 Preliminaries

Let $\Sigma$ denote a finite alphabet. We consider set operations including
union ($\cup$), concatenation ($\cdot$), Kleene star ($\ast$), intersection
($\cap$), and complement ($\lnot$). Let $\Sigma^{*}$ denote the set of all
strings over $\Sigma$. Let the empty string be denoted by $\varepsilon$. For a
string $w\in\Sigma^{*}$, let $|w|$ denote the length of $w$ and
$w=a_{1}a_{2}...a_{|w|}$ where $a_{i}\in\Sigma$ denotes the $i$-th symbol of
$w$. We also use $w_{i,j}$ to denote the substring $a_{i}a_{i+1}...a_{j}$. Fix
a special padding symbol $\\#$ not in $\Sigma$. Let $x,y\in\Sigma^{*}$ such
that $x=x_{1}x_{2}\ldots x_{m}$ and $y=y_{1}y_{2}\ldots y_{n}$. Let
$x^{\prime}=x_{1}^{\prime}x_{2}^{\prime}\ldots x_{r}^{\prime}$ and
$y^{\prime}=y_{1}^{\prime}y_{2}^{\prime}\ldots y_{r}^{\prime}$ where
$r=\max(m,n)$, $x_{i}^{\prime}=x_{i}$ if $i\leq m$ else $\\#$, and
$y_{i}^{\prime}=y_{i}$ if $i\leq n$ else $\\#$. Then, the convolution of $x$
and $y$ is
$conv(x,y)=\binom{x_{1}^{\prime}}{y_{1}^{\prime}}\binom{x_{2}^{\prime}}{y_{2}^{\prime}}\ldots\binom{x_{r}^{\prime}}{y_{r}^{\prime}}$
[39]. In other words, a convolution of two (or more) strings is formed by
making pairs symbol-by-symbol with appropriate padding at the end for shorter
strings. A relation $R\subseteq X\times Y$ is automatic iff the set
$\\{conv(x,y):(x,y)\in R\\}$ is regular. Likewise, a function $f:X\rightarrow
Y$ is automatic iff the relation $\\{(x,y):x\in domain(f)\land y=f(x)\\}$ is
automatic [40]. An automatic relation $R$ is bounded iff $\exists$ constant
$c$ such that $\forall(x,y)\in R,\leavevmode\nobreak\ \text{abs}(|y|-|x|)\leq
c$. On the other hand, an unbounded automatic relation has no such
restriction. Automatic functions and relations have a particularly nice
feature as shown in the following theorem.

######  Theorem 2.1 (Hodgson [20], Khoussainov and Nerode [26]).

Every function or relation which is first-order definable from a finite number
of automatic functions and relations is automatic, and the corresponding
automaton can be effectively computed from the given automata.

A grammar is a 4-tuple $(N,\Sigma,S,P)$ where $N$ and $\Sigma$ are disjoint
sets of non-terminal and terminal symbols. $S\in N$ is the starting symbol and
$P$ is the set of rules. Different restrictions on the rules in $P$ define
different family of languages. Moreover, $l\Rightarrow r$ denotes that $r$ can
be derived from $l$ in one step while $l\Rightarrow^{*}r$ denotes that $r$ can
be derived from $l$ in zero or more steps. A context-free grammar
$(N,\Sigma,S,P)$ is a grammar in which every rule in $P$ is restricted to be
in the form of $A\rightarrow\alpha$ where $A\in N$ and
$\alpha\in(N\cup\Sigma)^{*}$. A context-free language is a language generated
by a context-free grammar. For simplicity, we assume that the language does
not contain the empty string. A context-free grammar $(N,\Sigma,S,P)$ is in
Chomsky Normal Form if every rule in $P$ is restricted either in the form of
$A\rightarrow u$ or $A\rightarrow BC$ where $A,B,C\in N$ and $u\in\Sigma$. A
context-free grammar $(N,\Sigma,S,P)$ is in Greibach Normal Form if every rule
in $P$ is restricted in the form of $A\rightarrow\alpha$ where $A\in N$ and
$\alpha\in\Sigma N^{*}$. In informal definition by Okhotin [33], a Boolean
grammar $(N,\Sigma,S,P)$ extends context-free grammars by allowing two
additional types of rules in $P$: (1) $A\rightarrow\alpha\leavevmode\nobreak\
\&\leavevmode\nobreak\ \beta$ where $A\in N$ and
$\alpha,\beta\in(N\cup\Sigma)^{*}$: this type of rule states that for any
$w\in\Sigma^{*},A\Rightarrow^{*}w$ if $\alpha\Rightarrow^{*}w$ and
$\beta\Rightarrow^{*}w$; and (2) $A\rightarrow\lnot\alpha$ where $A\in N$ and
$\alpha\in(N\cup\Sigma)^{*}$: this type of rule states that for any
$w\in\Sigma^{*},A\Rightarrow^{*}w$ if $\alpha\not\Rightarrow^{*}w$. A Boolean
language is a language generated by a Boolean grammar. A Boolean grammar
$(N,\Sigma,S,P)$ is in Binary Normal Form if every rule in $P$ except
$S\rightarrow\varepsilon$ is restricted either in the form of $A\rightarrow u$
or $A\rightarrow B_{1}C_{1}\leavevmode\nobreak\ \&\leavevmode\nobreak\
\cdots\leavevmode\nobreak\ \&\leavevmode\nobreak\
B_{m}C_{m}\leavevmode\nobreak\ \&\leavevmode\nobreak\ \lnot
D_{1}E_{1}\leavevmode\nobreak\ \&\leavevmode\nobreak\
\cdots\leavevmode\nobreak\ \&\leavevmode\nobreak\ \lnot
D_{n}E_{n}\leavevmode\nobreak\ \&\leavevmode\nobreak\
\lnot\varepsilon\leavevmode\nobreak\ (m\geq 1,n\geq 0)$ where
$A,B_{i},C_{i},D_{i},E_{i}\in N$ and $u\in\Sigma$.

This paper uses a standard definition of Turing machines by Arora and Barak
[2] and focuses on single-tape Turing machines. We consider a one-dimensional
tape that is infinite to the right, consisting of a sequence of cells. Each
cell can hold a symbol from a finite set $\Gamma$ called the alphabet of the
machine. Note that the alphabet of a language $\Sigma$ will be a subset of
$\Gamma$ in this Turing machine model. The whole (non-empty) content of the
tape at one point of time is defined as the content of the machine. The tape
is equipped with a tape head pointing a cell to read or write the symbol on
that cell in a single step. The tape head is initially pointing to the
leftmost cell and can move left or right in a single step. A Turing machine
$M$ is described as a triple $\langle\Gamma,Q,\delta\rangle$ containing:

  1. 1.

The alphabet of the machine $\Gamma$. Let $\square\in\Gamma$ be a symbol
denoting an empty cell.

  2. 2.

A set $Q$ consisting of the possible states of the machine $M$. Let
$q_{start}$, $q_{halt\\_accept}$, $q_{halt\\_reject}\in Q$ denote the start
state, halt then accept state, and halt then reject state respectively.

  3. 3.

A transition function $\delta:Q\times\Gamma\rightarrow
Q\times\Gamma\times\\{L,R,S\\}$ describing the rules of $M$ in performing each
step. The rule describes: if the machine is in some state $\in Q$ and the tape
head reads some symbol $\in\Gamma$ then the machine will change its state to
some state $\in Q$, the tape head will write some symbol $\in\Gamma$ in the
cell it is pointing to, and then it either moves left, right, or stay.

An input is initially written on the leftmost cells of the tape and other
cells will be empty. The time complexity of a machine on input $x$ is the
minimum number of steps needed to reach $q_{halt,accept}$ or
$q_{halt,reject}$.

The exact concept of register machine varies from author to author. This paper
uses a definition of register machine which only has constantly many registers
— each capable of storing a non-negative integer — therefore the indirect
access operation $(R_{i}\leftarrow R_{R_{j}})$ is not used. We use basic
arithmetic operations and comparisons $(<,>,=)$ as in Floyd and Knuth [11] in
addition to allowing constant values assignment and bitwise operations (as
found in various programming languages like C, C++, and Javascript) by
Hartmanis and Simon [16]. Hartmanis and Simon observed that including either
concatenation or multiplication makes the concept to cover $PSPACE$ in
polynomially many steps therefore both are not used by us. Furthermore, inputs
were read explicitly in the program and writing was only possible in programs
which compute functions. The statements are numbered (with line numbers) and
conditional and unconditional $goto$ are allowed. For computing characteristic
functions of set, the explicit $halt\\_accept$ and $halt\\_reject$ operations
are used. Readers are advised to check Cook and Reckhow [10] for the relation
between register machine (using a RAM model) and Turing machine.

##  3 Automatic Register Machines

###  3.1 Formal Definition

Formally, we denote an Automatic Register Machine (ARM) by $M$ and represent
it as a quintuple $\langle\Gamma,\Sigma,R,Op,P\rangle$ by the following
definition. Semantically, our model tries to generalize the standard register
machines where the operations are no longer limited and the registers are able
to store string. The operations, however, are restricted depending on the the
type of $M$: in the most basic type, Deterministic Automatic Register Machine
(DARM) only allows $Op$ to be the set of automatic functions where the
parameters (and the output) are convoluted. Note that in standard register
machine, all operations are automatic, thus register machine is a subset of
DARM. More types of $M$, which are also more general than DARM, will be
discussed later in Subsection 3.3 and Section 7.

######  Definition 3.1 (Automatic Register Machine, Seah [39]).

Automatic Register Machine (ARM) is a machine
$M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where $M$ is specified by:

  1. 1.

a finite set of registers $R=\\{r_{1},r_{2},\cdots,r_{n}\\}$, each capable of
storing a string, possibly empty, over a fixed machine alphabet $\Gamma$;

  2. 2.

a finite set of possible operations $Op=\\{f_{1},f_{2},\cdots,f_{m}\\}$, where
the $f_{i}$’s are automatic relations and are further restricted to some rules
depending on the type of $M$ (for example, the $f_{i}$’s are automatic
functions if $M$ is deterministic and are bounded automatic relations if $M$
is nondeterministic);

  3. 3.

a program $P$ consisting of a finite list of instructions in form of
$LINE\\_NO:INSTR$.
The $INSTR$ takes one of the following forms:

     * (a)

$read(R_{i})$: assigning the input string over a fixed input alphabet
$\Sigma\subseteq\Gamma$ to register $R_{i}\in R$,

     * (b)

$write(R_{i})$: writing the output string of register $R_{i}\in R$,

     * (c)

$R_{i}\leftarrow w$: assigning any string $w$ over a fixed input alphabet
$\Sigma\subseteq\Gamma$ to register $R_{i}\in R$,

     * (d)

$R_{i}\leftarrow R_{j}$: assigning the value of register $R_{j}\in R$ to
register $R_{i}\in R$,

     * (e)

$R_{i}\leftarrow F(R_{1},R_{2},\cdots,R_{k})$: assigning the result of
operation $F\in Op$ with parameters $R_{1},R_{2},\cdots,R_{k}\in R$ to
register $R_{i}\in R$,

     * (f)

$goto(LINE\\_NO)$: go to the instruction in line $LINE\\_NO$ (i.e.
unconditional jump),

     * (g)

$if\leavevmode\nobreak\ F(R_{1},R_{2},\cdots,R_{k})\leavevmode\nobreak\
then\leavevmode\nobreak\ goto(LINE\\_NO)$: if the result of operation $F\in
Op$ with parameters $R_{1},\cdots,R_{k}\\\ \in R$ is true, then go to the
instruction in line $LINE\\_NO$ (i.e. conditional jump);

     * (h)

$halt$ (or $halt\\_accept$ or $halt\\_reject$): halting the program (and
accept or reject) the input.

Similar to register machine, the program runs sequentially from the first line
number to the next one unless jumped either conditionally or unconditionally,
while performing the instructions along the runtime. A single step is defined
as performing one line of instruction. Initially, all registers store empty
string. After several steps, the program terminates after halted by $halt$. If
one wants to recognize a language, both halt states (i.e. $halt\\_accept$ or
$halt\\_reject$) can be used. Alternatively, one can in deterministic model
write a bit output of ‘1’/‘0’ then halt to denote the acceptance/rejection. If
one wants to write a function value as an output, both halt states are also
allowed especially for nondeterministic models. This is because the whole
computation can be rejected when it turns out in guess-then-verify steps that
some info had been guessed wrongly and thus leads to rejection of the
computation. A partial constant-valued function can also be done in this way
where the output might be skipped (by $halt\\_reject$) as only the output on
members of some language $L$ is considered.

######  Remark.

Note that reading in a register will erase the previous content of the
register. Thus if you have a register machine which sums up all integer inputs
until it reads $0$, then this register machine needs at least two registers,
as otherwise the reading of a new input would erase the old content. One
register is only possible if one reads in the first statement a convolution of
all inputs (or in other longer format like the concatenation of all inputs).

######  Example 3.2.

We give an illustration of an Automatic Register Machine $M$ recognizing
$L_{two}=\\{0^{2^{i}}$ for some non-negative integer $i\\}$. Let
$M=\langle\Gamma,\Sigma,R,Op,P\rangle$, $\Gamma=\\{0,1\\}$, $\Sigma=\\{0\\}$,
$R=\\{r_{1},r_{2}\\}$,
$Op=\\{is\\_empty,is\\_one,is\\_odd,divide\\_by\\_two\\}$, and

$\displaystyle P=\\{\leavevmode\nobreak\ \leavevmode\nobreak\ 01$
$\displaystyle:read(r_{1})$ $\displaystyle 02$
$\displaystyle:if\leavevmode\nobreak\ is\\_empty(r_{1})\leavevmode\nobreak\
then\leavevmode\nobreak\ goto(09)$ $\displaystyle 03$
$\displaystyle:if\leavevmode\nobreak\ is\\_one(r_{1})\leavevmode\nobreak\
then\leavevmode\nobreak\ goto(08)$ $\displaystyle 04$
$\displaystyle:if\leavevmode\nobreak\ is\\_odd(r_{1})\leavevmode\nobreak\
then\leavevmode\nobreak\ goto(09)$ $\displaystyle 05$
$\displaystyle:r_{2}\leftarrow divide\\_by\\_two(r_{1})$ $\displaystyle 06$
$\displaystyle:r_{1}\leftarrow r_{2}$ $\displaystyle 07$
$\displaystyle:goto(03)$ $\displaystyle 08$ $\displaystyle:halt\\_accept$
$\displaystyle 09$ $\displaystyle:halt\\_reject\leavevmode\nobreak\
\leavevmode\nobreak\ \\}$

with the following definition of the operations:

  * 1.

$is\\_empty(w)$ returns true iff $w$ is an empty string,

  * 2.

$is\\_one(w)$ returns true iff $w$ has exactly one occurrence of symbol ‘0’,

  * 3.

$is\\_odd(w)$ returns true iff $w$ has odd occurrences of symbol ‘0’,

  * 4.

$divide\\_by\\_two(w)$ returns $w^{\prime}$ where $w^{\prime}$ is equal to $w$
after modifying every second occurrence of ‘0’ to ‘1’ (e.g. if
$w=10\underline{0}1011\underline{0}$ then
$w^{\prime}=10\underline{1}1011\underline{1}$.)

It is not hard to see that each operations can be constructed with finite
automatons thus they are automatic. Note that for $divide\\_by\\_two$ in
particular, the input $w$ and the output $w^{\prime}$ are convoluted. As $Op$
only consists of automatic functions, therefore $M$ satisfies the requirement
as a DARM. Let $n$ be the occurrence number of ‘0’ in $r_{1}$, which is
initially equal to the length of the input string. The proof of correctness of
the program comes from keep dividing $n$ by $2$ until $n$ is either $1$ — then
accept because $n$ is $2^{i}$ for some non-negative integer $i$ — or other odd
number — then reject. The program will halt and either accept or reject the
input in no more than $O(\log n)$ steps.

###  3.2 Alternative Representation with Single Operation

The representation of an ARM $M=\langle\Gamma,\Sigma,R,Op,P\rangle$ could be
simplified by rewriting each instructions in $P$ to a form of
$LINE\\_NO:F(R_{1},R_{2},\cdots,R_{k})$ for some operations $F$ and
$R_{1},R_{2},\cdots,R_{k}\in R$. The operation $F$ may be a member of $Op$ or
also a “keyword” operation (e.g. $read$, $goto$, $halt$). This new form
resembles a neater operation format in register machine such as $INC(R_{i})$,
$ADD(R_{i},R_{j})$, and $IFEQUAL(R_{i},R_{j},LINE\\_NO)$; which are all
automatic functions. We can then simplify the machine representation even
more: the $LINE\\_NO$ could also be inserted as a parameter in $F$ as well as
all unused registers — which are eventually ignored when the operation is
performed. Thus, the instructions in $P$ could be fully rewritten as
$F(LINE\\_NO,r_{1},r_{2},\cdots,r_{n})$ where $F$ is either a member of $Op$
or keyword operations.

Moreover, based on Theorem 2.1, the first-order definable function from
automatic functions is also automatic. As members of $Op$ and keyword
operations are all automatic, thus we can combine them as a single operation
$G(LINE\\_NO,r_{1},r_{2},\cdots,r_{n})$ where $G$ will run the specific
operations based on the $LINE\\_NO$. After one step, $G$ will update the new
$LINE\\_NO$ as well as some registers. The program $P$ then has this single
operation $G$ alone which will be applied iteratively from
$G(01,\epsilon,\epsilon,\cdots)$, where $01$ denotes the first line number,
until it halts. Therefore, we can replace $P$ by $G$ and finally ARM can be
re-represented as a triple $M=\langle\Gamma,\Sigma,G\rangle$. One single step
is redefined as applying the operation $G$ once.

######  Definition 3.3 (Alternative Representation of Automatic Register
Machine).

An Automatic Register Machine $M=\langle\Gamma,\Sigma,R,Op,P\rangle$ can also
be re-represented as $M=\langle\Gamma,\Sigma,G\rangle$ where $G$ is a single
operation combining all instructions in $P$ with a convolution of the line
number and all registers in $R$ as its parameter.

######  Example 3.4.

We can rewrite the ARM in Example 3.2 recognizing $L_{two}$ by letting
$M=\langle\Gamma,\Sigma,G\rangle$, $\Gamma=\\{0,1\\}$, $\Sigma=\\{0\\}$, and
$G$ with the following definition:

$G(LINE\\_NO,r_{1},r_{2})=\begin{cases}G(02,input,r_{2})&\text{if
$LINE\\_NO=01$}\\\ G(09,r_{1},r_{2})&\text{if $LINE\\_NO=02$ and
$r_{1}=\epsilon$}\\\ G(03,r_{1},r_{2})&\text{if $LINE\\_NO=02$ and
$r_{1}\neq\epsilon$}\\\ G(08,r_{1},r_{2})&\text{if $LINE\\_NO=03$ and `0'
occurs $1$ time in $r_{1}$}\\\ G(04,r_{1},r_{2})&\text{if $LINE\\_NO=03$ and
`0' does not occur $1$ time in $r_{1}$}\\\ G(09,r_{1},r_{2})&\text{if
$LINE\\_NO=04$ and `0' occurs odd times in $r_{1}$}\\\
G(05,r_{1},r_{2})&\text{if $LINE\\_NO=04$ and `0' occurs even times in
$r_{1}$}\\\ G(06,r_{1},div2(r_{1}))&\text{if $LINE\\_NO=05$}\\\
G(07,r_{2},r_{2})&\text{if $LINE\\_NO=06$}\\\ G(03,r_{1},r_{2})&\text{if
$LINE\\_NO=07$}\\\ halt\\_accept&\text{if $LINE\\_NO=08$}\\\
halt\\_reject&\text{if $LINE\\_NO=09$}\end{cases}$

where $input$ is an input string and $div2(w)$ is the result of modifying $w$
by changing every second occurrence of ‘0’ to ‘1’. Note that $G$ is an
automatic function. The machine will start with $G(01,\epsilon,\epsilon)$ and
eventually will halt in the same number of steps as the original machine which
is in $\mathcal{O}(\log n)$ steps where $n$ is the length of the input.

######  Remark.

Note that it is also possible to represent all registers in a single (big)
register which is simply a convolution of all registers. Moreover, while both
representations of $ARM$ are equivalent, the original representation is more
natural and mainly used for the sake of readability. However, the alternative
representation may also be used when proving some findings especially when
they are related to Turing machine computation.

###  3.3 Basic Types of ARM and Relations to Turing machine

We now first define the two basic types of $ARM$ which are our main focus
throughout this paper. Other types will be discussed later in Section 7.

######  Definition 3.5 (Deterministic Automatic Register Machine).

A Deterministic Automatic Register Machine (DARM) is an Automatic Register
Machine $M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where $Op$ is restricted to
automatic functions. Alternatively, a DARM is an Automatic Register Machine
$M=\langle\Gamma,\Sigma,G\rangle$ where $G$ is an automatic function.

######  Definition 3.6 (Nondeterministic Automatic Register Machine).

A Nondeterministic Automatic Register Machine (NARM) is an Automatic Register
Machine $M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where $Op$ is restricted to
bounded automatic relations. Alternatively, a NARM is an Automatic Register
Machine $M=\langle\Gamma,\Sigma,G\rangle$ where $G$ is a bounded automatic
relation.

In NARM, the bounded version of automatic relations is preferred to avoid the
ability to guess a huge witness in one step by unboundedness, which may
recognize a larger complexity class as discussed in Subsection 7.1.
Furthermore, the two concepts differ when act as functions: a nondeterministic
bounded automatic function can only have polynomial-sized output, while for
the unbounded one it can have exponential-sized output e.g. a concatenation of
all $n$-digits binary numbers separated by symbol ‘2’. We may now define the
complexity class of the models.

######  Definition 3.7 (Deterministic Automatic Register Machine Complexity).

Let $f(n)$ be any function in the input size $n$. DAL[$f(n)$] is the class of
languages accepted by DARM in $\mathcal{O}(f(n))$ steps.

######  Definition 3.8 (Nondeterministic Automatic Register Machine
Complexity).

Let $f(n)$ be any function in the input size $n$. NAL[$f(n)$] is the class of
languages accepted by NARM in no more than $\mathcal{O}(f(n))$ steps.

By this definition, $L_{two}$ in Example 3.2 is in $\text{DAL}[\log n]$.
Similar to nondeterministic Turing machine, a string in NARM is accepted iff
at least one of the nondeterministic computation path halt with accept. Note
that all accepting paths must be done in no more than $\mathcal{O}(f(n))$
steps for the language being in $\text{NAL}[f(n)]$. Next, the following two
theorems give the basic connection between automatic functions and bounded
relations to Turing machine computations.

######  Theorem 3.9.

(Case, Jain, Seah and Stephan [8, Theorem 2.4]) A function is automatic iff it
can be computed in $\mathcal{O}(n)$ time by a deterministic one-tape Turing
machine whose input and output start at the same cell, where $n$ is the length
of the input string.

######  Corollary 3.10.

Any step by a bounded automatic relation $R$ can be simulated by a one-tape
nondeterministic Turing machine in $\mathcal{O}(m)$ steps where $m$ is the
length of the longest current register content and $m$ is bounded by
$n+\mathcal{O}(t)$ where $t$ is the number of Automatic Register Machine steps
done after the machine reads the input of length $n$.

The core consequence of Theorem 3.9 is that we can translate a DARM to an
equivalent deterministic Turing machine which runs linear-time longer. Note
that the linear here is subjected to the length of the register. To show this,
consider any $\text{DARM}\leavevmode\nobreak\
M=\langle\Gamma,\Sigma,G\rangle$. The parameters of $G$ are convoluted and
this string could be pasted into a Turing tape. In a single step of $M$, the
parameters are updated by applying an automatic function $G$ on it. By the
theorem, this can be simulated by the Turing machine in linear step of the
length of the parameters, thus Q.E.D. Moreover, it is also possible to have
the following converse: we can translate a deterministic Turing machine $M$
which runs in $\mathcal{O}(f(n))$ to an equivalent DARM which runs in
$\text{DAL}[f(n)]$. The proof is quite similar where now the content of the
Turing tape is pasted as a single register in DARM and show that each Turing
machine step is an automatic function. Furthermore, the results can extended
to NARM (with nondeterministic Turing Machine) as a consequence of Theorem
3.10 in similar manner. Formal proof of these results can be found later in
Section 5 and 6.

##  4 ARM In Comparison to Other Models

This section is solely dedicated to justify that Automatic Register Machine is
an adequate computation model which has primitive operations that are
expressive and powerful yet not giving an unrealistic speed-up compared to
other models.

###  4.1 Deterministic Polynomial Time Model with Transducers as Primitive
Operations to Solve PSPACE-Complete

The computation model with transducers as primitive operations is similar to
ARM with the only difference that for $M=\langle\Gamma,\Sigma,G\rangle$, $G$
is a transducer. Informally, transducers allow one of the symbol to be
$\epsilon$ when “convoluted” and such “convolution” can be recognized by an
automaton (called Mealy machine), thus it is a superset of automatic functions
and relations. This model is close to a language generating device called an
Iterated Sequential Transducer by Bordihn, Fernau, Holzer, Manca and Martín-
Vide [4] albeit the complexity is usually measured by its number of states
(i.e. state complexity).

We show that the computation model with transducers as primitive operations
gives an extreme speed-up by solving a PSPACE-complete problem in only
polynomial number of steps. This can be deduced from our result in Theorem 7.9
later that a DARM with an access to exponential-length padding (i.e. allowing
its working space to be exponential larger) can solve $QSAT$ in
$\mathcal{O}(n)$ steps, and one can simulate the exponential padding by a
transducer which runs through a loop $p(n)$ times and each time doubles the
length of $y$ by mapping $y$ to a string twice the length (to get a padding of
length at least $2^{p(n)}$). Hartmanis and Simon [16] also show that
$NPSPACE\subseteq$ polynomial steps on RAM with concatenation. They write
later that they need only bitwise operations, concatenation, and division by
2; not even substring operation. All these operations can be realised by
transducers, therefore their result also shows that polynomial number of
transducer steps contains PSPACE. Though the exact construction is a bit
technical, the result is not that important in the context of this paper
therefore the working out of details and the verification is left to the
reader. As a comparison, such blow-up will be unlikely to happen in DARM as
based on Theorem 5.2 later, if 3SAT or $QSAT$ are in $\text{DAL}[poly(n)]$
then they are also in $P$.

###  4.2 ARM and G-systems

Generative systems (g-systems), introduced by Rovan [36] (stemming from
$\Gamma$-systems by Wood [43]) as a natural model for language generating
devices, depend on various types of transducers. We first define the
g-systems.

######  Definition 4.1 (Generative systems [36]).

A generative system (g-system) is a 4-tuple $G=\langle N,\Sigma,M$ $,S\rangle$
where $N$ and $\Sigma$ are disjoint set of non-terminal and terminal symbols,
$S\in N$ is the starting symbol and $M$ is a transducer with $M(w)=\emptyset$
for each $w\in\Sigma^{+}$. $M$ is a 6-tuple
$(K,N\cup\Sigma,N\cup\Sigma,H,q_{0},F)$, where $K$ is a finite set of states,
$q_{0}$ is the initial state, $F\subseteq K$ is a set of accepting states and
$H$ is a finite subset of $K\times(N\cup\Sigma)\times(N\cup\Sigma)^{+}\times
K$. A computation of $M$ is a word $h_{1}\ldots h_{n}\in H^{+}$ such that if,
for each $i\in\\{1,2,3,4\\}$, $p_{i}$ is the homomorphism on $H^{*}$ for which
$p_{i}(x_{1},x_{2},x_{3},x_{4})=x_{i}$, then $p_{1}(h_{1})=q_{0}$,
$p_{4}(h_{n})\in F$ and $p_{1}(h_{i+1})=p_{4}(h_{i})$ for $1\leq i\leq n-1$. A
computation of $M$ of length $n$ may be interpreted as a sequence of $n$
configurations such that the end state of each of the first $n-1$
configurations is the start state of its succeeding configuration;
furthermore, the first configuration starts with the initial state $q_{0}$ and
the end state of the last configuration is an accepting state. Let $\prod_{M}$
denote the set of all computations of $M$. For each language
$L\subseteq(N\cup\Sigma)^{*}$, $M(L)$ is defined to be
$p_{3}\left(p_{2}^{-1}(L)\cap\prod_{M}\right)$; in other words, for every
$w\in L$, if
$(x_{1}^{1},x_{2}^{1},x_{3}^{1},x_{4}^{1})(x_{1}^{2},x_{2}^{2},x_{3}^{2},x_{4}^{2})\ldots(x_{1}^{n},x_{2}^{n},x_{3}^{n},x_{4}^{n})$
is a computation such that $x_{2}^{1}x_{2}^{2}\ldots x_{2}^{n}=w$, then
$x_{3}^{1}x_{3}^{2}\ldots x_{3}^{n}\in M(L)$.

As is usually defined for grammars, the language generated by a g-system $G$
consists of all $w\in\Sigma^{*}$ such that there is a finite sequence
$S=v_{1},v_{2},\ldots,v_{k}=w$ of words over $N\cup\Sigma$ with $v_{i+1}\in
M(\\{v_{i}\\})$ for all $i\in\\{1,\ldots,k-1\\}$. We note that the transducer
$M$ in Definition 4.1 maps subsets of $(N\cup\Sigma)^{*}$ to subsets of
$(N\cup\Sigma)^{*}$ and is thus nondeterministic (otherwise, the language
generated by $G$ consists of at most one word).

As a generating language device, one step of derivation in the g-system is not
using a set of rules $P$ as in grammar but the transducer $M$. One step of
$l\Rightarrow r$ is valid if and only if $r\in M(l)$. Various families of
g-systems are differentiated by different types of their transducers. If the
transducer does not allow deletion, then it is called $\epsilon$-free
g-system, else we can call it a g-system with deletion. If the transducer is
some type of directed acyclic graph and either one goes forward in it or one
stays on some state and copies and pastes the current symbols, then it is
called a sequential g-system, else it is called a parallel g-system. It is not
hard to see the similarity between g-system if used as a language accepting
device with our model apart from the different types of operations. We list
out the connection between them as follows.

  1. 1.

If an $\epsilon$-free g-system accepting (or generating) $L$, there exists a
nondeterministic automatic function which also recognizes $L$ such that if the
g-system generates some word $w$ in $m$ steps then $w$ can be accepted in
$\text{NAL}[m]$ for some $m$. However, if NARM measures the time complexity in
a weak-measure i.e.

$\max\\{\min\\{\text{acceptance time for}\leavevmode\nobreak\
x\leavevmode\nobreak\ \text{on a nondeterministic path}\\}:|x|=n,x\in L\\},$

then such NARM might be faster as some languages are in $O(\log\log n)$ steps,
as shown later in Theorem 6.4, while a g-system can in each step increase the
length only by a constant factor and needs at least $\Omega(\log n)$ steps.

  2. 2.

G-systems with deletion is more powerful than our model as they can recognize
context-sensitive language in polynomial steps. The proof is based on the
symbol duplication, which allows solving $PSPACE$ in polynomial steps [16].

  3. 3.

Sequential g-systems are weaker than the parallel one as they do not have the
ability to duplicate a symbol. In fact, they are also weaker than our DAL
model. The fact that sequential g-systems work symbol-by-symbol with a
limitation of copy-pasting on some positions shows that it is actually a
restrictive automatic function steps.

We conclude our connection with the following evaluation. The essence of this
is that sequential g-systems do not allow too powerful steps but are slower
than our deterministic model, while parallel g-systems with deletion allow
speed-ups which incorporate larger complexity-classes into the class of $NP$
in polynomial deterministic steps. Even the $\epsilon$-free g-system is
comparable to our nondeterministic model. So our model may somehow sit in the
middle of the two by accommodating the adequate speed-up while avoiding
unrealistic blow-up.

###  4.3 Iterated Uniform Finite-State Transducers and its Open Problem

Kutrib, Malcher, Mereghetti, and Palano [30] introduced Iterated Uniform
Finite-State Transducers as a model of computation preserving the polynomial
time. This model uses length-preserving transducers as primitive operations
and might be a real restriction as allowing only a subclass of $P$ for
polynomial time recognition. As automatic functions can have output a constant
longer than the input in each step, the overall model using automatic
functions is not subjected to the length-limitation constraint and covers all
polynomial-time decidable languages when recognizing languages in polynomially
many steps, therefore more powerful. In a side note, the authors left it as an
open problem whether their model (in arbitrary time) can cover the whole of
context-sensitive languages. We prove the answer is positive by the following
proof.

Roughly speaking, an Iterated Uniform Finite-State Transducer is a finite-
state transducer that processes the input in multiple sweeps; in the first
sweep, it reads the input followed by an endmarker and outputs a word; in
subsequent sweeps, it reads the output word of the previous sweep and outputs
a new word. Formally, a nondeterministic iterated uniform finite-state
transducer is a system $T=\langle
Q,\Sigma,\Delta,q_{0},\triangleleft,\delta,F_{+},F_{-}\rangle$, where $Q$ is
the set of internal states, $\Sigma$ is the set of input symbols, $\Delta$ is
the set of output symbols, $q_{0}\in Q$ is the initial state,
$\triangleleft\in\Delta\setminus\Sigma$ is the endmarker, $F_{+}\subseteq Q$
is the set of accepting states, $F_{-}\subseteq Q\setminus F_{+}$ is the set
of rejecting states and $\delta:Q\times(\Sigma\cup\Delta)\mapsto
2^{Q\times\Delta}$ is the transition function (which is total on
$(Q\setminus(F_{+}\cup F_{-}))\times(\Sigma\cup\Delta)$); the endmarker
$\triangleleft$ is output only if it is read. (One observes from this
definition that any word emitted by an Iterated Uniform Finite-State
Transducer has the same length as the input word.) $T$ halts whenever the
transition function is undefined or $T$ enters an accept or reject state at
the end of a sweep. A computation of the nondeterministic iterated uniform
finite-state transducer $T$ on input $w\in\Sigma^{*}$ is a sequence of words
$w_{1},\ldots,w_{i},w_{i+1},\ldots$ such that $w_{1}\in T(w\triangleleft)$ and
$w_{i+1}\in T(w_{i})$; the computation halts if there is an $r\geq 1$ such
that $T$ halts on $w_{r}$. The set of possible words output by $T$ in a
complete sweep on input $w\in(\Sigma\cup\Delta)^{*}$ is denoted by $T(w)$. The
input word $w$ is accepted by $T$ iff all computations on $w$ halt and at
least one computation halts in an accepting state; $w$ is rejected by $T$ iff
all computations on $w$ halt and none of the computations halt in an accepted
state.

The proof is quite similar to the proof of showing context-sensitive languages
are in nondeterministic linear space. The essential idea is to construct a
transducer that reads and outputs a convolution of three components: first,
the input word (whose membership in the given context-sensitive language is to
be tested); second; a “work-tape” for simulating context-sensitive grammar
derivations; third, a counter for measuring the length of a derivation. At the
beginning, let us fix a constant-sized ordered set of digits (in the alphabet)
for counting e.g. $\\{0,1,\cdots,9\\}$, such that this set has size equal to
the total number of terminals and non-terminals plus one (this is to ensure
that whenever there is a repetition-free derivation of the word, the process
does not run out of the steps to be counted, but can complete the derivation).
Here, $9$ acts as the largest digit but it does not mean that there are
exactly $10$ digits. The input/output alphabet of the transducer consists of
all convolutions of the form $\left(\begin{smallmatrix}a\\\ b\\\
c\end{smallmatrix}\right)$, where $a$ (resp. $b$) either represents a letter
in the alphabet of the input grammar or is a blank symbol, and $c$ is either a
digit in the counting alphabet or a blank symbol. The first run of the
transducer translates the input to a same-length-word in the tape alphabet
which is a convolution of the input, the counter “$00\cdots 0$” and the start
symbol $S$ (using blank symbols as appropriate to ensure that all three
components are of equal length). Now for any given $n$, one may determine from
the input grammar the maximum length of a repetition-free derivation of a word
of length $n$. The counter starts from “$0000\cdots$” and goes increasingly to
“$9999\cdots$” in some sufficiently large alphabet with a word as long as the
input and forces a reject, if the input has not been derived in the
corresponding maximum possible number of steps in a repetition-free
derivation. If a derivation of a symbol $A$ becomes, under context, a word $w$
of length at least $1$, the transducer will nondeterministically guess the
distribution of its symbols over the position of $A$ so that they go into the
target position. If there is no non-terminal in the word, we just simply
increment the counter. The machine will accept if the generated word and the
given word are equal (independently of the counter number). The machine will
reject if the last counter (“$9999\cdots$”) is reached, thus if there is any
incorrect guess then the derivation will be stuck and eventually be rejected.

Finally, we remark that every automatic function which maps inputs to outputs
of the same length can be computed by a transducer which is length-preserving.
The reason is that an automatic function is verified by a synchronous nfa
which reads one symbol of each the input and the output per cycle; now turning
the “reading of the symbol” into “writing of a symbol” where the successor
state depends in the same way as before on the two symbols processed (the
input and the output symbol), turns the nfa into a transducer which in each
cycle reads one input symbol and writes one output symbol. At the input-end-
symbol, this nfa indicates that the sweep was successful iff the nfa on the
sequence of all the inputs processed and outputs generated would say that the
(input,output)-pair is in the automatic relation. This way one can translate
the nfa recognising the automatic relation into a transducer given as a Mealy
machine which computes a multivalued function of the possible next steps in
the derivation from the given step (with the corresponding maintenance of the
counter and comparison with the input-word).

##  5 Key Results in DARM

As we can translate a DARM to an equivalent deterministic Turing machine which
runs linear-time longer, theoretically it may be — but not always — possible
for some languages to be recognized by DARM in up to linear-time fewer steps
than an established algorithm for such language in standard Turing machine
steps. This section highlights several key results of those interesting
languages in DAL class.

###  5.1 Deterministic Polynomial ARM and Lower Bound Technique

We start with the following theorem which is a direct consequence of authors’
result in another work [12].

######  Theorem 5.1.

$\text{DAL}[1]=Regular$.

###### Proof.

Let $P_{k}$ be the class of languages decided by a $k$-step DARM program. We
will show that languages in $P_{k}$ are regular over constant $k$ by
induction. For $k=1$, any language $L\in P_{1}$ must be regular as the
automatic function step is a Deterministic Finite Automaton (DFA) recognizing
$L$. Now assume that all languages in $P_{k}$ are regular. For any language
$L\in P_{k+1}$ and its $\text{DARM}\leavevmode\nobreak\
M=\langle\Gamma,\Sigma,G\rangle$, let $g_{k}$ be the content (parameters) of
$G$ after $k$-th step. One can construct a Nondeterministic Finite Automaton
(NFA) guessing $g_{k}$ then verify with the automatic function step (i.e. a
DFA) on the $(k+1)$-th step whether to accept or reject the string. This whole
process can be replaced by another DFA of exponential-larger size by
processing the convolution of the content of $G$ generated from the first step
to the $(k-1)$-th step. Note that the program now consists of $k$ steps and
the last step is done by a DFA therefore $L\in P_{k+1}$ is regular. ∎

Mentioned briefly in Subsection 3.3 and 4.1, we can also prove the following
equality.

######  Theorem 5.2.

$\text{DAL}[poly(n)]=P$.

###### Proof.

To show $\text{DAL}[poly(n)]\subseteq P$, note that in a single step of an
automatic function the space used grows by a constant, thus each step update
of the registers can be done in polynomial time in the length of the register
string. For $P\subseteq\text{DAL}[poly(n)]$, we refer to the result from
Hartmanis and Simon [16] where $P$ can be covered by polynomial many steps of
basic operations which are in fact automatic functions without any use of
indirect addressing. ∎

We also give the definition of a crossing sequence by Hennie [18] as a tool to
compute a lower bound on the computational complexity of a language and then
connect it in the context of the execution of automatic relations in DARM.

######  Definition 5.3 (Crossing Sequence, Hennie [18]).

Given a deterministic one-tape Turing Machine and an input, a crossing
sequence of the $i$-th cell is a sequence of states whenever the head of
Turing Machine crosses between the $i$-th and $i+1$-th cells along the
computation. Informally, a crossing sequence of the $i$-th cell describes how
the Turing Machine carries the information between the left and right cells
separated by the border of $i$-th and $i+1$-th cell. The total computation
time is the sum of the lengths of all crossing sequences.

The connection of crossing sequences to the execution of automatic relations
in a $\text{DARM}\leavevmode\nobreak\ M=\langle\Gamma,\Sigma,G\rangle$ is the
following. Each step in the execution of $G$ can be simulated by a double-pass
of a deterministic one-tape Turing machine. The machine passes first forward
and then backward over the content of the register to replace the convolution
(of $r$ and $r^{\prime}$, where $r^{\prime}$ is the content of $r$ after the
execution of $G$) by their updated versions in all cells. As the state may
change at the end of each pass, hence the crossing sequence becomes only at
most two symbols (states) longer in one step update. In general, a program
line number update in DARM can also be simulated similarly. Thus, the length
of a $\text{DAL}[f(n)]$-computation gives a crossing sequence of length
$\mathcal{O}(f(n))$. So a lower bound on the crossing sequence length gives a
lower bound on the DAL-computation too.

###  5.2 Context-Free Languages and Boolean Languages in DARM

We first mention the CYK algorithm, discovered independently by Cocke, Kasami,
and Younger [1, 24, 44]: a parsing algorithm for context-free languages based
on a bottom-up approach of dynamic programming. Given a context-free language
$L$ in its grammar $G=(N,\Sigma,S,P)$ in Chomsky Normal Form, the algorithm
tries to parse an input string $s=s_{1}\cdots s_{n}$ with length $n$ using CYK
triangular matrix. Here is an example of the CYK triangular matrix for
$|s|=4$.

|  |  |  | $\alpha_{1,4}$ |  |  |
---|---|---|---|---|---|---|---
|  |  | $\alpha_{1,3}$ |  | $\alpha_{2,4}$ |  |
|  | $\alpha_{1,2}$ |  | $\alpha_{2,3}$ |  | $\alpha_{3,4}$ |
| $\alpha_{1,1}$ |  | $\alpha_{2,2}$ |  | $\alpha_{3,3}$ |  | $\alpha_{4,4}$
$s=$ | $s_{1}$ |  | $s_{2}$ |  | $s_{3}$ |  | $s_{4}$

The variables $\alpha_{i,j}$ will be the set of all non-terminals generating
substring $s_{i}\cdots s_{j}$ i.e. $\alpha_{i,j}=\\{A\leavevmode\nobreak\
|\leavevmode\nobreak\ A\in N,\leavevmode\nobreak\ A\Rightarrow^{*}s_{i,j}\\}$.
The algorithm starts with the bottom row computing
$\alpha_{i,i}=\\{A\leavevmode\nobreak\ |\leavevmode\nobreak\ A\rightarrow
s_{i,i}\in P\\}$. Iteratively, $\alpha_{i,j}$ can be efficiently computed
using its (lower-)left diagonal: $\alpha_{i,k}$ where $k<j$; and (lower-)right
diagonal: $\alpha_{k,j}$ where $k>i$ . This is captured by the matrix such
that $\alpha_{i,j}=\bigcup_{i\leq k<j}\leavevmode\nobreak\
\alpha_{i,k}\times\alpha_{k+1,j}$ where $X\times Y=\\{A\leavevmode\nobreak\
|\leavevmode\nobreak\ B\in X,C\in Y,\leavevmode\nobreak\ A\rightarrow BC\in
P\\}$. Finally, $s\in L$ iff $S\in\alpha_{1,n}$. The algorithm clearly runs in
$\mathcal{O}(n^{3})$ in modern RAM model and translates to an
$\mathcal{O}(n^{4})$-algorithm on a one-tape deterministic Turing machine. We
show that the problem needs less number of steps in DARM.

######  Theorem 5.4.

Given a context-free language $L$ in its grammar $G=(N,\Sigma,S,P)$ in Chomsky
Normal Form, recognizing an input with length $n$ in $L$ can be done in
$DAL[n^{2}]$.

###### Proof Sketch.

The idea is similar to using 1-dimensional arrays in solving context-free
languages in quadratic steps by Kosaraju [27]. We simulate CYK algorithm but
for each variables $\alpha_{i,j}$ we only need constant steps to compute
$\bigcup_{i\leq k<j}\leavevmode\nobreak\ \alpha_{i,k}\times\alpha_{k+1,j}$
which is done in parallel. We present the DARM algorithm as follows.

For $0\leq k<n$, let the $k$-th layer of CYK triangular matrix be the
$(k+1)$-th row from the bottom i.e. the set of $\alpha_{i,i+k}$ for $1\leq
i\leq n-k$. Assign two registers $R_{l}$ and $R_{r}$ in DARM to be responsible
of left and right diagonals respectively. The DARM algorithm will run in $n$
iterations and process layer-by-layer from $0$-th to $(k-1)$-th. When it
finished processing the $k$-th layer, the algorithm guarantees the following
properties:

  1. 1.

Started with some padding, $R_{l}$ will be a concatenation of all left
diagonals up to the $k$-th layer (i.e. left-diagonals of $\alpha_{i,j}$ for
$i\leq j\leq\min\\{n,i+k\\}$) written from left-to right and separated by some
separator.

  2. 2.

$R_{r}$ will be a concatenation of all right diagonals up to the $k$-th layer
(i.e. right-diagonals of $\alpha_{1,i}$ for $1\leq i\leq k$ and $\alpha_{i,j}$
for $i\leq j\leq\min\\{n,i+k\\}$) written from left-to right and separated by
some separator, followed by some padding.

  3. 3.

The separators in $R_{l}$ and $R_{r}$ are lined up in such a way that
$\alpha_{1,1}$ in $R_{l}$ is matched with $\alpha_{2,2+k}$ in $R_{r}$. In
other words, full “blocks” of diagonals are aligned to compute $\bigcup_{i\leq
k<j}\leavevmode\nobreak\ \alpha_{i,k}\times\alpha_{k+1,j}$ in the next
iteration.

Below is the illustration of above properties when processing a string of
length $4$ for the first three iterations. A dashed line denote a separator
symbol. Note that each of possible subsets of $N$ of $G$ can be denoted by a
single symbol in $\Gamma$ of $\text{DARM}\leavevmode\nobreak\ M$ thus each
$\alpha_{i,j}$ is represented as a single symbol.

$0:$ | $R_{l}$ | $\\#$ | $\alpha_{1,1}$ | $\alpha_{2,2}$ | $\alpha_{3,3}$ | $\alpha_{4,4}$
---|---|---|---|---|---|---
$R_{r}$ | $\alpha_{1,1}$ | $\alpha_{2,2}$ | $\alpha_{3,3}$ | $\alpha_{4,4}$ | $\\#$

$1:$ | $R_{l}$ | $\\#$ | $\\#$ | $\\#$ | $\alpha_{1,1}$ | $\alpha_{1,2}$ | $\alpha_{2,2}$ | $\alpha_{2,3}$ | $\alpha_{3,3}$ | $\alpha_{3,4}$ | $\alpha_{4,4}$
---|---|---|---|---|---|---|---|---|---|---|---
$R_{r}$ | $\alpha_{1,1}$ | $\alpha_{1,2}$ | $\alpha_{2,2}$ | $\alpha_{2,3}$ | $\alpha_{3,3}$ | $\alpha_{3,4}$ | $\alpha_{4,4}$ | $\\#$ | $\\#$ | $\\#$

$2:$ | $R_{l}$ | $\\#$ | $\\#$ | $\\#$ | $\\#$ | $\\#$ | $\\#$ | $\alpha_{1,1}$ | $\alpha_{1,2}$ | $\alpha_{1,3}$ | $\alpha_{2,2}$ | $\alpha_{2,3}$ | $\alpha_{2,4}$ | $\alpha_{3,3}$ | $\alpha_{3,4}$ | $\alpha_{4,4}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$R_{r}$ | $\alpha_{1,1}$ | $\alpha_{1,2}$ | $\alpha_{2,2}$ | $\alpha_{1,3}$ | $\alpha_{2,3}$ | $\alpha_{3,3}$ | $\alpha_{2,4}$ | $\alpha_{3,4}$ | $\alpha_{4,4}$ | $\\#$ | $\\#$ | $\\#$ | $\\#$ | $\\#$ | $\\#$

By the construction, the final iteration will eventually compute
$\alpha_{1,n}$ thus the membership of $s$ is tested by checking whether
$S\in\alpha_{1,n}$. To process $0$-th layer in particular, it can be done in
linear steps by first transforming $s_{i}$ to $\alpha_{i,i}$, adding one
padding symbol in the beginning of $R_{l}$ and at the end of $R_{r}$, then
adding $n$ many times the separators.

To process $k$-th layer from $(k-1)$-th layer, one can in a single automatic
step compute all variables in the $k$-th layer by looking at the diagonals
formed by the pairs in $R_{l}$ and $R_{r}$ — ignoring incomplete blocks of
diagonals. Note that $\bigcup_{i\leq k<j}\leavevmode\nobreak\
\alpha_{i,k}\times\alpha_{k+1,j}$ could be computed in that single step as
there is an automaton recognizing the union of subsets of $N$ given that each
$\alpha_{i,k}$ and $\alpha_{k+1,j}$ are already convoluted therefore the
automaton can also compute a subset $\alpha_{i,k}\times\alpha_{k+1,j}$. After
reading the separator, the variable $\alpha_{i,i+k}$ can be formed and
convoluted to the separator (or stored in the third register $R_{t}$) and it
continues to form the next variables. After all variables in the $k$-th layer
is formed, the algorithm needs to put it on the correct positions: to the
right of its left diagonal and to the left of its right diagonal. As its
diagonals are directly before the separator, inserting it to the correct
position can also be done in constant steps. Lastly, some paddings are added
in the beginning of $R_{l}$ and at the end of $R_{r}$ such that $\alpha_{1,1}$
in $R_{l}$ is matched with $\alpha_{2,2+k}$ in $R_{r}$. Adding one padding
needs one step, in addition, some separators might be added as well.

Finally, to compute the total complexity time, one can observe that all
operations are constant and could be reduced to how many times it inserts a
symbol into $R_{l}$ and $R_{r}$. As the length of both will be equal to the
size of CYK triangular matrix, therefore the algorithm runs in
$\text{DAL}[n^{2}]$. ∎

We can further extend the proof in Theorem 5.4 for Boolean languages.

######  Theorem 5.5.

Given a Boolean language $L$ in its grammar $G=(N,\Sigma,S,P)$ in Binary
Normal Form, recognizing an input with length $n$ in $L$ can be done in
$DAL[n^{2}]$.

###### Proof.

The CYK algorithm can be extended to parse Boolean grammars by Okhotin’s work
[33]. The algorithm is exactly the same with some modifications on computing
$\alpha_{i,j}$ as now it allows conjunctions and negations. The algorithm also
runs in $\mathcal{O}(n^{3})$ in modern RAM model. In DARM, we can only modify
the automaton when computing $\alpha_{i,j}$. Note that set operations such as
intersection and complement can be done by introducing an additional Boolean
flag and that will only multiply the number of states in the automaton by a
factor of constant. Therefore the complexity will still be
$\mathcal{O}(n^{2})$. ∎

######  Remark.

Note that the runtime complexity in Theorem 5.4 and 5.5 still translates to an
$\mathcal{O}(n^{4})$-algorithms on a one-tape Turing machine due to the length
of the register becoming $\mathcal{O}(n^{2})$.

###  5.3 Multi-Sources Connectivity Problem in DARM

We define multi-source connectivity problem as the following.

######  Definition 5.6 (Multi-Source Connectivity Problem).

Given a directed graph $G=(V,E)$ with $n$ vertices $\\{1,2,\cdots,n\\}$, and
some vertices as sources $S\subseteq V$, Multi-Source Connectivity Problem is
to find all vertices reachable from at least one of the vertices in $S$.

We then define a string format of a directed graph $G=(V,E)$ with $n$ vertices
$\\{1,2,\cdots,n\\}$ as the following. Note that ‘$|$’ is a separator symbol.

$v_{1}$ | $e_{1,1}$ | $e_{1,2}$ | $\cdots$ | $e_{1,n}$ | $v_{2}$ | $e_{2,1}$ | $e_{2,2}$ | $\cdots$ | $e_{2,n}$ | $\cdots$ | $v_{n}$ | $e_{n,1}$ | $\cdots$ | $e_{n,n}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---

This format represents an adjacency matrix of $G$ which is written row-by-row.
For each row, it starts with the vertex number $v_{i}=i$ followed by its
neighbours: $e_{i,j}=j$ if $(i,j)\in E$, otherwise $e_{i,j}=0$. Note that
$v_{i}$ and $e_{i,j}$ are written in binary form thus each have length $\log
n$. In this way, the string format of $G$ with $n$ vertices has total length
of $\mathcal{O}(n^{2}\log n)$.

As an input of multi-source connectivity problem, in addition to above string
of $G$, we can also have a separate input for $S$: a string of length $n$
denoting the membership of each vertices in $S$ where the $i$-th symbol is $1$
iff $i\in S$ (else, $i$-th symbol will be $0$). Alternatively, if we just want
the input to be a single string, all symbols of $v_{i}$ in the string of $G$
will be convoluted by a tick symbol $\checkmark$ (i.e.
$|\binom{v_{i}}{\checkmark}|$) iff $i\in S$. Note that both input
representations are equivalent and interchangeable with an additional
$\mathcal{O}(n)$ simple automatic function steps to construct one from the
other. To solve the multi-source connectivity problem, the algorithm must tick
all reachable vertices by the similar convolution (or alternatively construct
the membership string of length $n$ of reachable vertices). We then have the
following results.

######  Theorem 5.7.

Multi-source connectivity problem of a directed graph with $n$ vertices can be
solved in $DAL[n\log n]$.

###### Proof.

We use the input format with a single string (i.e. the vertices in $S$ is
convoluted with tick symbol) and try to tick all reachable vertices. We give
the following algorithm:

  1. 1.

Find any ticked vertex $u$ having at least one out-going edge. If no such
vertex exists, then terminate the algorithm.

  2. 2.

Find any $v$ such that $e_{u,v}=v$.

  3. 3.

Tick vertex $v$ (even if $v$ is already ticked).

  4. 4.

Remove all edges going to $v$ and repeat the algorithm.

The algorithm uses the concept of flood-fill where it relays the connectivity
from any visited (i.e. ticked) vertex to another vertex, shown by points $1$,
$2$, and $3$. By removing all in-going edges to vertex $v$ in point $4$, $v$
will be guaranteed to be traversed at most once thus the algorithm will repeat
at most $n$ times.

Now we will calculate the time complexity. Point $1$ can trivially be done in
a constant number of steps. Point $2$ is done similarly as the continuation.
But in addition, the vertex $v$ is copied to another register in
$O(\log\leavevmode\nobreak\ n)$ steps. The copy of $v$ then compared to each
$v_{i}$ in parallel and the matched vertex number will be ticked in point $3$.
By “comparing in parallel” we mean here that the first character of $v$ is
matched to the first character of every vertex, then the second character of
$v$ is matched to the second character of every vertex, and so. As each
matching takes one round and $v$ is represented by $\log(n)$ bits, these
comparisons need only $O(\log\leavevmode\nobreak\ n)$ steps. Point $4$ is done
in the same fashion by comparing $v$ for each $e_{i,j}$ then set the matched
ones to $0$, again in $O(\log\leavevmode\nobreak\ n)$ steps. As there are at
most $n$ iterations, therefore the overall time complexity is $DAL[n\log n]$.
∎

######  Corollary 5.8.

Any graph problem with $n$ vertices whose solution relies on Breadth-First-
Search (BFS) such as Shortest Path in Unweighted Graph, Cycle Detection,
Bipartite Checking, and Eulerian Checking; can be solved in $DAL[n\log n]$.

###### Proof.

BFS can be done with some modifications of the algorithm of Theorem 5.7.
Instead of convoluting $v_{i}$ with a tick, $v_{i}$ will be convoluted with
its distance, starting from $0$ on the source. Assign a register as a counter
$cnt$, initialized with $0$. The modified algorithm is then the following:

  1. 1.

Find any vertex $u$ with distance $=cnt$ and having at least one out-going
edge. If no such vertex exists and $cnt<n$, then increment $cnt$. If no such
vertex exists and $cnt=n$, then terminate the algorithm.

  2. 2.

Find any $v$ such that $e_{u,v}=v$.

  3. 3.

If the distance of vertex $v$ is not set yet, set it to $cnt+1$.

  4. 4.

Remove all edges going to $v$ and repeat the algorithm.

The proof of correctness is still the same as the previous algorithm but now
”the ticks” are done in increasing order of the distance, instead of in an
arbitrary order. The time complexity remains the same. ∎

We also show that, if the graph is acyclic then a faster solution exists given
that the graph is in a nice format.

######  Definition 5.9 (Sorted-Directed-Acyclic-Graph).

A Sorted-Directed-Acyclic-Graph (SDAG) is defined as a directed graph with no
cycles and each edge $(i,j)\in E$ satisfies $i<j$. Note that every directed
acyclic graph can be converted into its respective SDAG e.g. by performing a
topological sort to relabel the vertex numbers.

######  Theorem 5.10.

Multi-source connectivity problem of a SDAG with $n$ vertices can be solved in
$DAL[n]$.

###### Proof.

We give the following algorithm in high-level. Assign two new registers
denoted as $R_{v}$ and $R_{e}$ which has the same length as the input string.
Initially, $R_{v}$ will have exactly a single marker symbol (denoted as
$\uparrow$) located at the same position as the first symbol of $v_{1}$.
$R_{e}$ instead will have exactly $n$ marker symbols located at the same
positions as all the first symbol of $e_{i,1}$ for $1\leq i\leq n$. All other
symbols in $R_{v}$ and $R_{e}$ are blank.

Now, for the next $n$ iterations, we maintain the markings in $R_{v}$ and
$R_{e}$ such that on the $j$-th iteration: $R_{v}$ will have exactly one
single marker at the first symbol of $v_{j}$ and $R_{e}$ will have exactly $n$
markers at the first symbol of each $e_{i,j}$ for $1\leq i\leq n$. Here is the
illustration of the movement of the markers. Note that, as we only mark the
first symbol, the movement can be done in constant steps by moving the markers
to their next spot in parallel.

Iteration | $G$ | $v_{1}$ | $e_{1,1}$ | $e_{1,2}$ | $\cdots$ | $e_{1,n}$ | $v_{2}$ | $e_{2,1}$ | $e_{2,2}$ | $\cdots$ | $e_{2,n}$ | $\cdots$ | $v_{n}$ | $e_{n,1}$ | $e_{n,2}$ | $\cdots$ | $e_{n,n}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$1$ | $R_{v}$ | $\uparrow$ |  |  | $\cdots$ |  |  |  |  | $\cdots$ |  | $\cdots$ |  |  |  |  |
$R_{e}$ |  | $\uparrow$ |  | $\cdots$ |  |  | $\uparrow$ |  | $\cdots$ |  | $\cdots$ |  | $\uparrow$ |  |  |
$2$ | $R_{v}$ |  |  |  | $\cdots$ |  | $\uparrow$ |  |  | $\cdots$ |  | $\cdots$ |  |  |  |  |
$R_{e}$ |  |  | $\uparrow$ | $\cdots$ |  |  |  | $\uparrow$ | $\cdots$ |  | $\cdots$ |  |  | $\uparrow$ |  |
$\cdots$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
$n$ | $R_{v}$ |  |  |  | $\cdots$ |  |  |  |  | $\cdots$ |  | $\cdots$ | $\uparrow$ |  |  |  |
$R_{e}$ |  |  |  | $\cdots$ | $\uparrow$ |  |  |  | $\cdots$ | $\uparrow$ | $\cdots$ |  |  |  |  | $\uparrow$

After the marking is maintained on the $j$-th iteration, our next job is to
check whether $j$ is a reachable vertex. This can be done by checking if there
exists any ticked (with $\checkmark$) vertex number $v_{i}$ that has an out-
going edge to $j$ (i.e. $v_{i,j}=j$), if yes then tick vertex number $v_{j}$.
Note that we only need constant steps as all relevant variables are already
marked. After $n$ iterations, the program terminates and we show that all
reachable vertex have been ticked.

The proof of correctness is by an induction of this statement: after $j$-th
iteration, all reachable vertices $i\leq j$ are all ticked. The base case of
$j=1$ is trivial because $1$ is reachable if and only if $1\in S$ (which holds
if and only if vertex $1$ is already ticked at the beginning). For the
inductive step, suppose the statement is already correct for $j=k$. The
$k+1$-th iteration checks whether vertex $k+1$ is reachable and that is true
iff there exists a reachable vertex $i$ going to $k+1$ i.e. $v_{i,k+1}=k+1$.
As the graph is SDAG, $i$ must be less than $k+1$. As we already correctly
ticked the reachable vertices up to vertex number $k$, therefore the
reachability of $k+1$ can be fully checked. ∎

The upper bound of the multi-source connectivity problem is almost tight. In
fact, it is match with the lower bound if the graph is a SDAG by the following
theorem.

######  Theorem 5.11.

The lower bound of multi-source connectivity of a directed graph with $n$
vertices is $\text{DAL}[\Omega(n)]$.

###### Proof.

Assume that $n$ is even so we can split the vertices into two equal groups:
$\\{1,2,\cdots,\frac{n}{2}\\}$ and $\\{\frac{n}{2}+1,\cdots,n\\}$. Let us
construct an input graph such that $(i,j)\in E$ iff $i+\frac{n}{2}=j$ and
$S\subseteq\\{1,2,\cdots,\frac{n}{2}\\}$ i.e. the sources are the subset of
the first group. By this construction, we reduce the problem to a duplication
problem: the algorithm must tick the vertices in the second group such that
they are equal to the ticks of the first group. It is also equivalent to
transforming $w$ to $ww$ where $|w|=\frac{n}{2}$. Between both $w$, at least
$\frac{n}{2}$ bits has to be transmitted as it carries the copy of $w$. Thus
by its crossing sequence, the lower bound will be $\Omega(n)$-DAL-computation.
∎

###  5.4 Sorting in DARM

We also have a nice result in sorting where the solution is optimal.

######  Theorem 5.12.

Given $n$ many $m$-digits numbers as an input, sorting those $n$ numbers can
be solved in $DAL[nm]$. Moreover, it is also matched with the lower bound.

###### Proof.

We can directly implement parallel neighbour-sort by Habermann [15]. The
algorithm runs in $n$ rounds. In odd-numbered round, $\lfloor n/2\rfloor$
pairs are set: $(1,2),(3,4),\cdots$; while in even-numbered round,
$\lfloor(n-1)/2\rfloor$ pairs are set: $(2,3),(4,5),\cdots$. These pairs
denote the two index numbers to be compared and those two numbers will be
swapped if the former is larger. In a single round, all comparisons and
swappings can be done in parallel and need $\mathcal{O}(m)$ steps since each
number has $m$ digits. Thus, the total complexity time is $DAL[nm]$.

For lower bound, an input can be generated by putting $n/2$ large numbers in
the first half and smaller numbers in the rest last half of the input. To sort
this requires transferring all numbers in the first half to the last half and
vice versa. Therefore, at least $nm/2$ bits of information have to be
transmitted between the middle point. As crossing sequences are only
determined up to a constant factor, thus the length of the crossing sequence
between both halves will be in length $\Omega(nm)$, hence the lower bound is
attained. ∎

##  6 Key Results in NARM

In the same spirit of DARM, this section presents the relationship between
NARM and standard Turing machine complexity classes followed by membership of
some interesting languages in NAL class.

###  6.1 Nondeterministic Turing Machine, Regularity, and NONPALINDROME

We first start our result with the following theorem.

######  Theorem 6.1.

$\text{NAL}[f(n)]\subseteq\text{NSPACE}[f(n)]\cap\text{NTIME}[(n+f(n))f(n)]$.

###### Proof.

Consider the space-time diagram of the register content in
$\text{NARM}\leavevmode\nobreak\ M=\langle\Gamma,\Sigma,G\rangle$. Let $l$ be
the maximum length of a string in the computation of $G$ automata until it
halts. The input is padded with $\\#$’s such that the length from first to
last computation is always $l$. Let $r_{i}$ be the $i$-th symbol of the
register.

step | $r_{1}$ | $r_{2}$ | … | $r_{l}$
---|---|---|---|---
1 | $r_{1}^{(1)}$ | $r_{2}^{(1)}$ | … | $r_{l}^{(1)}$
2 | $r_{1}^{(2)}$ | $r_{2}^{(2)}$ | … | $r_{l}^{(2)}$
… | … | … | … | …
$cf(n)$ | $x_{1}^{(cf(n))}$ | $r_{2}^{(cf(n))}$ | … | $r_{l}^{(cf(n))}$

Note that it suffices to keep track of the state of a deterministic finite
automaton accepting the automatic relation step updates in order to simulate
it. Hence, the Turing machine simply maintains a column of states. These
states correspond to the states of the automata recognizing the automatic step
updates. The Turing machine then guesses the contents column by column and
simulates the automata to process these contents. At the end of all $l$
columns, it then verifies that all step updates are valid. The total amount of
space used is simply $\mathcal{O}(f(n))$. Hence, we have
$\text{NAL}[f(n)]\subseteq\text{NSPACE}[f(n)]$.

Secondly, in each bounded automatic relation step, the length of the string is
allowed to increase by at most a constant $c$. Hence, the length of the string
after $\mathcal{O}(f(n))$ steps is bounded by $\mathcal{O}(n+f(n))$. By
Theorem 3.10, the execution of automatic relations can be simulated by a
nondeterministic Turing Machine in $\mathcal{O}((n+f(n))f(n))$ steps. Hence,
$\text{NAL}[f(n)]\subseteq\text{NTIME}[(n+f(n))f(n)]$. ∎

######  Corollary 6.2.

$\text{NAL}[poly(n)]=\text{NP}$.

######  Corollary 6.3.

For $f(n)=\Omega(n)$, under the assumption that
$\text{NTIME}[(n+f(n))f(n)]\not\supseteq\text{NSPACE}[f(n$
$)],\text{NAL}[f(n)]\subset\text{NSPACE}[f(n)]$.

Next, we show several results on a NARM with a smaller number of computations.
Note that an automatic relation step is an NFA which can be constructed as a
DFA but with exponential-larger size. Therefore, we can directly use the proof
in Theorem 5.1 to show that $\text{NAL}[1]=\text{DAL}[1]=Regular$. However, a
better bound can be achieved.

######  Theorem 6.4.

$\text{NAL}[o(\log n)]=Regular$, moreover if NARM measures the time complexity
in a weak-measure i.e. $\max\\{\min\\{\text{acceptance time
for}\leavevmode\nobreak\ x\leavevmode\nobreak\ \text{on a nondeterministic
path}\\}:|x|=n,x\in L\\}$ then $\text{NAL}[o(\log\log n)]=Regular$.

###### Proof.

In Subsection 5.1 we show that the length of a $\text{DAL}[f(n)]$-computation
gives a crossing sequence of length $\mathcal{O}(f(n))$. This result can be
extended to NARM in a similar manner as a bounded automatic relation can be
simulated by a double-pass of a nondeterministic one-tape Turing machine. Thus
an $f(n)$-steps NARM produces an $f(n)$ crossing sequence length accepting
computation on the best possible run. Szepietowski [42] and Pighizzini [34]
show that if a nondeterministic one-tape Turing machine uses a crossing
sequences of length at most $o(\log n)$ then it accepts regular language. This
result allows to translate that NARM in $o(\log n)$ steps accept regular
language too.

Moreover, Pighizzini [34] also shows that in a weak-measure where the
acceptance of a string is only measured to its shortest computation path, then
the previous bound goes down to $o(\log\log n)$. Their proof is based on
accepting a unary string of length $n$ where the smallest integer non dividing
$n$ is not a power of $2$, by guessing $s$ and $t$ such that
$2^{s}<t<2^{s+1}$, $n\mod 2^{s}=0$, and $n\mod t\neq 0$. This translates well
for NARM in a weak-measure by guessing a string where every $t$-th symbol is a
$2$ and in between are symbols $1$, for some non-negative integer $t$ —
allowing NARM to check the divisibility of $t$. ∎

The next lemma nicely follows the hierarchy that in $O(\log n)$ steps, NARM
may recognize a non-regular language.

######  Definition 6.5 (PALINDROME and NONPALINDROME).

PALINDROME = $\\{x\in\\{0,1\\}^{*}:\forall i,x_{i}$ $=x_{|x|-i+1}\\}$ while
NONPALINDROME = $\\{0,1\\}^{*}\setminus PALINDROME$.

######  Theorem 6.6 (Bārzdiņš [3], Hennie [18], Rabin [35]).

PALINDROME cannot be accepted on a nondeterministic one-tape Turing Machine in
$o(n^{2})$ steps.

The subsequent corollary follows from Theorems 6.1 and 6.6.

######  Corollary 6.7.

PALINDROME $\notin\text{NAL}[o(n)]$.

######  Lemma 6.8.

NONPALINDROME $\in\text{NAL}[\log n]$.

###### Proof.

The idea is the following. After $r_{1}$ reads an input $w$ where $|w|=n$,
$r_{2}$ guesses (i.e. nondeterministically chooses) a string $0^{i}\cdot
3\cdot 1^{j}\cdot 3\cdot 2^{i}$ where $2i+j+2=n$ such that the symbols of $w$
at positions $i+1$ and $n-i$ are different, thus $w$ is nonpalindrome. As
$r_{2}$ can only guess in form of $0^{*}31^{*}32^{*}$ with an automatic
relation, our task is then to verify that the length is exactly $n$ and the
number of symbol ‘0’ and ‘2’ are equal. Verifying that the length is exactly
$n$ is trivial by comparing $r_{1}$ and $r_{2}$ (reject if one string is
longer/shorter). To verify that the occurrences of ‘0’s and ‘2’s are the same,
while there exists symbol ‘0’ or ‘2’, repeat the following rounds:

  1. 1.

If the parities of ‘0’s and ‘2’s are different, then reject.

  2. 2.

Else, modify the $1,3,5,\cdots$-th occurrences of ‘0’ to ‘1’, and modify the
$1,3,5,\cdots$-th occurrences of ‘2’ to ‘1’.

If the iteration terminates without reject, both digits are disappearing at
the same time and proven to be always equal. The final step is then to verify
that the symbols on $r_{1}$ in the same positions of both ‘3’s on $r_{2}$ are
different, thus a nonpalindrome. Note that both the number of ‘0’s and ‘2’s
are halved in each round and therefore the runtime of the verification is
logarithmic in the length of the input. ∎

Finally, we wrap up this subsection with the following result.

######  Theorem 6.9.

$\text{NAL}[\log n]\subset\text{NLOGSPACE}\subseteq P$.

###### Proof.

Combining Corollary 6.7 and Lemma 6.8, $\text{NAL}[\log n]$ is not closed
under complement, whereas NLOGSPACE is closed under complement [22][41]. From
Theorem 6.1, we also have $\text{NAL}[\log n]\subseteq\text{NLOGSPACE}$.
Hence, $\text{NAL}[\log n]\subset\text{NLOGSPACE}$. ∎

###  6.2 3SAT and Context-free Languages in NARM

We employ the following binary encoding of 3SAT as an input.

######  Definition 6.10 (Binary Encoding of 3SAT).

Consider a binary encoding of 3SAT where a variable $x_{i}$ is represented by
a binary number $i$. We use $s_{i}\in\\{+,-\\}$ to represent whether the
$i$-th literal is positive or negative such that a clause $(x_{i}\lor\lnot
x_{j}\lor\lnot x_{k})$ is represented by $i+\leavevmode\nobreak\
|\leavevmode\nobreak\ j-\leavevmode\nobreak\ |\leavevmode\nobreak\ k-$.
Different clauses are separated by symbol “$\&$”.

Let $n$ be the length of the formula (and not the number of variables). We can
show a nice result that in unary encoding $\text{3SAT}\in\text{NAL}[n]$.
However, using a similar technique, we can actually show that
$\text{3SAT}\in\text{NAL}[\frac{n}{\log n}]$ if it is in binary encoding. The
catch is that an additional small constraint has to be imposed: if there are
$k$ variables then the first $k$ binary numbers (i.e. $1$ to $k$) must be used
as their namings and are in the same length $O(\log k)$. The following is the
proof.

######  Theorem 6.11.

In a nice format, $\text{3SAT}\in\text{NAL}[\frac{n}{\log n}]$ where $n$ is
the length of the 3SAT formula.

###### Proof.

After reading the input of formula $f$, assign a register $r_{c}$ as a
counter. Register $r_{c}$ will copy the input $f$ but every variables in it is
replaced by $0$. Then the following iteration is performed:

  1. 1.

Increment every variables in $r_{c}$.

  2. 2.

Nondeterministically choose a truth value $T$ or $F$.

  3. 3.

For each variable in $f$ which is equal to the one in $r_{c}$, assign above
truth value to it.

  4. 4.

If every variables in $f$ has been assigned, terminate the iteration; else
repeat.

The idea is that in the $i$-th iteration, the algorithm will assign the $i$-th
variable a same truth value. Each operations in the iterations such as
increment and assigning a truth value can be done in constant steps as it is
possible update all variables both in $r_{c}$ and $f$ in parallel. After the
iteration terminates, every variables has been assigned and a single step can
be performed to check the satisfiability of the $f$.

Note that the algorithm runs in $\mathcal{O}(k)$ steps where $k$ is the number
of iterations. The number of iterations is equal to the number of variables if
the first $k$ binary numbers are used as the naming. As each variable is
written in the same length of $\mathcal{O}(\log k)$ therefore there must be at
most $\mathcal{O}(\frac{n}{\log n})$ many variables, thus the runtime of the
algorithm is $\text{NAL}[\frac{n}{\log n}]$. ∎

Beside 3SAT, we also have a result in context-free languages.

######  Theorem 6.12.

Context-free languages and their closure under union, intersection,
concatenation, and Kleene star are in $\text{NAL}[n]$; moreover, it is also
optimal.

###### Proof.

The upper bound comes from a direct translation from grammars in Greibach
normal form [14]. Meanwhile, the lower bound follows from Corollary 6.7. As
PALINDROME is a context-free language, there is no $\text{NAL}[o(n)]$
algorithm to recognize the membership for context-free language. ∎

##  7 Advanced Types of ARM

In this last section, we further extend the types of ARM by allowing
unboundedness of automatic relations, a booster operation to generate padding,
and also a concept similar to Alternating Turing machines.

###  7.1 Unbounded Nondeterministic Automatic Register Machine

This type of machine is similar to NARM but it uses unbounded automatic
relations instead.

######  Definition 7.1 (Unbounded Nondeterministic Automatic Register
Machine).

An Unbounded Nondeterministic Automatic Register Machine (UNARM) is an
Automatic Register Machine $M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where $Op$
is restricted to unbounded automatic relations. Alternatively, a UNARM is an
Automatic Register Machine $M=\langle\Gamma,\Sigma,G\rangle$ where $G$ is an
unbounded automatic relation.

######  Definition 7.2 (Unbounded Nondeterministic Automatic Register Machine
Complexity).

Let $f(n)$ be any function in the input size $n$. UNAL[$f(n)$] is the class of
languages accepted by UNARM in no more than $\mathcal{O}(f(n))$ steps.

As unbounded automatic relation has the ability to guess a huge witness in one
step, it may recognize a larger complexity class compared to NARM as shown by
the following result.

######  Theorem 7.3.

For $f(n)=\Omega(n)$, $\text{NSPACE}[f(n)]\subseteq\text{UNAL}[f(n)]$.

###### Proof.

Consider a one-tape nondeterministic Turing Machine with $cf(n)$ cells for
some constant $c$. Let $C_{i}$ denote the string on the tape of Turing Machine
along with the head location (marked on the string) and state of the machine
at the $i$-th step, padded with ‘#’ such that $|C_{i}|=cf(n)$. Let $|$ be a
new symbol not in the alphabet of the Turing Machine. Now UNARM
nondeterministically guesses

$r=\begin{array}[]{c | c | c | c | c | c}C_{1}&C_{2}&\ldots&C_{i}&\ldots&C_{t-1}\\\ C_{2}&C_{3}&\ldots&C_{i+1}&\ldots&C_{t}\end{array}$

and verifies in one step that $C_{1}$ is the input (with starting state and
the head location marked the leftmost symbol), $C_{t}$ is in accepting state,
and $C_{i}$ to $C_{i+1}$ is a valid transition in each column separated by
$|$. In the next $cf(n)$ steps, it verifies that $\forall i,C_{i}$ in the
first row is the same as $C_{i}$ in the second row. Let $m=cf(n)$, expanding
$C_{i}$ into $C_{i,1}C_{i,2}\ldots C_{i,m}$:

$r=\begin{array}[]{c | c | c | c}C_{1,1}C_{1,2}C_{1,3}\ldots C_{1,m}&C_{2,1}C_{2,2}C_{2,3}\ldots C_{2,m}&C_{3,1}C_{3,2}C_{3,3}\ldots C_{3,m}&\ldots\\\ C_{2,1}C_{2,2}C_{2,3}\ldots C_{2,m}&C_{3,1}C_{3,2}C_{3,3}\ldots C_{3,m}&C_{4,1}C_{4,2}C_{4,3}\ldots C_{3,m}&\ldots\end{array}$

In the $j$-th step, more specifically, it verifies that $\forall i$, $C_{i,j}$
from the second row of the $(i-1)$-th block is the same as $C_{i,j}$ from the
first row of the $i$-th block. It also marks off $C_{i,j}$ with the marker
symbol $@$ after checking. The $@$ will help the automatic relation to
identify which is the $j$-th symbol: the $j$-th symbol is exactly the first
non $@$ symbol in each block.

After one step:

$r=\begin{array}[]{c | c | c | c}\ @\ C_{1,2}C_{1,3}\ldots C_{1,m}&\ @\ C_{2,2}C_{2,3}\ldots C_{2,m}&\ @\ C_{3,2}C_{3,3}\ldots C_{3,m}&\ldots\\\ \ @\ C_{2,2}C_{2,3}\ldots C_{2,m}&\ @\ C_{3,2}C_{3,3}\ldots C_{3,m}&\ @\ C_{4,2}C_{4,3}\ldots C_{3,m}&\ldots\end{array}$

After two steps:

$r=\begin{array}[]{c | c | c | c}\ @\ \ @\ C_{1,3}\ldots C_{1,m}&\ @\ \ @\ C_{2,3}\ldots C_{2,m}&\ @\ \ @\ C_{3,3}\ldots C_{3,m}&\ldots\\\ \ @\ \ @\ C_{2,3}\ldots C_{2,m}&\ @\ \ @\ C_{3,3}\ldots C_{3,m}&\ @\ \ @\ C_{4,3}\ldots C_{3,m}&\ldots\end{array}$

Lastly, it also verifies all $C_{i}$ are having the same length, i.e.
$|C_{i}|=m$, and it can be done with the help of a counter (for example, in
another register). Hence, we have
$\text{NSPACE}[f(n)]\subseteq\text{UNAL}[f(n)]$ for $f=\Omega(n)$. Note that
the condition $f(n)=\Omega(n)$ is necessary as the simulation needs to verify
that the correct input are used in the computation which takes $\Omega(n)$
steps. ∎

######  Corollary 7.4.

$\text{UNAL}[poly(n)]=\text{PSPACE}$.

######  Remark.

While it is clear that $\text{NP}\subseteq\text{PSPACE}$, the
equality/inequality part is still not known thus it is also unclear whether
polynomial time models with bounded and unbounded automatic relations as
operations are actually the same or different as a decision problem. As
mentioned before, if both act as functions instead then the two concepts
differ as a nondeterministic bounded automatic function can only have
polynomial-sized output while the unbounded one can have exponential-sized
output.

###  7.2 Polynomial-Size and Exponential-Size Padded Automatic Register
Machines

Automatic functions and bounded automatic relations have a nice property that
the length of the string only increases by a constant. As unboundedness
introduces more power by its ability to guess a huge witness, we are curious
whether the length of the string is what matters. What happens if we are still
using automatic functions and bounded automatic relations yet we initially
give the ”working space” big enough? Here we define such models with a booster
operation.

######  Definition 7.5 (Polynomial-Size Padded Automatic Register Machine).

A Polynomial-Size Padde-d Automatic Register Machine (PARM) is an ARM
$M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where instead of operation
$read(R_{i})$, there is an operation $read\\_and\\_boost(R_{i},R_{j},p)$ where
$R_{i},R_{j}\in R$ and $p$ is a polynomial. This operation will:

  1. 1.

Assign the input string to register $R_{i}$.

  2. 2.

Let $n$ be the input length, then a padding string $0^{*}$ is generated in an
adversarial way such that its length is at least $p(n)$ and then is assigned
to $R_{j}$.

######  Definition 7.6 (Exponential-Size Padded Automatic Register Machine).

An Exponential-Size Pad-ded Automatic Register Machine (ExpARM) is an ARM
$M=\langle\Gamma,\Sigma,R,Op,P\rangle$ where instead of operation
$read(R_{i})$, there is an operation $read\\_and\\_boost(R_{i},R_{j},p,q)$
where $R_{i},R_{j}\in R$ and $p,q$ are polynomials. This operation will:

  1. 1.

Assign the input string to register $R_{i}$.

  2. 2.

Let $n$ be the input length, then a padding string $0^{*}$ is generated in an
adversarial way such that its length is at least $2^{p(n)}\cdot q(n)$ and then
is assigned to $R_{j}$.

With PARM model, a working space with polynomial-size larger than the original
length of the input is generated and it can only be done once when reading the
input. Any polynomial $p$ can be chosen by the designer of the algorithm but,
due to the adversary nature of the booster step, it does not guarantee that
the padding string has exactly $p(n)$ symbols — it only guarantees that there
are at least $p(n)$ symbols. The intention is that in $\mathcal{O}(1)$ steps
only automatic functions and relations can be computed, i.e. it is not
possible to have a function $h:x\rightarrow 0^{p|x|}$, thus a booster step is
solely used to enlarge the working space. Note that one can however in
$\mathcal{O}(\log n)$ steps trims the booster string to get the exact length
of $p(n)$. This concept also applies for ExpARM model where the padding length
will be at least $2^{p(n)}\cdot q(n)$ and all other properties can be chosen
adversially.

######  Remark.

As any upper bound of PARM and ExpARM are also welcome, one can modify the
boosting operation to $read\\_and\\_boost(R_{i},R_{j},c)$ then just choose a
constant $c$ such that the padding string has to have at least length $n^{c}$
in PARM and $2^{n^{c}+c}$ in ExpARM.

We then have the following definitions for the complexity.

######  Definition 7.7 (Polynomial-Size Padded Deterministic Automatic
Register Machine Complexity).

Let $f(n)$ be any function in the input size $n$. $\text{PDAL}[f(n)]$ is the
class of languages accepted by deterministic PARM in $\mathcal{O}(f(n))$. Here
the PARM has to finish in $\mathcal{O}(f(n))$ steps no matter what length of
the padding string a booster step generate.

######  Definition 7.8 (Exponential-Size Padded Deterministic Automatic
Register Machine Complexity).

Let $f(n)$ be any function in the input size $n$. $\text{ExpDAL}[f(n)]$ is the
class of languages accepted by deterministic ExpARM in $\mathcal{O}(f(n))$.
Here the ExpARM has to finish in $\mathcal{O}(f(n))$ steps no matter what
length of the padding string a booster step generate.

It turns out allowing a large working space gives the machine more power as
shown by the following result.

######  Theorem 7.9.

The problem $QSAT$ is in $ExpDAL[n]$.

###### Proof.

Given an input $x$ which is a QSAT-formula of length $n$, let $m$ be the
number of variables in it. One assumes the following coding and only in that
case the number returned by the algorithm needs to be correct:

  1. 1.

There is a prefix of the variables saying whether they are universal or
existential quantified and the variables are ordered as numbers
$m-1,m-2,\ldots,2,1,0$ in this prefix;

  2. 2.

Each variable name has $k$ binary digits and $m\leq 2^{k}<2m$;

  3. 3.

The quantified part is in square brackets and within this, the variables are
either prefixed by + or by - to indicate that they are non-negated or negated
in the clause, respectively, and they have furthermore an underscore `_` after
the variable to record the value and they are separated by commas inside the
clause and clauses are separated by semicolons;

  4. 4.

Every number $0,1,\ldots,m-1$ (in binary) occurs as a variable name somewhere
in the inner part of the formula;

  5. 5.

The instance is redundance-free, that is, no clause $\alpha$ logically implies
a clause $\beta$.

For $m=3$, an example of a correct coding is the following:

$\exists 10\forall 01\exists 00[+00\\_,+01\\_,+10\\_;-01\\_,-10\\_]$

and it says that variable number 2 is existentially quantified followed by
variable 1 being universally quantified followed by variable number $0$ being
existentially quantified such that one of the variables is positive and one of
the variables number 1 and number 2 is negative. The variable order is in each
quantification from top to bottom and that exactly the variables are
quantified which occur inside the formula. If this is not the case then the
algorithm can return any value. Now the algorithm is as follows:

  1. 1.

Read input $x$ and let $n$ denote its length;

  2. 2.

One guesses (i.e. uses booster step) a string $y$ of length at least
$2^{n+2}\cdot n$ and in the next step one makes all symbols in $y$ to $3$;

  3. 3.

While the position of the second $3$ in $y$ is not at least two symbols after
the end of $x$ do Begin Change in $y$ the second, fourth, sixth, $\ldots$
occurrence of $3$ to $5$ End;

  4. 4.

Make the symbol after the last occurrence of $3$ to $4$ and delete everything
afterwards (this can either increase the length of $y$ by $1$ or leave it as
it is or make $y$ shorter);

  5. 5.

For all symbols $a$ between the two square brackets in $x$ (which might be
read out by using a marker in the loop) and then for $a$=“.” Do Begin For each
occurrence of a $3$ in $y$ go to the first $5$ after it and replace it by $a$
End;

  6. 6.

Make a copy $z$ of $y$; Replace all $1$ in $z$ by $0$;

  7. 7.

If there are still some variable names which do not have an $s$ or $u$ after
them and either there is no position where the variable names in $y$ and $z$
coincide and or there is a position where the variable name in $z$ consists
only of $1$ then return the value $0$;

  8. 8.

If there is no variable name in $y$ which is not followed by either $s$ or $u$
then go to line 13;

  9. 9.

Go over $y$ and $z$ in parallel and with a bit $b$ having value $u$ at the
beginning such that whenever one passes a $3$ in $y$ then one swaps $b$ from
$u$ to $s$ or from $s$ to $u$ and whenever one passes a variable name which
coincides in $y$ and $z$ then one replaces in $y$ the $\\_$ after it by the
value of $b$;

  10. 10.

Go over $y$ and change the second, fourth, sixth, $\ldots$ $3$ to $2$;

  11. 11.

Go over $z$ and increment all binary variable names by $1$ (an automatic
function can do this);

  12. 12.

Go to line 7;

  13. 13.

In $y$, make the symbol after the second occurrence of a $3$ to $4$ (this $3$
sits after the first instance where all variables are evaluated to $s$) and
discard all symbols after this $4$;

  14. 14.

Now replace in $y$ all $2$ by $3$;

  15. 15.

For each instance in $y$ (where an “instance” in $y$ refers to the segment
between two consecutive occurrences of $3$), if every clause contains either a
substring $+\\{0,1\\}^{*}s$ or a substring $-\\{0,1\\}^{*}u$ then all clauses
are satisfied and the first $5$ after the dot at the end of the instance is
made an $s$ else the instance is not satisfied and the first $5$ after the dot
at the end of the instance is made a $u$;

  16. 16.

Go backward through the quantifier prefix of $x$ (using some marker) until
again $y$ has only two $3$s Do Begin

  17. 17.

For each subsequent two occurrences of $s,u$ after a dot do Begin
if the quantifier is universal and both are $s$ then replace the first by $5$
and the second one by $s$ else
if the quantifier is universal and at least one is $u$ then replace the first
by $5$ and the second by $u$ else
if the quantifier is existential and both are $u$ then replace the first by
$5$ and the second by $u$ else
if the quantifier is existential and at least one is $s$ then replace the
first by $5$ and the second by $s$ End End;

  18. 18.

Now there is only one $s$ or $u$ left after a dot and this is the result of
the formula ($s$ is satisfied and $u$ is unsatisfied).

Here are some explanations. First note that functions which are computed by
one-way Turing machines going either over one input alone or over several
inputs synchronously and doing changes on the spot are automatic and all
automatic functions in this algorithm are of this type; for line 11 the Turing
machine has to go backward for easily seen to be deterministic. Actually
nondeterministic Turing machines going forward can also do the job. The
characterisation [7] says that the Turing machine processing the variable $y$
(or $y$ and $z$ in parallel) for an automatic function can change the
direction constantly many times, but here the easier one-directional pass is
sufficient for all automatic functions; when comparing the variable names in
$y$ and $z$, the Turing machine goes over the word by accessing in both
variables the same position in each step.

  * 1.

In line 2, $4n$ is a safe upper bound of the length of copy of the inner part
of the quantified variable plus some additional space and $n$ is a safe upper
bound on the number of variables, thus the length reserved in $y$ is
sufficient (one cannot fix the length exactly but only get it above the bound
for avoiding of coding).

  * 2.

Line 3 thins out symbols $3$ in $y$ by always converting every second to $5$
(what an automatic function can do) until the gap between the first $3$ (at
the beginning fo the word) and the second $3$ is longer than the length of
$x$, this are $O(\log n)$ many runs through the body of the loop which is
implemented by one automatic function.

  * 3.

Line 4 rectifies the end of the word and removes trailing $5$s and adds a $4$
as an end marker.

  * 4.

Line 5 copies in $O(n)$ rounds the inner part of the formula into $y$ starting
after each $3$ (there is enough space for this) by always for each symbol $a$
copied replacing the first $5$ after each $3$ by $a$. Each copying of a symbol
$a$ into all these places can be done by invoking one automatic function to
update $y$ and thus in overall $O(n)$ steps the copying can be done.

  * 5.

Line 6 copies $y$ into a new variable $z$ and makes in $z$ all variable names
to $00\ldots 0$ by making all $1$ to $0$.

  * 6.

Lines 7–12 are one big loop in order to set in $y$ all values of the variables
in a consistent manner with the additional property that all $2^{m}$ ways of
putting the variable values are covered in an instance.

  * 7.

Line 7 causes early termination of the algorithm in the case that the names of
the used variables are not contiguous.

  * 8.

Line 8 leaves the loop in the case that all variables are assigned $s$ (for
satisfied or true) or $u$ (for unsatisfied or false).

  * 9.

Line 9 and line 10 make the values of the $\ell$-th variable to change every
$2^{\ell}$ instances, initially the zeroth variables changes from every
instance to the next between $u$ and $s$ and subsequently each second, fourth,
sixth, $\ldots$ $3$ becomes a $2$ to increase the number of instances with the
same value from $2^{\ell}$ to $2^{\ell+1}$ before processing the $\ell$+first
variable.

  * 10.

Before going into the next iteration of the loop, all variable names in $z$
are increased from $\ell$ to $\ell+1$.

  * 11.

Line 13 is just to make sure that exactly $2^{m}$ instances will survive and
these have the variable values $(u,\ldots,u,u)$, $(u,\ldots,u,s)$,
$(u,\ldots,s,u)$, $(u,\ldots,s,s)$, $\ldots$, $(s,\ldots,s,s)$ and a one-way
Turing machine going over the word $y$ can detect the position of the instance
where all variables are $s$ and change the symbol after the $3$ after that
instance to $4$ and discard the symbols after that; thus this modification can
be computed by an automatic function.

  * 12.

Line 14 is only a step needed to make the separation by two neighbouring
instances always by a 3 and not by a 3 or a 2. This eases the writing of the
algorithm, but has no further significance.

  * 13.

For each instance in $y$, a one-way Turing machine can check whether all
literals with value $s,u$ of the variable are set such that the instance is
satisfied, if so then the instance gets after its final dot the value $s$ else
the instance gets after its final dot the value $u$. This is done in one scan
for all instances in $y$.

  * 14.

The loop in Lines 16 and 17 goes backwards over the quantifiers in $x$ and for
each quantifier, it identifies the still active values of blocks of instances
in the form $.s$ and $.u$ after the instance and it evaluates the first and
the second with the result in the second, the third and the fourth with the
result in the fourth, the fifth and the sixth with the result in the sixth and
so on in order to process the currently quantified variable; in the $\ell$-th
round $(\ell$ goes from $0$ to $m-1)$ this loop treats the quantification of
the $\ell$-th variable and takes the result of two neighbouring blocks blocks
of $2^{\ell}$ instances with the $\ell$-th variable being $u$ and $s$
respectively from before and puts the result into the entry for the second of
these blocks while the entry for the first of these blocks get erased. After
doing this for all $m$ variables, one entry for the block of $2^{m}$ instances
remains and this is the result of this loop and value of the QSAT formula.

  * 15.

Line 18 returns this value. Note that the number of rounds in each of the
loops is $O(\log n)$ in the loop of Line 3, $O(n)$ for the loop copying the
formula in all applicable positions in Lines 4–5, number $m$ of variables for
the big loop in lines 7–12, number $m$ of variables for the loop in lines
16–17. Thus the overall amount of operations in the evaluation of the QSAT
formula is $O(n)$; note that $m\leq n$.

This completes the algorithm and its explanations for this proposition. ∎

We also show the connection between ExpARM and UNARM as the following.

######  Theorem 7.10.

$PSPACE=\text{ExpDAL}[poly(n)]=\text{UNAL}[poly(n)]$.

###### Proof.

We first prove $PSPACE\subseteq\text{ExpDAL}[poly(n)]$. Let a problem $R$ in
$PSPACE$ be given which is many-one reduced by a function $f$ in polynomial
time to QSAT where $f$ increases the size of an instance $n^{\prime}$ to at
most $p(n^{\prime})$ for some polynomial $p$. Let an input $x^{\prime}$ of $R$
be given. One generates in padding an input $y$ of length
$2^{p(n^{\prime})+4}\cdot p(n^{\prime})$ and then one translates the instance
$x^{\prime}$ into $x=f(x^{\prime})$ of length $n$ with $n\leq p(n^{\prime})$
in $poly(n^{\prime})$ steps. Afterwards one runs above $QSAT$ algorithm in
$O(n)$ = $O(p(n^{\prime}))$ steps to decide whether $x$ is in $QSAT$, without
loss of generality $f$ produces a formula which satisfies all the constraints
of the above algorithm so that the algorithm is correct. Thus the algorithm is
correct.

Next, we prove that $\text{ExpDAL}[poly(n)]\subseteq\text{UNAL}[poly(n)]$: One
just replaces the step of producing the $y$ by exponential padding having at
least $2^{n^{c}+c}$ symbols (where $c$ is a sufficiently large constant) by an
unrestricted guessing of the $y$ and then one makes all bits in $y$ to $1$ and
then one verifies that $n^{c}+c$ many steps of the algorithm which converts in
each step half of the $1$s to $0$s does not produce a $0$ only word. Then the
word is long enough and one can proceed with the previous ExpDAL$[poly(n)]$
algorithm. By Corollary 7.4, we know that $\text{UNAL}[poly(n)]=PSPACE$
therefore the equality is established. ∎

We move on to the result in polynomial-size padding.

######  Theorem 7.11.

Let $c$ be a constant. Solving $(c\log n)$-variable 3SAT is in
$PDAL[\mathrm{polylog}(n)]$.

###### Proof.

Without loss of generality the input is given as a pair $(x,y^{\prime})$ where
$y^{\prime}$ has length $n^{c+2}$ and $x$ is a 3SAT formula (all variables
existentially quantified) written in the conventions of Theorem 7.9. In
particular the variables are written in binary and the instance $x$ is
redundance-free. Thus the instance $x$ has at most length $10(c\log n\log\log
n)^{3}+c^{\prime}$ for some constant $c^{\prime}$ and the factor $10$ is
larger than the expected factor $8$ to absorb constant add-ons per literal and
the quantifier prefix. If $x$ violates this length bound then one can return
the value $0$, as the input is not in adequate form.

Note that $n$ can be computed from $y^{\prime}$ in $\log(n)$ rounds. The
computation and checking of the length-bound can be done in polylogarithmic
many steps. Furthermore, one can do a padding using that the $y$ guessed must
have $2^{c\log(n)}$ instances of length $|x|$ (which is polylogarithmic and
thus shorter than n) so that $n^{c+2}$ is a save lower bound for the length of
the padding parameter. The algorithm of Theorem 7.9 can now run with $x$ and
$y$ using $|y|\geq 2^{m}\cdot|x|\cdot 4$ and it needs $O(|x|)$ steps where
$|x|\leq 10(\log n\cdot c)^{3}+c^{\prime}$. Thus the overall amount of steps
done is polylogarithmic in $n$. ∎

Lastly, we prove that $\text{PDAL}[o(n)]\neq\text{DAL}[o(n)]$ if the following
hypothesis is true.

######  Hypothesis 7.12 (Exponential Time Hypothesis [23]).

Exponential Time Hypothesis (ETH) states that solving an $h$-variable 3SAT
instance needs time $\Omega(2^{\delta h})$ for some $\delta>0$.

######  Theorem 7.13.

If ETH is true then $\text{PDAL}[o(n)]\neq\text{DAL}[o(n)]$.

###### Proof.

Let $h=c\log n$ such that $c\delta>2$. It follows from ETH that solving the
$h$-variable 3SAT needs $\Omega(2^{c\delta\log n})$. As we set $c\delta>2$
thus the lower bound will be $\Omega(n^{2})$. Suppose there is an algorithm in
DARM solving it in $\text{DAL}[o(n)]$. By Theorem 3.9, such algorithm can be
translated to a Turing machine algorithm which runs in $o(n^{2})$ thus we get
a contradiction. It is clear that the problem can be solved in
$\text{PDAL}[o(n)]$ by Theorem 7.11 therefore
$\text{PDAL}[o(n)]\neq\text{DAL}[o(n)]$. ∎

###  7.3 Alternating Automatic Register Machine

Alternating Turing machine is formulated by Chandra, Kozen and Stockmeyer [9]
to generalize the concept of nondeterminism. We bring such notion of
alternation to ARM called Alternating Automatic Register Machine (AARM) and
have defined and investigated the model in another work [12]. We denote AARM
complexity by AAL and its polynomial-size padded version by PAAL. The
important findings of AARM are the following:

  1. 1.

$\bigcup_{k}\text{AAL}[n^{k}]=\text{PSPACE}$.

  2. 2.

$\text{AAL}[1]=\textit{Regular}$, while there is already an NP-complete
problem in $\text{AAL}[\log^{*}n]$.

  3. 3.

$\text{PH}\subseteq\text{PAAL}[\log^{*}n]\subseteq\text{PSPACE}$.

##  8 Conclusion

This paper introduced and studied several variants of register machines that
employ automatic functions as primitive steps. The first, known as a
Deterministic Automatic Register Machine (DARM), is provably more
computationally powerful than conventional register machines. For example, it
was shown that any graph problem with $n$ vertices whose solution relies on
Breadth-First-Search (BFS) can be solved by a DARM in $\mathcal{O}(n\log n)$
time; moreover, the multi-source connectivity problem can be solved by a DARM
in $\mathcal{O}(n)$ time. Allowing non-determinism gives rise to a more
powerful type of register machine known as a Non-Deterministic Automatic
Register Machine (NARM). It was shown that the class of context-free languages
can be recognised by a NARM in linear time, an improvement on the quadratic
time complexity of this class for DARMs; furthermore, 3SAT can be recognised
by a NARM in $\mathcal{O}\left(\frac{n}{\log n}\right)$ time when the input
formula is given in a particular format, where $n$ is the length of the input
formula. Finally, we introduced Automatic Register Machines that are given
more “working space” by means of a padding of the input with a string of
$0$’s; a Polynomial-Size Padded Automatic Register Machine (PARM) is provided
with a polynomial-size padding of the input while an Exponential-Size Padded
Automatic Register Machine (ExpARM) is provided with an exponential-size
padding. It turned out that an ExpARM is just as powerful as an unbounded NARM
(unbounded in the sense that during each computation of an automatic relation,
the output can be arbitrarily longer than the input), and both types of
machines can recognise all languages in PSPACE in polynomial time.

It may be natural to draw parallels between the models of computation studied
in the present work and other automata-based machines. In this regard, we
mention one such class of machines: cellular automata. One can show that for
any function $f$, $\text{NAL}[f(n)]$ is characterised by a certain class of
non-deterministic cellular-automata with $\mathcal{O}(n+f(n))$ cells. In
addition, both $\text{DAL}[f(n)]$ and $\text{NAL}[f(n)]$ can be characterised
by tiling systems, though these characterisations are somewhat unnatural. As
such machine comparisons are not the main focus of this work, we omit the
details.

## References

  * [1] Alfred Aho and Jeffrey Ullman.  The Theory of Parsing, Translation, and Compiling.  Prentice-Hall Englewood Cliffs, NJ, 1972.
  * [2] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 2009.
  * [3] Jānis Bārzdiņš.  Complexity of recognition of symmetry on Turing machines.  Problemy Kibernet, 15:245–248, 1965.
  * [4] Henning Bordihn, Henning Fernau, Markus Holzer, Vincenz Manca and Carlos Martín-Vide.  Iterated sequential transducers as language generating devices.  Theoretical Computer Science, 369:67–81, 2006.
  * [5] J. Richard Büchi.  Weak second-order arithmetic and finite automata.  Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6:66–92, 1960.
  * [6] J. Richard Büchi.  On a decision method in restricted second order arithmetic.  In Proceedings of the International Congress on Logic, Methodology and Philosophy of Science, pages 1–11, 1962.
  * [7] John Case, Sanjay Jain, Samuel Seah and Frank Stephan.  Automatic functions, linear time and learning.  In Conference on Computability in Europe, volume 7318, pages 96–106, 2012.
  * [8] John Case, Sanjay Jain, Samuel Seah and Frank Stephan.  Automatic functions, linear time and learning.  Logical Methods in Computer Science, 9(3), 2013.
  * [9] Ashok Chandra, Dexter Kozen and Larry Stockmeyer.  Alternation.  Journal of the Association of Computing Machinery, 28(1):114–133, 1981.
  * [10] Stephen Cook and Robert Reckhow.  Time bounded random access machines.  Journal of Computer and System Sciences, 7(4):354–375, 1973.
  * [11] Robert Floyd and Donald Knuth.  Addition machines.  SIAM Journal on Computing, 19:329–340, 1990.
  * [12] Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Sabili, and Frank Stephan.  Alternating automatic register machines, 2021.  URL: https://arxiv.org/abs/2111.04254.
  * [13] Erich Grädel.  Automatic structures: Twenty years later.  In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, page 21–34, 2020.
  * [14] Sheila Greibach.  A new normal-form theorem for context-free phrase structure grammars.  Journal of the ACM, 12(1):42–52, 1965.
  * [15] Nico Habermann.  Parallel neighbor-sort (or the glory of the induction principle).  Carnegie Mellon University Computer Science Report, Carnegie Mellon University, 1972.
  * [16] Juris Hartmanis and Janos Simon.  On the power of multiplication in random access machines.  In 15th Annual Symposium on Switching and Automata Theory (SWAT 1974), pages 13–23, 1974.
  * [17] Juris Hartmanis and Janos Simon.  On the structure of feasible computations.  In Morris Rubinoff and Marshall C. Yovits, editors, Advances in Computers, volume 14, pages 1–43. Elsevier, 1976.
  * [18] Fred Hennie.  One-tape, off-line Turing machine computations.  Information and Control, 8:553–578, 1965.
  * [19] Bernard R. Hodgson.  On direct products of automaton decidable theories.  Theoretical Computer Science, 19:331–335, 1982.
  * [20] Bernard R. Hodgson.  Décidabilité par automate fini.  Annales des sciences mathématiques du Québec, 7:39–57, 1983\.
  * [21] Bernard R. Hodgson.  Théories décidables par automate fini.  PhD thesis, Université de Montréal, 1976.
  * [22] Neil Immerman.  Nondeterministic space is closed under complementation.  SIAM Journal on Computing, 17:935–938, 1988.
  * [23] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [24] Tadao Kasami.  An efficient recognition and syntax-analysis algorithm for context-free languages.  University of Illinois Coordinated Science Laboratory Report No. R-257, University of Illinois, 1966.
  * [25] Bakhadyr Khoussainov and Mia Minnes.  Three lectures on automatic structures.  In Proceedings of Logic Colloquium 2007, volume 35 of Lecture Notes in Logic, pages 132–176, 2010.
  * [26] Bakhadyr Khoussainov and Anil Nerode.  Automatic presentations of structures.  In International Workshop on Logic and Computational Complexity, volume 960, pages 367–392, 1995.
  * [27] Sambasiva Kosaraju.  Speed of recognition of context-free languages by array automata.  SIAM Journal on Computing, 4(3):331–340, 1975.
  * [28] Martin Kutrib and Andreas Malcher.  On one-way one-bit o(one)-message cellular automata.  Electronic Notes in Theoretical Computer Science, 252:77–91, 2009\.
  * [29] Martin Kutrib and Andreas Malcher.  One-dimensional cellular automaton transducers.  Fundamenta Informaticae, 126:201–224, 2013.
  * [30] Martin Kutrib, Andreas Malcher, Carlo Mereghetti and Beatrice Palano.  Deterministic and nondeterministic iterated uniform finite-state transducers: Computational and descriptional power.  In Beyond the Horizon of Computability, volume 12098, pages 87–99, 2020.
  * [31] Zeyong Li.  Complexity of linear languages and its closures and exploring automatic functions as models of computation.  Undergraduate Research Opportunities Programme (UROP) Project Report, National University of Singapore, 2018/2019.
  * [32] André Nies.  Describing groups.  The Bulletin of Symbolic Logic, 13(3):305–339, 2007.
  * [33] Alexander Okhotin.  Conjunctive and Boolean grammars: The true general case of the context-free grammars.  Computer Science Review, 9:27–59, 2013.
  * [34] Giovanni Pighizzini.  Nondeterministic one-tape off-line turing machines and their time complexity.  Journal of Automata, Languages and Combinatorics, 14(1):107–124, 2009.
  * [35] Michael Rabin.  Real time computation.  Israel Journal of Mathematics, 1:203–211, 1963.
  * [36] Branislav Rovan.  A framework for studying grammars.  In Mathematical Foundations of Computer Science 1981, Štrbstké Pleso, Czechoslovakia, August 31 - September 4, 1981, Proceedings, volume 118, pages 473–482, 1981.
  * [37] Sasha Rubin.  Automata presenting structures: A survey of the finite string case.  The Bulletin of Symbolic Logic, 14(2):169–209, 2008.
  * [38] Arnold Schönhage.  On the power of random access machines.  In Automata, Languages and Programming, 6th Colloquium, Graz, Austria, July 16-20, 1979, Proceedings, volume 71 of Lecture Notes in Computer Science, pages 520–529. Springer, 1979.
  * [39] Samuel Seah.  Turing machines and automatic functions as models of computation.  Master’s thesis, National University of Singapore, 2012.
  * [40] Frank Stephan.  Methods and Theory of Automata and Languages.  School of Computing, National University of Singapore, 2016.
  * [41] Róbert Szelepcsényi.  The method of forced enumeration for nondeterministic automata.  Acta Informatica, 26:279–284, 1988.
  * [42] Andrzej Szepietowski.  Turing machines with sublogarithmic space, volume 843.  Springer Verlag, 1994.
  * [43] Derick Wood.  Iterated a-NGSM maps and $\Gamma$ systems.  Information and Control, 32:1–26, 1976.
  * [44] Daniel Younger.  Recognition and parsing of context-free languages in time $n^{3}$.  Information and Control, 10:189–208, 1967.