11institutetext: Department of Mathematics, National University of Singapore,
10 Lower Kent Ridge Road, S17, Singapore 119076, Republic of Singapore
11email<EMAIL_ADDRESS>22institutetext: School of Computing, National
University of Singapore, 13 Computing Drive, COM1, Singapore 117417, Republic
of Singapore 22email<EMAIL_ADDRESS>
33institutetext: Centre for Quantum Technologies, National University of
Singapore, Block S15, 3 Science Drive 2, Singapore 117543
33email<EMAIL_ADDRESS>
# Alternating Automatic Register Machines††thanks: Z. Gao (as RF) and S. Jain
(as Co-PI), F. Stephan (as PI) have been supported by the Singapore Ministry
of Education Academic Research Fund grant MOE2019-T2-2-121 / R146-000-304-112.
Furthermore, S. Jain is supported in part by NUS grants C252-000-087-001 and
E-252-00-0021-01. Further support is acknowledged for the NUS tier 1 grants
AcRF R146-000-337-114 (F. Stephan as PI) and R252-000-C17-114 (F. Stephan as
PI).

Ziyuan Gao 11 Sanjay Jain 22 Zeyong Li 33 Ammar Fathin Sabili 22 Frank Stephan
1122

###### Abstract

This paper introduces and studies a new model of computation called an
Alternating Automatic Register Machine (AARM). An AARM possesses the basic
features of a conventional register machine and an alternating Turing machine,
but can carry out computations using bounded automatic relations in a single
step. One finding is that an AARM can recognise some NP-complete problems,
including CNF-SAT (using a particular coding), in $\log^{*}n+\mathcal{O}(1)$
steps. On the other hand, if all problems in P can be solved by an AARM in
$\mathcal{O}(\log^{*}n)$ rounds, then $\text{P}\subset\text{PSPACE}$.

Furthermore, we study an even more computationally powerful machine, called a
Polynomial-Size Padded Alternating Automatic Register Machine (PAARM), which
allows the input to be padded with a polynomial-size string. It is shown that
the polynomial hierarchy can be characterised as the languages that are
recognised by a PAARM in $\log^{*}n+\mathcal{O}(1)$ steps. These results
illustrate the power of alternation when combined with computations involving
automatic relations, and uncover a finer gradation between known complexity
classes.

###### Keywords:

Theory of Computation Computational Complexity Automatic Relation Register
Machine Nondeterministic Complexity Alternating Complexity Measures of
Computation Time

##  1 Introduction

Automatic structures generalise the notion of regularity for languages to
other mathematical objects such as functions, relations and groups, and were
discovered independently by Hodgson [14, 15], Khoussainov and Nerode [18] as
well as Blumensath and Grädel [2, 3]. One of the original motivations for
studying automaticity in general structures came from computable structure
theory, in particular the problem of classifying the isomorphism types of
computable structures and identifying isomorphism invariants. In computer
science, automatic structures arise in the area of infinite state model
checking; for example, Regular Model Checking, a symbolic framework for
modelling and verifying infinite-state systems, can be expressed in
Existential Second-Order Logic over automatic structures [23]. Although
finite-state transducers are a somewhat more popular extension of ordinary
finite-state automata for defining relations between sets of strings, there
are several advantages of working with automatic relations, including the
following: (1) in general, automatic relations enjoy better decidability
properties than finite-state transducers; for example, equivalence between
ordinary automata is decidable while this is not so for finite-state
transducers; (2) automatic relations are closed under first-order definability
[15, 17, 18] while finite-state transducers are not closed under certain
simple operations such as intersection and complementation.

In this paper, we introduce a new model of computation, called an Alternating
Automatic Register Machine (AARM), that is analogous to an alternating Turing
machine but may incorporate bounded automatic relations111Here an update
relation is bounded if there is a constant such that each possible output is
at most that constant longer than the longest input parameter; see Section 2.
Since we mainly consider bounded automatic relations in this paper, such
relations will occasionally be called “automatic relations”. into each
computation step. The main motivation is to try to discover new interesting
complexity classes defined via machines where automatic relations are taken as
primitive steps, and use them to understand relationships between fundamental
complexity classes such as P, PSPACE and NP. More powerful computational
models are often obtained by giving the computing device more workspace or by
allowing non-deterministic or alternating computations, where alternation is a
well-known generalisation of non-determinism. We take up both approaches in
this work, extending the notion of alternation to automatic relation
computations. An AARM is similar to a conventional register machine in that it
consists of a register $R$ containing a string over a fixed alphabet at any
point in time, and the contents of $R$ may be updated in response to
instructions. One novel feature of an AARM is that the contents of the
register can be non-deterministically updated using an automatic relation.
Specifically, an instruction $J$ is an automatic relation. Executing the
instruction, when the content of the register $R$ is $r$, means that the
contents of $R$ is updated to any $x$ in $\\{x:(x,r)\in J\\}$; if there is no
such $x$, then the program halts. Each AARM contains two finite classes,
denoted here as $A$ and $B$, of instructions; during a computation,
instructions are selected alternately from $A$ and $B$ and executed.

To further explain how a computation of an AARM is carried out, we first
recall the notion of an alternating Turing machine as formulated by Chandra,
Kozen and Stockmeyer [8]. As mentioned earlier, alternation is a
generalisation of non-determinism, and it is useful for understanding the
relationships between various complexity classes such as those in the
polynomial hierarchy (PH). The computation of an alternating Turing machine
can be viewed as a game in which two players – Anke and Boris – make moves
(not necessarily strictly alternating) beginning in the start configuration of
the machine with a given input $w$ [11]. Anke moves from existential
configurations (configurations with an existential state), and Boris from
universal configurations (configurations with a universal state) to successor
configurations according to the machine’s transition function. Anke wins if,
after a finite number of moves, an accepting configuration is reached. The
input $w$ is then accepted by the machine iff Anke has a winning strategy. Our
definition of an AARM computation is inspired by this game-theoretic
interpretation of alternating Turing machines. Given an input $w$, which is
the string in $R$ at the start of the computation, Anke and Boris move in
alternating turns, with Anke moving first. During Anke’s turn, she carries out
any single instruction in the predefined set $A$, possibly changing the
contents of the register. Boris moves similarly during his turn, except that
he carries out an instruction in $B$. Anke wins if a configuration is reached
such that Boris is no longer able to carry out any instructions in $B$, and
$w$ is accepted iff Anke has a winning strategy. We also introduce and study
Polynomial-Size Padded Bounded Alternating Automatic Register Machines
(PAARMs), which allow a polynomial-size padding to the input of an AARM.

The idea of defining computing devices capable of performing single-step
operations that are more sophisticated than the basic operations of Turing
machines is not new. For example, Floyd and Knuth [10] studied addition
machines, which are finite register machines that can carry out addition,
subtraction and comparison as primitive steps. Unlimited register machines,
introduced by Shepherdson and Sturgis [24], can copy the number in a register
to any register in a single step. Bordihn, Fernau, Holzer, Manca and Martín-
Vide [4] investigated another kind of language generating device called an
iterated sequential transducer, whose complexity is usually measured by its
number of states (or state complexity). More recently, Kutrib, Malcher,
Mereghetti and Palano [19] proposed a variant of an iterated sequential
transducer that performs length-preserving transductions on left-to-right
sweeps. Automatic relations are more expressive than arithmetic operations
such as addition or subtraction, and yet they are not too complex in that even
one-tape linear-time Turing machines are computationally more powerful; for
instance, the function that erases all leading 0’s in any given binary word
can be computed by a one-tape Turing machine in linear time but it is not
automatic [26]. Despite the computational limits of automatic relations, we
show in Theorem 3.4 below that the NP-complete Boolean satisfiability problem
can be recognised by an AARM in $\log^{*}n+\mathcal{O}(1)$ steps, where $n$ is
the length of the formula. The results not only show a proof-of-concept for
the use of automatic relations in models of computation, but also shed new
light on the relationships between known complexity classes.

##  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$. A language is a set of strings. Let the empty string be
denoted by $\varepsilon$. For a string $w\in\Sigma^{*}$, let $|w|$ denote the
length of $w$ and $w=w_{1}w_{2}...w_{|w|}$ where $w_{i}\in\Sigma$ denotes the
$i$-th symbol of $w$. Fix a special 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 a string over
$(\Sigma\cup\\{\\#\\})\times(\Sigma\cup\\{\\#\\})$, defined as
$conv(x,y)=(x_{1}^{\prime},y_{1}^{\prime})(x_{2}^{\prime},y_{2}^{\prime})\ldots(x_{r}^{\prime},y_{r}^{\prime})$.
A relation $J\subseteq X\times Y$ is automatic if the set
$\\{conv(x,y):(x,y)\in J\\}$ is regular, where the alphabet is
$(\Sigma\cup\\{\\#\\})\times(\Sigma\cup\\{\\#\\})$. Likewise, a function
$f:X\rightarrow Y$ is automatic if the relation $\\{(x,y):x\in domain(f)\land
y=f(x)\\}$ is automatic [27]. An automatic relation $J$ is bounded if
$\exists$ constant $c$ such that $\forall(x,y)\in J,\text{abs}(|y|-|x|)\leq
c$. On the other hand, an unbounded automatic relation has no such
restriction. The problem of determining satisfiability of any given Boolean
formula in conjunctive normal form will be denoted by CNF-SAT. Automatic
functions and relations have a particularly nice feature as shown in the
following theorem.

######  Theorem 2.1 ([15, 18]).

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.

##  3 Alternating Automatic Register Machines

An Alternating Automatic Register Machine (AARM) consists of a register $R$
and two finite sets $A$ and $B$ of instructions. $A$ and $B$ are not
necessarily disjoint. Formally, we denote an AARM by $M$ and represent it as a
quadruple $(\Gamma,\Sigma,A,B)$. (An equivalent model may allow for multiple
registers.) At any point in time, the register contains a string, possibly
empty, over a fixed alphabet $\Gamma$ called the register alphabet. The
current string in $R$ is denoted by $r$. Initially, $R$ contains an input
string over $\Sigma$, an input alphabet with $\Sigma\subseteq\Gamma$. Strings
over $\Sigma$ will sometimes be called words. The contents of the register may
be changed in response to an instruction. An instruction
$J\subseteq\Gamma^{*}\times\Gamma^{*}$ is a bounded automatic relation; this
changes the contents of $R$ to some $x$ such that $(r,x)\in J$ (if such an $x$
exists). The instructions in $A$ and $B$ are labelled $I_{1},I_{2},\ldots,$
(in no particular order and not necessarily distinct). A configuration is a
triple $(\ell,r,w)$, where $I_{\ell}$ is the current instruction’s label and
$r,w\in\Gamma^{*}$. Instructions are generally nondeterministic, that is,
there may be more than one way in which the string in $R$ is changed from a
given configuration in response to an instruction. A computation history of an
AARM with input $w$ for any $w\in\Sigma^{*}$ is a finite or infinite sequence
$c_{1},c_{2},c_{3},\ldots$ of configurations such that the following
conditions hold. Let $c_{i}=(\ell_{i},r_{i},w_{i})$ for all $i$.

  * •

$r_{1}=w$. We call $c_{1}$ the initial configuration of the computation
history.

  * •

For all $i$, $(r_{i},w_{i})\in I_{\ell_{i}}$. This means that $I_{\ell_{i}}$
can be carried out using the current register contents, changing the contents
of $R$ to $w_{i}$.

  * •

Instructions executed at odd terms of the sequence belong to $A$, while those
executed at even terms belong to $B$:

> $I_{\ell_{i}}\in\left\\{\begin{array}[]{ll}A&\mbox{if $i$ is odd;}\\\
> B&\mbox{if $i$ is even.}\end{array}\right.$

  * •

If $c_{i+1}$ is defined, then $r_{i+1}=w_{i}$. In other words, the contents of
$R$ are (nondeterministically) updated according to the instruction and
register contents of the previous configuration.

  * •

Suppose $i$ is odd (resp. even) and $c_{i}=(I_{\ell_{i}},r_{i},w_{i})$ is
defined. If there is some $I_{\ell}\in B$ (resp. $I_{\ell}\in A$) with
$\\{x:(w_{i},x)\in I_{\ell}\\}$ nonempty, then $c_{i+1}$ is defined. In other
words, the computation continues so long as it is possible to execute an
instruction from the appropriate set, either $A$ or $B$, at the current term.

We interpret a computation history of an AARM as a sequential game between two
players, Anke and Boris, where Anke moves during odd turns and Boris moves
during even turns. During Anke’s turn, she must pick some instruction $J$ from
$A$ such that $\\{x:(r,x)\in J\\}$ is nonempty and select some
$w\in\\{x:(r,x)\in J\\}$; if no such instruction exists, then the game
terminates. The contents of $R$ are then changed to $w$ at the start of the
next turn. The moving rules for Boris are defined analogously, except that he
must pick instructions only from $B$. Anke wins if the game terminates after a
finite number of turns and she is the last player to execute an instruction;
in other words, Boris is no longer able to carry out an instruction in $B$ and
the length of the game (or computation history), measured by the total number
of turns up to and including the last turn, is odd. The condition for Boris to
win is defined symmetrically. A draw game is one such that no player wins in
finitely many turns, that is, the game runs forever. The AARM accepts a word
$w$ if Anke can move in such a way that she will always win a game with an
initial configuration $(\ell,w,v)$ for some $I_{\ell}\in A$ and
$v\in\Gamma^{*}$, regardless of how Boris moves. To state this acceptance
condition more formally, one could define Anke’s and Boris’ strategies to be
functions $\mathcal{A}$ and $\mathcal{B}$ respectively with
$\mathcal{A}:(\mathbb{N}\times\Gamma^{*}\times\Gamma^{*})^{*}\times\Gamma^{*}\mapsto
A\times\Gamma^{*}$ and
$\mathcal{B}:(\mathbb{N}\times\Gamma^{*}\times\Gamma^{*})^{*}\times\Gamma^{*}\mapsto
B\times\Gamma^{*}$, which map each segment of a computation history together
with the current contents of $R$ to a pair specifying an instruction as well
as the new contents of $R$ at the start of the next round according to the
moving rules given earlier. The AARM accepts $w$ if there is an $\mathcal{A}$
such that for every $\mathcal{B}$, there is a finite computation history
$\langle c_{1},\ldots,c_{2n+1}\rangle$ where

  * •

$c_{i}=(\ell_{i},r_{i},w_{i})$ for each $i$,

  * •

$r_{1}=w$,

  * •

$\mathcal{A}((\langle
c_{i}:i<2j+1\rangle,r_{2j+1}))=(I_{\ell_{2j+1}},w_{2j+1})$ for each
$j\in\\{0,\ldots,n\\}$,

  * •

$\mathcal{B}((\langle c_{i}:i<2k\rangle,r_{2k}))=(I_{\ell_{2k}},w_{2k})$ for
each $k\in\\{1,\ldots,n\\}$;

  * •

there is no move for $B$ in $c_{2n+1}$, that is no instruction in $B$ contains
a pair of the form $(w_{2n+1},\cdot)$.

Here $\langle c_{i}:i<k\rangle$ denotes the sequence $\langle
c_{1},\ldots,c_{k-1}\rangle$, which is empty if $k\leq 1$. Such an
$\mathcal{A}$ is called a winning strategy for Anke with respect to $(M,w)$.
Given a winning strategy $\mathcal{A}$ for Anke with respect to $(M,w)$ and
any strategy $\mathcal{B}$, the corresponding computation history of $M$ with
input $w$ is unique and will be denoted by
$\mathcal{H}(\mathcal{A},\mathcal{B},M,w)$. In most subsequent proofs,
$\mathcal{A}$ and $\mathcal{B}$ will generally not be defined so formally. Set

> $L(M):=\\{w\in\Sigma^{*}:\mbox{$M$ accepts $w$}\\}$;

one says that $M$ recognises $L(M)$. Note that even though we have given the
description of AARM via alternation of moves by Anke and Boris, it is possible
to define games where strict alternation is not needed. Furthermore, a
constant amount of extra state information can be stored in the register.

######  Definition 1 (Alternating Automatic Register Machine Complexity).

Let $M=(\Gamma,\Sigma,A,B)$ be an AARM and let $t\in\mathbb{N}_{0}$. For each
$w\in\Sigma^{*}$, $M$ accepts $w$ in time $t$ if Anke has a winning strategy
$\mathcal{A}$ with respect to $(M,w)$ such that for any strategy $\mathcal{B}$
played by Boris, the length of $\mathcal{H}(\mathcal{A},\mathcal{B},M,w)$ is
not more than $t$. (As defined earlier,
$\mathcal{H}(\mathcal{A},\mathcal{B},M,w)$ is the computation history of $M$
with input $w$ when $\mathcal{A}$ and $\mathcal{B}$ are applied.)

An AARM decides a language $L$ in $f(n)$ steps for a function $f$ depending on
the length $n$ of the input if for all $x\in\\{0,1\\}^{n}$, both players can
enforce that the game terminates within $f(n)$ steps by playing optimally and
one player has a winning strategy needing at most $f(n)$ moves and $x\in L$ if
Anke is the player with the winning strategy. $\text{AAL}[f(n)]$ denotes the
family of languages decided by AARMs that decide in time $f(n)$.

We begin with several examples to illustrate AARMs and how they carry out
computations.

######  Example 1.

  1. 1.

If $A$ and $B$ are both empty, then every computation history of the
corresponding AARM is empty; thus the AARM does not accept any input.

  2. 2.

Suppose $\Gamma=\\{0,1\\}$. Let $A$ consist of the single instruction $I_{1}$
which consists of all pairs $(y,x)\in\Gamma^{*}\times\Gamma^{*}$ with $x=y$,
and suppose $B$ is empty. It is easy to see that $I_{1}$ is an automatic
relation. Since $\\{x:(v,x)\in I_{1}\\}$ is nonempty for any $v$ and $B$ is
empty, it follows that every computation history with any input $w$ always
ends at the initial configuration $(1,w,w)$. The corresponding AARM thus
accepts any binary word.

  3. 3.

Suppose
$\Gamma=\\{0,1,\overset{\bullet}{0},\overset{\bullet}{1},\blacksquare,\bigstar\\}$.
$\overset{\bullet}{i}$ is a “marked” version of $i$ for $i\in\\{0,1\\}$;
$\blacksquare$ is a special symbol indicating a rejection of the input, while
$\bigstar$ indicates an acceptance of the input. Let $A$ consist of the
instructions $I_{1}$ and $I_{2}$.
$I_{1}\subseteq\\{0,1,\overset{\bullet}{0},\overset{\bullet}{1}\\}^{*}\times\\{0,1,\overset{\bullet}{0},\overset{\bullet}{1}\\}^{*}$
is the relation containing all pairs $(y,x)$ such that
$y\in\\{0,\overset{\bullet}{0}\\}^{*}\cdot\\{1,\overset{\bullet}{1}\\}^{*}$
and $x$ is the string obtained from $y$ by marking every alternate unmarked
$0$ starting with the first unmarked $0$ as well as every alternate unmarked
$1$ starting with the first unmarked $1$, while leaving other symbols
unchanged. For example,
$(00011,\overset{\bullet}{0}0\overset{\bullet}{0}\overset{\bullet}{1}1)\in
I_{1},(\overset{\bullet}{0}0\overset{\bullet}{0}\overset{\bullet}{1}1\times\overset{\bullet}{0}0\overset{\bullet}{0}\overset{\bullet}{1}\overset{\bullet}{1})\notin
I_{1}.$

$I_{2}\subseteq\\{\overset{\bullet}{0},\overset{\bullet}{1},\bigstar\\}^{*}\times\Gamma^{*}$
contains all pairs $(y,x)$ such that $y$ does not have any unmarked $0$’s or
$1$’s and $x=y\cdot\bigstar$.

Let $B$ consist of the instruction $I_{3}$, where
$I_{3}\subseteq\\{0,1,\overset{\bullet}{0},\overset{\bullet}{1}\\}^{*}\times\Gamma^{*}$
is the relation containing all pairs $(y,x)$ such that $x=y\cdot\blacksquare$
if the total number of unmarked $0$’s and $1$’s in $y$ is odd and $x=y$
otherwise. One can show as before that $I_{1},I_{2}$ and $I_{3}$ are
automatic. Let $w\in\\{0,1\\}^{*}$ be any given input. If $0$ occurs to the
right of some $1$ in $w$, then each computation history with input $w$ is
empty, so the AARM does not accept $w$. If $w$ is of the shape $0^{n}1^{m}$
with $n\neq m$, then, after an odd number of turns, the total number of
unmarked $0$’s or $1$’s will be odd, and executing $I_{3}$ from $B$ during the
next turn will result in $R$ containing a string with the symbol
$\blacksquare$. No instructions in $A$ can subsequently be carried out. If $w$
is of the shape $0^{n}1^{n}$, then eventually all the symbols in $w$ will be
marked and $I_{2}$ can be carried out, resulting in $R$ containing a string
with the symbol $\bigstar$. No instructions in $B$ can then be executed. The
corresponding AARM thus accepts the language of all binary words of the shape
$0^{n}1^{n}$.

We first establish the closure of $\text{AAL}[\mathcal{O}(f(n))]$ under the
usual set-theoretic Boolean operations as well as the regular operations.

######  Theorem 3.1.

Let $\star$ denote any one of the operations union, intersection and
concatenation. For each $L_{1}\in\text{AAL}[\mathcal{O}(f(n))]$ and each
$L_{2}\in\text{AAL}[g(n)]$, $L_{1}\star
L_{2}\in\text{AAL}[\max\\{f(n),g(n)\\}]$ and
$L_{1}^{*}\in\text{AAL}[\mathcal{O}(f(n))]$. In particular, the languages in
$\text{AAL}[\mathcal{O}(f(n))]$ are closed under union, intersection,
concatenation and Kleene star.

###### Proof.

Suppose $L_{1}\in\text{AAL}[f(n)]$ and $L_{2}\in\text{AAL}[g(n)]$. Let
$M_{1}=(\Gamma,\Sigma,A,B)$ and
$M_{2}=(\Gamma^{\prime},\Sigma,A^{\prime},B^{\prime})$ be AARMs such that
$L_{1}=L(M_{1})$, $L_{2}=L(M_{2})$ and $M_{1}$ and $M_{2}$ recognise in times
$f(n)$ and $g(n)$ respectively. We provide the formal details for constructing
an AARM
$M_{3}=(\Gamma^{\prime\prime},\Sigma,A^{\prime\prime},B^{\prime\prime})$
recognising $L_{1}\cup L_{2}$ in time $\max\\{f(n),g(n)\\}$, and give informal
descriptions of the AARMs for the other operations.

  * •

The components of $M_{3}$ are defined as follows. Suppose
$\boxplus\notin\Gamma\cup\Gamma^{\prime}$ and
$\lozenge\notin\Gamma\cup\Gamma^{\prime}$.

    1. (i)

$\Gamma^{\prime\prime}=\Gamma\cup\Gamma^{\prime}\cup\\{\boxplus,\lozenge\\}$.

    2. (ii)

Let $J$ (resp. $J^{\prime}$) be the relation consisting of all pairs
$(x,\boxplus x)$ (resp. $(x,\linebreak[3]\lozenge x)$) with $x\in\Sigma^{*}$
and put $J$ (resp. $J^{\prime}$) into $A^{\prime\prime}$.

    3. (iii)

Let $K$ (resp. $K^{\prime}$) be the relation consisting of all pairs
$(x,\boxplus x,)$ (resp. $(x,\linebreak[3]\lozenge x)$) with
$x\in\boxplus\cdot\Sigma^{*}$ (resp. $x\in\lozenge\cdot\Sigma^{*}$) and put
$K$ (resp. $K^{\prime}$) into $B^{\prime\prime}$.

    4. (iv)

For every instruction $L$ in $A$ (resp. $B$), let $L^{\prime}$ be the relation
such that $(\boxplus\boxplus y,\boxplus\boxplus x)\in
L^{\prime}\Leftrightarrow(y,x)\in L$, and put $L^{\prime}$ into
$A^{\prime\prime}$ (resp. $B^{\prime\prime}$).

    5. (v)

For every instruction $L$ in $A^{\prime}$ (resp. $B^{\prime}$), let
$L^{\prime}$ be the relation such that $(\lozenge\lozenge y,\lozenge\lozenge
x)\in L^{\prime}\Leftrightarrow(y,x)\in L$, and put $L^{\prime}$ into
$A^{\prime\prime}$ (resp. $B^{\prime\prime}$).

Given any $w\in L_{1}\cup L_{2}$, a winning strategy for Anke with respect to
$(M_{3},w)$ is as follows. At the start of the game, Anke determines whether
$w\in L_{1}$ or $w\in L_{2}$ (if $w\in L_{1}\cap L_{2}$, then Anke can just
follow the subsequent steps for the case $w\in L_{1}$). Assume $w\in L_{1}$.
The first move of Anke is to change the contents of $R$ from $w$ to $\boxplus
w$ using one of the instructions defined in (ii). During the second turn, the
only move Boris can make is to change the current contents of $R$ by
prepending it with $\boxplus$, using one of the instructions defined in (iii).
The third turn starts with $\boxplus\boxplus w$ in $R$. Anke then adapts a
winning strategy with respect to $(M_{1},w)$, using the instructions defined
in (iv); the only difference between the current strategy and that for
$(M_{1},w)$ is that the current one applies to the register’s contents
prepended with $\boxplus\boxplus$. From the third turn onwards, Anke and Boris
can only apply instructions defined in (iv) and so the game would proceed as
in a computation history of $M_{1}$ with input $w$ (except that the register’s
contents are prepended with $\boxplus\boxplus$). In the case that $w\in
L_{2}$, Anke proceeds similarly, except that the third turn starts with
$\lozenge\lozenge w$ in $R$ and she would adapt a winning strategy with
respect to $(M_{2},w)$. In either case, the length of the game is
$\mathcal{O}(\max\\{f(|w|),g(|w|)\\})+2=\mathcal{O}(\max\\{f(|w|),g(|w|)\\})$.

Suppose $w\notin L_{1}\cup L_{2}$. If $R$ contains $\boxplus\boxplus w$ (resp.
$\lozenge\lozenge w$) at the start of the third turn, then the game would
proceed in a way similar to that of a computation history of $M_{1}$(resp.
$M_{2}$) with input $w$, that is, either it terminates with Boris making the
last move or it never terminates. Therefore $L(M_{3})=L_{1}\cup L_{2}$ and
$M_{3}$ recognises in time $\mathcal{O}(\max\\{f(n),g(n)\\})$.

  * •

For $L_{1}\cap L_{2}$, a technique similar to that in (i) can be applied.
$A^{\prime\prime}$ will have an instruction allowing Anke to skip the first
turn and $B^{\prime\prime}$ will have an instruction allowing Boris in the
second turn to “pick” $L_{1}$ or $L_{2}$ (say by prepending the input with a
special symbol). If Boris picks $L_{1}$, then the remainder of the game would
proceed as in a computation history of $M_{1}$ with input $w$; otherwise, it
proceeds as in a computation history of $M_{2}$ with input $w$.

  * •

For $L_{1}\cdot L_{2}$, Anke would first mark a splitting point in the input,
then Boris will pick which side he wants to verify.

  * •

For $L_{1}^{*}$, Anke would first mark all splitting points, then Boris will
pick a single string he wants to verify.

∎

We now show that the family of all languages recognised by some AARM coincides
with the family of all recursively enumerable (r.e.) languages. First, it is
shown that any conventional register machine can be simulated with an AARM. We
use a slight variant of Shepherdson and Sturgis’ [24] unlimited register
machine.

######  Proposition 1.

Consider any register machine $M^{\prime}$ with $n$ registers
$R_{1},\ldots,R_{n}$ and a program consisting of a sequence
$I_{1},\ldots,I_{k}$ of instructions, each taking one of the following forms:

  * •

$R^{+}\rightarrow I^{\prime}$, which adds $1$ to the contents of register $R$
and jumps to instruction $I^{\prime}$;

  * •

$R^{-}\rightarrow I^{\prime},I^{\prime\prime}$, which subtracts $1$ from the
contents of register $R$ and jumps to instruction $I^{\prime}$ if the current
number in $R$ is positive, else jumps to instruction $I^{\prime\prime}$;

  * •

HALT, which stops any further instructions from being carried out.

The contents of the registers at any point in time are binary strings, each
representing a natural number. Then there is an AARM $M$ such that for each
binary word $w$, $M$ accepts $w$ iff $M^{\prime}$ halts when $R_{1}$ initially
contains $w$ and $R_{i}$ initially contains $0$ for each $i>1$.

###### Proof.

For any natural number $k$, let $\mathit{string}(k)$ denote the binary
representation of $k$. Let $M$ be an AARM with register $R$ and instruction
sets $A$ and $B$. Let $\Gamma=\\{0,1,\\#,\bigstar\\}$. $R$ will simulate the
current instruction being read by $M^{\prime}$ as well as the current contents
of $R_{1},\ldots,R_{n}$; each of these simulated items will be separated with
the symbol $\\#$. Suppose $R_{1}$ initially contains $w$ and $R_{i}$ initially
contains $0$ for each $i>1$. We may assume without loss of generality that
$w\neq\varepsilon$ and $R$ initially contains the string

> $\mathit{string}(1)\\#w\\#0\\#\ldots\\#0$,

which contains $n$ occurrences of $\\#$. For each $I_{i}$, $A$ will contain a
corresponding instruction $I^{\prime}_{i}$ defined according to the following
case distinction:

$I_{i}:=R_{j}^{+}\rightarrow I_{k}$:

Let $I_{i}^{\prime}$ be the relation consisting of all pairs $(y,x)$ such that
$y$ is of the form
$\mathit{string}(i)\\#\mathit{string}(i_{1})\\#\mathit{string}(i_{2})\\#\ldots\\#\mathit{string}(i_{n})$
and $x$ equals $\mathit{string}(k)\\#\mathit{string}(i_{1})\\#\ldots$
$\\#\mathit{string}(i_{j}+1)\\#\ldots\\#\mathit{string}(i_{n})$. This
instruction simulates, when running $M^{\prime}$, the addition of $1$ to
$R_{j}$ and the jump from $I_{i}$ to $I_{k}$.

$I_{i}:=R_{j}^{-}\rightarrow I_{k},I_{\ell}$:

Let $I_{i}^{\prime}$ be the relation consisting of all pairs $(y,x)$ such that
$y$ is of the form
$\mathit{string}(i)\\#\mathit{string}(i_{1})\\#\mathit{string}(i_{2})\\#\ldots\\#\mathit{string}(i_{n})$;
if $y$ is of this form, then $i_{j}=0$ implies $x$ equals
$\mathit{string}(\ell)\\#\mathit{string}(i_{1})\\#\ldots\\#\mathit{string}(i_{n})$,
that is, only the first segment is changed and it becomes
$\mathit{string}(\ell)$, and $i_{j}>0$ implies $x$ equals
$\mathit{string}(k)\\#\mathit{string}(i_{1})\\#\ldots$
$\mathit{string}(i_{j}-1)\\#\ldots\\#\mathit{string}(i_{n})$, that is, the
first segment is changed to $\mathit{string}(k)$ and the $(j+1)$-st segment is
changed to $\mathit{string}(i_{j}-1)$. If $R_{j}$ currently contains a
positive number, then $I^{\prime}_{i}$ simulates the subtraction of $1$ from
the number currently in $R_{j}$ and the jump from $I_{i}$ to $I_{k}$;
otherwise, $I^{\prime}_{i}$ simulates the jump from $I_{i}$ to $I_{\ell}$.

$I_{i}:=\textsc{HALT}$:

Let $I_{i}^{\prime}$ be the relation consisting of all pairs $(y,x)$ such that
$y$ is of the form
$\mathit{string}(i)\\#\mathit{string}(i_{1})\\#\mathit{string}(i_{2})\\#\ldots\\#\mathit{string}(i_{n})$
and $x$ equals $\bigstar^{|y|}$. $I^{\prime}_{i}$ changes the contents of $R$
to a nonempty string over $\\{\bigstar\\}$, signalling that $M^{\prime}$ has
halted.

$B$ consists of the single instruction $R^{\prime}\in\\{x:(R^{\prime},x)\in
N\\}$, where $N\subseteq(\Gamma\setminus\\{\bigstar\\})^{*}\times\Gamma^{*}$
is the relation consisting of all pairs $(y,x)$ such that $x=y$. Suppose
$M^{\prime}$ eventually halts when $R_{1}$ initially contains $w$ and $R_{i}$
contains $0$ for each $i>1$. Anke carries out instruction $I^{\prime}_{i}$
whenever $I_{i}$ applies to $M^{\prime}$, starting with $i=1$. Boris can only
carry out one instruction, which leaves the contents of $R^{\prime}$
unchanged. $M^{\prime}$ halts only when some $I_{i}:=\textsc{HALT}$ is
applied; Anke then applies $I^{\prime}_{i}$, which changes the contents of
$R^{\prime}$ to a nonempty string over $\\{\bigstar\\}$. Since Boris cannot
execute any instruction when $R^{\prime}$ contains a string with an occurrence
of $\bigstar$, the game will always end with Anke. On the other hand, if
$M^{\prime}$ never halts, then the contents of $R^{\prime}$ will never change
to a string containing $\bigstar$ and so Boris can always keep the game going.
Thus $M$ accepts $w$ iff $M^{\prime}$ halts. ∎

It remains to show that an AARM recognises only r.e. languages. The proof of
this fact relies on the boundedness assumption for automatic relations used in
register updates of an AARM.

######  Proposition 2.

For each AARM $M$, $L(M)$ is r.e.

###### Proof.

Suppose $w$ is given as an input to $M$. The family of all computation
histories of $M$ with input $w$ may be viewed as a tree $\tau$ consisting of a
root node $(0,\varepsilon,\varepsilon)$ and all possible configurations (each
represented as a node) of such a computation history. Each maximal path in
$\tau$ starting with the root node is a concatenation of the root node and a
computation history of $M$ with input $w$. Owing to the boundedness of all
automatic relations used in the instructions of $M$, $\tau$ is finitely
branching. Suppose Anke has a winning strategy with respect to $(M,w)$.
Consider the subtree $\tau^{\prime}$ of all computation histories prepended
with the root node $(0,\varepsilon,\varepsilon)$ such that Anke always moves
according to a fixed winning strategy. If $\tau^{\prime}$ were infinite, then
by König’s lemma, $\tau^{\prime}$ would have an infinite branch and Boris
would win the game represented by this branch, contradicting the assumption
that Anke is applying a winning strategy. Thus there is some $d$ such that all
computation histories when Anke is applying a winning strategy have length at
most $d$. An algorithm can guess the value of $d$ and, by Theorem 2.1,
determine recursively that Boris can no longer make a valid move when the
length of the game has reached $d$ no matter how he plays, and accept $w$. On
the other hand, if Anke does not have a winning strategy, then no such $d$
exists and so the algorithm would never accept $w$. Such an algorithm would
therefore recognise the set of all words for which Anke has a winning
strategy. ∎

Propositions 1 and 2 together imply the desired result.

######  Theorem 3.2.

The family of languages recognised by AARMs is precisely the family of r.e.
languages.

We recall that an alternating Turing machine that decides in
$\mathcal{O}(f(n))$ time can be simulated by a deterministic Turing machine
using $\mathcal{O}(f(n))$ space. The following theorem gives a similar
connection between the time complexity of AARMs and the space complexity of
deterministic Turing machines.

######  Theorem 3.3.

For any $f$ such that $f(n)\geq n$,
$\text{AAL}[\mathcal{O}(f(n))]\subseteq\text{DSPACE}[\mathcal{O}((n+f(n))f(n))]=\text{DSPACE}[\mathcal{O}(f(n)^{2})]$.

###### Proof.

Given an AARM $M$, there is a constant $c$ such that each register update by
an automatic relation used to define an instruction of $M$ increases the
length of the register’s contents by at most $c$. Thus, after
$\mathcal{O}(f(n))$ steps, the length of the register’s contents is
$\mathcal{O}(n+f(n))$. As implied by [7, Theorem 2.4], each computation of an
automatic relation with an input of length $\mathcal{O}(n+f(n))$ can be
simulated by a nondeterministic Turing machine in $\mathcal{O}(n+f(n))$ steps;
this machine can then be converted to a deterministic space
$\mathcal{O}(n+f(n))$ Turing machine. If $M$ accepts an input $w$, then there
are $\mathcal{O}(f(n))$ register updates by automatic relations when Anke
applies a winning strategy, and so there is a deterministic Turing machine
simulating $M$’s computation with input $w$ using space
$\mathcal{O}((n+f(n))f(n))$. ∎

As a consequence, one obtains the following analogue of the equality between
AP (classes of languages that are decided by alternating polynomial time) and
PSPACE.

######  Corollary 1.

$\bigcup_{k}\text{AAL}[\mathcal{O}(n^{k})]=\text{PSPACE}$.

###### Proof.

The containment relation
$\text{AAL}[\mathcal{O}(f(n))]\subseteq\text{DSPACE}[\mathcal{O}((n+f(n))f(n))]$
in Theorem 3.3 holds whether or not the condition $f(n)\geq n$ holds.
Furthermore, the computation of an alternating Turing machine can be simulated
using an AARM, where the transitions from existential (respectively,
universal) states correspond to the instructions for Anke (respectively,
Boris), and each computation step of the alternating Turing machine
corresponds to a move by either player. Therefore PSPACE, which is equal to
AP, is contained in $\bigcup_{k}\text{AAL}[n^{k}]$. ∎

We come next to a somewhat surprising result: an AARM-program can recognise
3SAT using just $\log^{*}n+\mathcal{O}(1)$ steps. To prove the theorem, we
give the following lemma, which illustrates most of the power of AARMs.

######  Lemma 1 (Log-Star Lemma).

Let $u,v\in\Sigma^{*}$. Let $\\#,\$\not\in\Sigma$. Then both languages
$\\{u^{\prime}\$v^{\prime}:u^{\prime}\in\\#^{*}u\\#^{*},v^{\prime}\in\\#^{*}v\\#^{*}$
and $u=v\\}$ and
$\\{u^{\prime}\$v^{\prime}:u^{\prime}\in\\#^{*}u\\#^{*},v^{\prime}\in\\#^{*}v\\#^{*}$
and $u\neq v\\}$ are in $\text{AAL}[\log^{*}n+\mathcal{O}(1)]$.

The Log-Star Lemma essentially states that a comparison of two substrings can
be done by an AARM in $\log^{*}n+\mathcal{O}(1)$ time. This is done by
ignoring the unnecessary symbols in the register by replacing them with
$\\#$’s and adding a separator ($\$$) between the two strings.

###### Proof.

We now prove the Log-Star Lemma. The algorithm below recursively reduces the
problem to smaller sizes of $u$, $v$ in constant number of steps (the maximum
of the length of $u,v$ is reduced logarithmically in constant number of
steps). For the base case, if size of $u$ or $v$ is bounded by a constant,
then clearly both languages can be recognized in one step.

For larger size $u,v$, the algorithm/protocol works as follows. For ease of
explanation, suppose Anke is trying to show that $u=v$ (case of Anke showing
$u\neq v$ will be similar). Given input $s=u^{\prime}\$v^{\prime}$, player
Anke will try to give each symbol except $’s a mark $\in\\{0,1,2,3\\}$ as
follows:

  1. 1.

For each $\\#$ in $u^{\prime}$ and $v^{\prime}$, the mark of $3$ will be
given.

  2. 2.

For the contiguous symbols of $u$, starting from the first symbol, the
following infinite marking will be given (whitespaces are for the ease of
readability and not part of marking):

$20~{}21~{}200~{}201~{}210~{}211~{}2000~{}2001~{}2010~{}2011~{}2100~{}2101~{}2110~{}2111~{}20000~{}\cdots$

Namely, a series of blocks of string in ascending length-lexicographical
order. Let $T$ be the so defined infinite sequence. Given a string
$s=u^{\prime}\$v^{\prime}$, where $u^{\prime}\in\\#^{*}u\\#^{*}$ and
$v^{\prime}\in\\#^{*}v\\#^{*}$ for some $u,v\in\Sigma^{*}$, each contiguous
subsequence of $u$ (resp. $v$) whose sequence of positions is equal to the
sequence of positions of $T$ of some string in $2\\{0,1\\}^{*}$ such that the
next symbol in $T$ is $2$ will be called a block. Each block starts with $2$
followed by a binary string. Let $k$ ($\geq 2$) be the maximum size of a
block. Summing the lengths of the blocks of $u$ gives that $(k-2)\cdot
2^{k-1}+k\leq n$, and thus $k\leq\log n$.

  3. 3.

For the contiguous symbols of $v$, the marking will be similar.

The marking is considered valid if all above rules are satisfied. This is an
example of a valid marking of $S=``\\#foobar\\#\\#\$foobar\\#\\#"$:

s | # | f | o | o | b | a | r | # | # | $ | f | o | o | b | a | r | # | #
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Mark | 3 | 2 | 0 | 2 | 1 | 2 | 0 | 3 | 3 | $ | 2 | 0 | 2 | 1 | 2 | 0 | 3 | 3

If $u=v$ and the marking is valid, player Anke will guarantee that each symbol
of $u$ and $v$ will be marked with exactly the same marking. However if $u\neq
v$ and the marking is valid, either the length of $u$ and $v$ are different or
there will be at least a single block which differs on at least one symbol
between $u$ and $v$. Therefore, player Boris can have the following choices of
challenges:

  1. 1.

Challenge that player Anke did not make a valid marking, or

  2. 2.

$|u|\neq|v|$, or

  3. 3.

the string in a specified block differs on at least one symbol between $u$ and
$v$.

Notice that $u=v$ if and only if player Boris could not successfully challenge
player Anke. The first challenge will ensure that player Anke gave a valid
marking. There are three possible cases of invalid marking:

  1. (a)

There is a $\\#$ in $u^{\prime}$ or $v^{\prime}$ which is not given by a mark
of $3$. In this case, player Boris may point out its exact position. Here,
player Boris needs $1$ step.

  2. (b)

For $u$ and $v$, the first block is not marked with "20". This can also be
easily pointed out by player Boris. Here, player Boris needs $1$ step.

  3. (c)

For $u$ and $v$, a block is not followed by its successor. This can be pointed
out by player Boris by checking two things: the length of the ‘successor’
block should be less than or equal to the length of the ‘predecessor’ block
plus one, and the ‘successor’ block indeed should be the successor of the
‘predecessor’ block. Also, we note that the last block may be incomplete.

    1. (i)

The length case can be checked by looking at how many symbols there are
between the pair of $2$’s bordering each block. Let $p$ and $q$ be the length
of ‘predecessor’ block and the ‘successor’ block respectively. In the case
that the ‘successor’ block is not the last block (not incomplete), player
Boris may challenge if $p\neq q$ and $p+1\neq q$. This can be done by marking
both blocks with $1$ separated by $ and the rest with dummy symbols $\\#$ and
then doing the protocol for equality of the modified $u$ and $v$ recursively.
As player Boris may try to find the ‘short’ challenge, player Boris will find
the earliest block which has the issue and thus make sure that $p$ is at most
logarithmic in the maximum of the lengths of $u$ and $v$. As $q$ may be much
larger than $p$, player Boris may limit the second block by taking at most
$p+2$ symbols.

    2. (ii)

The successor case can be checked by the following observation. A successor of
a binary string can be calculated by finding the last $0$ symbol and flipping
all digits from that position to the end while maintaining the previous
digits. As an illustration, the successor of "101100111" will be "101101000"
where the symbols are separated in $3$ parts: the prefix which is the same,
the last $0$ digit, which is underlined, becoming $1$; and all $1$ digits on
suffix becoming $0$. Player Boris then may challenge the first part not to be
equal or the last part not to be the same length or not all $1$’s by providing
the position of the last $0$ on the ‘predecessor’ block (or the last $1$ on
the ‘successor’ block, if any). Checking the equality of two strings can be
done recursively, also similarly applied for checking the length. Notice a
corner case of all $1$’s which has the successor consisting of $1$ followed by
$0$’s with the same length, which can be handled separately. Also notice that
the ‘successor’ block may be incomplete if it is the last block, which can
also be handled in a similar manner as above.

For the second challenge, player Boris can (assuming the marking is valid)
check whether the last two blocks of $u$ and $v$ are equal. Again, player
Boris may limit it for a ‘short’ challenge so the checking size is decreasing
to its $\log$. For the third challenge, player Boris will specify the two
blocks on $u$ and $v$ (same block on both) which differ on at least one symbol
between $u$ and $v$. Again, same protocol will apply and the size is
decreasing to its $\log$. Furthermore, both the marking and selection of
blocks are done in a single turn.

Thus, the above algorithm using one alternation of each of the players reduces
the problem to logarithmic in the size of the maximum of the lengths of $u$
and $v$. In particular, when the size of $u$ and $v$ are small enough, the
checking will be done in constant number of steps. Thus, the complexity of the
problem satisfies: $T(m_{k+1})\leq T(\log m_{k})$, where $m_{i}$ denotes the
maximum of the sizes of $u$ and $v$ at step $i$. As the lengths of $u,v$ at
each step are bounded by the length of the whole input string, the lemma
follows. Note that either player can enforce that the algorithm runs in
$\log^{*}n+\mathcal{O}(1)$ steps. The player makes the own markings always
correct and challenges incorrect markings of the opponent at the first error
so that the logarithmic size descent is guaranteed. Challenged correct
markings always cause the size to go down once in a logarithmic scale. ∎

######  Theorem 3.4.

There is an NP-complete problem in $\text{AAL}[\log^{*}n+\mathcal{O}(1)]$.

###### Proof.

Consider any encoding of a SAT formula in conjunctive normal form such that
after each variable occurrence there is a space for a symbol indicating the
truth value of that variable. For example, literals may be represented as $+$
or $-$ followed by a variable name and then a space for the variable’s truth
value, clauses may be separated by semicolons, literals may be separated by
commas and a dot represents the end of the formula. Anke sets a truth value
for each variable occurrence in the formula and a dfa then checks whether or
not between any two semicolons, before the first semicolon and after the last
semicolon there is a true literal; if so, Boris can challenge that two
identical variables received different truth values. It is now player Anke’s
job to prove that the two variables picked by Boris are different. By the Log-
Star Lemma, this verification needs $\log^{*}n+\mathcal{O}(1)$ steps. Hence,
$\text{CNF-SAT}\in\text{AAL}[\log^{*}n+\mathcal{O}(1)]$. ∎

The Log-Star Lemma can also be applied, using a technique similar to that in
the proof of Theorem 3.4, to show that for any $k\geq 3$, the NP-complete
problem $k$-COLOUR of deciding whether any given graph $G$ is colourable with
$k$ colours belongs to $\text{AAL}[\log^{*}n+\mathcal{O}(1)]$. Using a
suitable encoding of nodes, edges and colours as strings, Anke first
nondeterministically assigns any one of $k$ colours to each node and ensures
that no two adjacent nodes are assigned the same colour; Boris then challenges
Anke on whether there are two substrings of the current input that encode the
same node but encode different colours.

The next theorem shows that the class $\text{AAL}[\log^{*}n+\mathcal{O}(1)]$
contains
NLOGSPACE.

######  Theorem 3.5.

$\text{NLOGSPACE}\subseteq\text{AAL}[\log^{*}n+\mathcal{O}(1)]$.

###### Proof.

Consider an NLOGSPACE computation that takes time $n^{c}$. One splits the
input into $\sqrt{n}$ equal-sized blocks, each of which represents the
sequence of configurations of the Turing Machine during an interval of
$\frac{s}{\sqrt{n}}$ steps, where $s$ is the total number of steps on the
input, and Anke guesses for each block the following information:

  * •

The overall number of steps needed, $s$;

  * •

The block number;

  * •

The rounded number of steps done in this block (approximately
$\frac{s}{\sqrt{n}}$ steps);

  * •

The total number of steps done until this block;

  * •

The starting configuration at this block;

  * •

The ending configuration at this block.

Furthermore, the number of variables needed is $2c$ plus a constant.

Boris can now challenge that some configuration is too long or that the number
of digits is wrong or that the information at the end of one block does not
coincide with the information at the start of another block or that initial
and final configurations are not starting and ending configurations or select
a block whose computation has to be checked in the next round, again by
distributing the steps covered in this interval evenly onto $\sqrt{n}$ blocks
in the next variable.

By $\mathcal{O}(c)$ iterations, the distance of steps between two neighbouring
configurations becomes 1. Now Boris can select two pieces of information
copied to check whether they are right or whether the LOGSPACE computation in
the last step read the symbol correctly out of the input word and so on. These
checks can all be done in $\log^{*}n+\mathcal{O}(1)$ steps. ∎

As yet, we have no characterisation of those problems in NP which are in
$\text{AAL}[\mathcal{O}(\log^{*}n)]$ and we think that for each such problem
it might depend heavily on the way the problem is formatted. The reason is
that it may be difficult to even prove whether or not P is contained in
$\text{AAL}[\mathcal{O}(\log^{*}n)]$, due to the following proposition. We
will later show that the class $\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$ which
is obtained from $\text{AAL}[\log^{*}n+\mathcal{O}(1)]$ by starting with one
additional step which generates a variable of polynomially sized length
coincides with PH.

######  Proposition 3.

If $\text{P}\subseteq\text{AAL}[\mathcal{O}(\log^{*}n)]$, then
$\text{P}\subset\text{PSPACE}$.

###### Proof.

By Theorem 3.3 (the condition $f(n)\geq n$ is not necessary for the first
containment relation to hold),
$\text{AAL}[\mathcal{O}(\log^{*}n)]\subseteq\text{DSPACE}[\mathcal{O}((n+\log^{*}(n))\cdot\log^{*}(n))]$.
Moreover, by the space hierarchy theorem [25, Corollary 9.4], one has
$\text{DSPACE}[\mathcal{O}((n+\log^{*}(n))\cdot\log^{*}(n))]\subset\text{DSPACE}[\mathcal{O}(n^{2})]$.
Thus if $\text{P}\subseteq\linebreak[4]\text{AAL}[\mathcal{O}(\log^{*}n)]$,
then $\text{P}\subset\text{DSPACE}[\mathcal{O}(n^{2})]\subset\text{PSPACE}$. ∎

##  4 Polynomial-Size Padded Alternating Automatic Register Machine

An AARM is constrained by the use of bounded automatic relations during each
computation step. As we will prove later in Theorem 5.1, this is a real
limitation, for the use of unbounded automatic relations allows an AARM to
recognise the class of elementary recursive functions. In this section, we
study the effect of allowing a polynomial-size padding to the input of an
Alternating Automatic Register Machine on its time complexity; this new model
of computation will be called a Polynomial-Size Padded Bounded Alternating
Automatic Register Machine (PAARM). The additional feature of a polynomial-
size padding will sometimes be referred to informally as a “booster” step of
the PAARM. Intuitively, padding the input before the start of a computation
allows a larger amount of information to be packed into the register’s
contents during a computation history. We show two contrasting results: on the
one hand, even a booster step does not allow an PAARM with time complexity
$\mathcal{O}(1)$ to recognise non-regular languages; on the other hand, the
class of languages recognised by PAARMs in time $\log^{*}n+\mathcal{O}(1)$
coincides with the polynomial hierarchy.

Formally, a Polynomial-Size Padded Bounded Alternating Automatic Register
Machine (PAARM) $M$ is represented as a quintuple $(\Gamma,\Sigma,A,B,p)$,
where $\Gamma$ is the register alphabet, $\Sigma$ the input alphabet, $A$ and
$B$ are two finite sets of instructions and $p$ is a polynomial. As with an
AARM, the register $R$ initially contains an input string over $\Sigma$, and
$R$’s contents may be changed in response to an instruction,
$J\subseteq\Gamma^{*}\times\Gamma^{*}$ which is a bounded automatic relation.
A computation history of a PAARM with input $w$ for any $w\in\Sigma^{*}$ is
defined in the same way that was done for an AARM, except that the initial
configuration is $(\ell,wv,x)$ for some $I_{\ell}\in A$, some
$x,v\in\Gamma^{*}$, $(wv,x)\in I_{\ell}$, where $v=@^{k}$ for a special symbol
$@\in\Gamma-\Sigma$ and $k\geq p(|w|)$. Think of $@^{k}$ as padding of the
input. Anke’s and Boris’ strategies, denoted by $\mathcal{A}$ and
$\mathcal{B}$ respectively, are defined as before. For any $u\in\Gamma^{*}$, a
winning strategy for Anke with respect to $(M,u)$ is also defined as before.
Given any $w\in\Sigma^{*}$, $M$ accepts $w$ if for every $v\in@^{*}$, with
$|v|\geq p(|w|)$, Anke has a winning strategy with respect to $(M,wv)$.
Similarly, $M$ rejects $w$ if for every $v\in@^{*}$, with $|v|\geq p(|w|)$,
Boris has a winning strategy with respect to $(M,wv)$. Note that the winning
strategies need to be there for every long enough padding. If Anke and Boris
do not satisfy the above properties, then $(A,B)$ is not a valid pair.

######  Definition 2 (Polynomial-Size Padded Bounded Alternating Automatic
Register Machine Complexity).

Let $M=(\Gamma,\Sigma,A,B,p)$ be a PAARM and let $t\in\mathbb{N}_{0}$. For
each $w\in\Sigma^{*}$, $M$ accepts $w$ in time $t$ if for every $v=@^{k}$,
where $k\geq p(|w|)$ and $@\in\Gamma-\Sigma$, Anke has a winning strategy
$\mathcal{A}$ with respect to $(M,wv)$ and for any strategy $\mathcal{B}$
played by Boris, the length of $\mathcal{H}(\mathcal{A},\mathcal{B},M,wv)$ is
not more than $t$.

A PAARM decides a language $L$ in $f(n)$ steps for a function $f$ depending on
the length $n$ of the input if for all $x\in\\{0,1\\}^{n}$, both players can
enforce that the game terminates within $f(n)$ steps by playing optimally and
one player has a winning strategy needing at most $f(n)$ moves and $x\in L$ if
Anke is the player with the winning strategy. $\text{PAAL}[f(n)]$ denotes the
family of languages decided by PAARMs that decide in time $f(n)$.

######  Remark 4.1.

Note that a PAARM-program can trivially simulate an AARM-program by ignoring
the generated padding; thus
$\text{AAL}[\mathcal{O}(f(n))]\subseteq\text{PAAL}[\mathcal{O}(\linebreak[4]f(n))]$.
On the other hand, to simulate a booster step, an AARM-program needs
$\mathcal{O}(p(n))$ steps as each bounded automatic relation step can only
increase the length by a constant.

As with $\text{AAL}[\mathcal{O}(f(n))]$, the class
$\text{PAAL}[\mathcal{O}(f(n))]$ is closed under the usual set-theoretic
Boolean operations as well as regular operations.

######  Theorem 4.2.

Let $\star$ denote any one of the operations union, intersection and
concatenation. For each $L_{1}\in\text{PAAL}[f(n)]$ and each
$L_{2}\in\text{PAAL}[g(n)]$, $L_{1}\star
L_{2}\in\text{PAAL}[\max\\{f(n),g(n)\\}]$ and $L_{1}^{*}\in\text{PAAL}[f(n)]$.
In particular, the languages in $\text{PAAL}[f(n)]$ are closed under union,
intersection, concatenation and Kleene star.

One also has that any language recognised by a PAARM in constant time must be
regular; the converse assertion, that any regular language is recognised by
some PAARM in constant time, follows from an argument similar to that for the
case of AARMs.

######  Theorem 4.3.

For any constant $c$, all languages recognised by a PAARM program in $c$ steps
are regular.

###### Proof.

Let $L$ be any regular language. Then clearly, $\\{x@^{*}:x\in L\\}$ is also
regular. Now suppose that for some polynomial $p$, $B=\\{x@^{k}:k\geq
p(|x|),x\in A\\}$ is regular. Then, $A=\\{x:(\exists j)(\forall k\geq
j)[x@^{k}\in B]\\}$. As $B$ is regular, $A$ is regular as regular sets are
closed under first order quantification. ∎

######  Corollary 2.

$\text{PAAL}[1]=\text{REG}$.

Our main result concerning PAARMs is a characterisation of the polynomial
hierarchy (PH) as the class $\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$.

######  Theorem 4.4.

$\text{PH}=\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$.

To help with the proof, we first extend the Log-Star Lemma as follows. Recall
that a configuration (or instantaneous description) of a Turing Machine is
represented by a string $xqw$, where $q$ is the current state of the machine
and $x$ and $w$ are strings over the tape alphabet, such that the current tape
contents is $xw$ and the current head location is the first symbol of $w$
[16].

######  Lemma 2.

Checking the validity of a Turing Machine step, i.e., whether a configuration
of Turing Machine follows another configuration (given as input, separated by
a special separator symbol) can be done in
$\text{AAL}[\log^{*}n+\mathcal{O}(1)]$, where $n$ is the length of the shorter
of the two configurations.

###### Proof.

Let the input be the two configurations of the Turing Machine, where the
second configuration is supposedly the successive step of the first one and
separated by a separator symbol. Now there are two things that need to be
checked: (1) The configuration is "copied" correctly from the previous step.
Note that a valid Turing Machine transition will change only the cell on the
tape head and/or both of its neighbour; thus "copied" here means the rest of
the tape content should be the same; (2) The local Turing step is correct.

For the first checking, the player who wants to verify, e.g. Anke, will give
the infinite valid marking as used in the Log-Star Lemma. In addition, Anke
also marks the position of the old tape head on the second configuration.
Boris can then challenge the following: (a) The Log-Star Lemma marking is not
valid; (b) The old tape head position is not marked correctly (in the intended
position) on the second configuration; (c) The string in a specified block
differs, but not the symbols around the tape head; (d) The length difference
of the configuration is not bounded by a constant.

Challenge (a) can be done in $\log^{*}n+\mathcal{O}(1)$ steps; this follows
from the Log-Star Lemma. Challenge (b) can also be done in
$\log^{*}n+\mathcal{O}(1)$ steps where both players reduce the block to focus
on that position, and finally check whether it is on the same position or not.
Challenge (c) can also be done in $\log^{*}n+\mathcal{O}(1)$ steps; this
follows again from the Log-Star Lemma. Note that if Boris falsely challenges
that the different symbol is around the tape head, Anke can counter-challenge
by pointing out that at least one of its neighbours is a tape head. For
challenge (d), note that a valid Turing Machine transition will only increase
the length by at most one. Thus, Boris can pinpoint the last character of the
shorter configuration and also its pair on another configuration, then check
whether the longer one is only increased by up to one in length. This again
can be done in $\log^{*}n+\mathcal{O}(1)$ steps.

For the second checking about the correctness of the Turing step, it can be
done in a constant number of checks as a finite automaton can check the
computation and determine whether the Turing steps are locally correct, that
is, each state is the successor state of the previous steps head position and
the symbol to the left or right of the new head position is the symbol
following from the transition to replace the old symbol and so on. Therefore,
all-in-all the validity of a Turing Machine step can be checked in
$\text{AAL}[\log^{*}n+\mathcal{O}(1)]$ steps. ∎

###### Proof of Theorem 4.4.

We first prove that $\text{PAAL}[\log^{*}n+\mathcal{O}(1)]\subseteq\text{PH}$.
Define a binary function Tower recursively as follows:

$\displaystyle\text{Tower}(0,c)$ $\displaystyle=1$
$\displaystyle\text{Tower}(d+1,c)$
$\displaystyle=2^{c\cdot\text{Tower}(d,c)}.$

We prove by induction that for each $c\geq 1$, there is a $c^{\prime}$ such
that for all $d$, $\text{Tower}(d+c^{\prime},1)>\text{Tower}(d,c)$. When
$c=1$, $\text{Tower}(d,c)$ gives the usual definition of the tower function.
In particular, when $c=1$, one has $\text{Tower}(d+1,c)>\text{Tower}(d,c)$ for
all $d$, so the induction statement holds for all $c=1$ and all $d$. Suppose
that $c>1$. Then there is some $c^{\prime}$ large enough so that
$\text{Tower}(c^{\prime},1)>c^{2}=c^{2}\cdot\text{Tower}(0,c)$, and so the
induction statement holds for $d=0$. Assume by induction that $c>1$ and that
$\text{Tower}(c^{\prime\prime}+d,1)>c^{2}\cdot\text{Tower}(d,c)$. Then
$2^{\text{Tower}(c^{\prime\prime}+d,1)}>2^{c^{2}\cdot\text{Tower}(d,c)}\geq(2^{c\cdot\text{Tower}(d,c)})^{c}>c^{2}\cdot
2^{c\cdot\text{Tower}(d,c)}$, and therefore
$\text{Tower}(c^{\prime\prime}+d+1,1)>c^{2}\cdot\text{Tower}(d+1,c)$. This
completes the induction step.

Say that Anke (resp. Boris) wins within $k$ steps iff for some $n\leq k$,
Boris (resp. Anke) starts the $(n+1)$-st turn of the game and he (resp. she)
cannot make a move (it is assumed that both players aim to win and they play
optimally). Suppose that $c$ is the number of states of the automaton $M$
corresponding to the update function for the configuration of an AAL
algorithm. Then there is a dfa of size at most $\text{Tower}(k+2,c)$ that
recognises whether or not a player wins within $k$ steps. We prove this claim
by induction on $k$, showing that there is a dfa of size $\text{Tower}(k+1,c)$
such that for any string $x$, the dfa accepts $x$ iff Anke wins within $k$
steps on input $x$ when she (resp. Boris) starts the game. We can similarly
show that there is a dfa of size $\text{Tower}(k+1,c)$ such that for any
string $x$, the dfa accepts $x$ iff Boris wins within $k$ steps when he (resp.
Anke) starts, so the union of the languages accepted by the two dfa’s is
recognised by a dfa of size at most $\text{Tower}(k+2,c)$.

By the earlier definition of “winning within $k$ steps”, Anke cannot win in
zero steps if she starts the game. If Boris starts, then Anke wins in zero
steps on input $x$ iff there is no $y$ such that $M$ accepts $(x,y)$. The
latter condition can be checked with a dfa of size $2^{c}=\text{Tower}(1,c)$:
one first constructs from $M$ an nfa $M^{\prime}$ that has the same set of $c$
states as $M$ and for any $x\in\Gamma$, $M^{\prime}$ on input $x$ goes from
state $p$ to state $q$ iff there is some $y\in\Gamma$ such that $M$ on input
$conv(x,y)$ goes from state $p$ to state $q$; $M^{\prime}$ is then converted
into another nfa $M^{\prime\prime}$ with the same number of states as
$M^{\prime}$ that accepts the complement of the language accepted by
$M^{\prime}$, after which $M^{\prime\prime}$ can be converted into a dfa of
size $2^{c}$. This verifies the statement for the base case.

Assume inductively that for all $k^{\prime}\leq k$, there is a dfa of size
$\text{Tower}(k^{\prime}+1,c)$ that accepts $x$ iff Anke wins within
$k^{\prime}$ steps on input $x$ when she (resp. Boris) starts. Suppose it is
Anke’s turn and we need to check if she wins within $k+1$ steps. Let $M_{k}$
be a dfa of size $\text{Tower}(k+1,c)$ that accepts $x$ iff Anke wins within
$k$ steps on input $x$ when Boris starts the game. Define an nfa $N$ as
follows. For each state $p$ of $M$, make $\text{Tower}(k+1,c)$ states
$(p,q_{1}),\ldots,(p,q_{\text{Tower}(k+1,c)})$, where
$q_{1},\ldots,q_{\text{Tower}(k+1,c)}$ are the states of $M_{k}$. Then each
state $(p,q)$ on input $x\in\Gamma$ goes to each state
$(p^{\prime},q^{\prime})$ such that for some $y\in\Gamma$, $M$ on input
$conv(x,y)$ goes from state $p$ to state $p^{\prime}$ and $M_{k}$ on input $y$
goes from state $q$ to state $q^{\prime}$. The start state of $N$ is
$(p_{1},q_{1})$, where $p_{1}$ and $q_{1}$ are the start states of $M$ and
$M_{k}$ respectively, and the final states of $N$ are states $(p_{f},q_{f})$
such that $p_{f}$ and $q_{f}$ are final states of $M$ and $M_{k}$
respectively. Then $N$ accepts $x$ iff there is a string $y$ such that $M$
accepts $(x,y)$ and Anke wins within $k$ steps on input $y$ when Boris starts;
in other words, $N$ accepts $x$ iff Anke wins within $k+1$ steps when she
starts with input $x$. The nfa $N$, which is of size
$c\cdot\text{Tower}(k+1,c)$, can then be converted into a dfa $M^{\prime}$ of
size $2^{c\cdot\text{Tower}(k+1,c)}=\text{Tower}(k+2,c)$, as required.

Suppose now that it is Boris’ turn and we need to check if Anke wins within
$k+1$ steps. By the induction hypothesis, there is a dfa $M^{\prime}_{k}$ of
size $\text{Tower}(k+1,c)$ that accepts $x$ iff Anke wins within $k$ steps on
input $x$ when she starts. Let $M^{\prime\prime}_{k}$ be a dfa with the same
number of states as $M^{\prime}_{k}$ that accepts the complement of the
language accepted by $M^{\prime}_{k}$, that is, $M^{\prime\prime}_{k}$ accepts
$x$ iff Anke does not win within $k$ steps on input $x$ when she starts. We
build an nfa $N^{\prime}$ with $c\cdot\text{Tower}(k+1,c)$ states following a
construction similar to that of $N$ in the previous case but replacing $M_{k}$
by $M^{\prime\prime}_{k}$. Then $N^{\prime}$ accepts $x$ iff there is a string
$y$ such that $M$ accepts $conv(x,y)$ and Anke does not win within $k$ steps
on input $y$ when she starts; in other words, $N^{\prime}$ accepts $x$ iff
Anke does not win within $k+1$ steps when Boris starts. The nfa $N^{\prime}$
can be converted into an nfa $N^{\prime\prime}$ with the same number of states
as $N^{\prime}$ that accepts the complement of the language accepted by
$N^{\prime}$ – that is, $N^{\prime\prime}$ accepts $x$ iff Anke wins within
$k+1$ steps when Boris starts. The nfa $N^{\prime\prime}$ can in turn be
converted into a dfa of size
$2^{c\cdot\text{Tower}(k+1,c)}=\text{Tower}(k+2,c)$. This completes the
induction step.

By the preceding result on the function Tower, $\text{Tower}(k+2,c)$ is
bounded by $\text{Tower}(k+c^{\prime},1)$ for some $c^{\prime}$. Thus any
language in $\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$ is recognised in a
constant number of alternating steps plus a predicate that can be computed by
a dfa of size $\text{Tower}(\log^{*}n-3,1)$. This dfa can be computed in
LOGSPACE since $\log^{*}n$ can be computed in logarithmic space. Then one
constructs the dfa by determinizing out the last step until it reaches size
$\log\log n$. This happens only when only constantly many steps are missing by
the above tower result. These constantly many steps can be left as a formula
with alternating quantifiers followed by a dfa computed in logarithmic space
of size $\log\log n$. Thus the formula whether Anke wins is in PH. Similarly
for the formula whether Boris wins and so the overall decision procedure is in
PH.

For the proof that $\text{PH}\subseteq\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$,
we first note that PH can be defined with alternating Turing machines [9]. We
define $\Sigma^{P}_{k}$ to be the class of languages recognised by alternating
Turing Machine in polynomial time where the machine alternates between
existential and universal states $k$ times starting with existential state. We
also define $\Pi^{P}_{k}$ similarly but starting with universal state. PH is
then defined as the union of all $\Sigma^{P}_{k}$ and $\Pi^{P}_{k}$ for all
$k\geq 0$. We now show
$\Sigma^{P}_{k}\cup\Pi^{P}_{k}\subseteq\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$
for any fixed constant $k$. As the alternating Turing Machine runs in
polynomial time on each alternation, the full computation (i.e., sequence of
configurations) in one single alternation can be captured non-
deterministically in $p(m)$ Turing Machine steps, for some polynomial $p$
(which we assume to be bigger than linear), where $m$ is the length of the
configuration at the start of the alternation. In a PAARM-program, Anke first
invokes a booster step to have a string of length at least $p^{k}(n)$. After
that, Boris and Anke will alternately guess the full computation of the
algorithm of length $p(p^{i}(n))$, $i=0,1,\ldots$, in their respective
alternation: Boris guesses the first $p(n)$ computations (the first
alternation), Anke then guesses the next $p(p(n))$ computations on top of it
(the second alternation), etc. In addition, they also mark the position of the
read head and symbol it looks upon in each step. Ideally, the PAARM-program
will take $k$ alternating steps to complete the overall algorithm. Note that a
PAARM can keep multiple variables in the register by using convolution, as
long as the number of variables is a constant. Thus, we could store the $k$
computations in $k$ variables: $v_{1},v_{2},\cdots,v_{k}$. Now each player can
have the following choices of challenges to what the other player did: (1)
Copied some symbol wrongly from the input i.e. in $v_{1}$; (2) Two successive
Turing Machine steps in the computation are not valid (at some $v_{i}$); (3)
The last Turing Machine step on some computation (at some $v_{i}$) does not
follow-up with the first Turing Machine step on the next computation (at
$v_{i+1}$).

All the above challenges can be done in $\log^{*}n+\mathcal{O}(1)$ steps by a
slight modification of Lemma 2. In particular, the third challenge needs one
to compare the first Turing Machine configuration of $v_{i+1}$ and the last
Turing Machine configuration $v_{i}$, which can be done in a way similar to
the proof of Lemma 2. Thus,
$\Sigma^{P}_{k}\cup\Pi^{P}_{k}\subseteq\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$
for every fixed constant $k$, therefore
$PH\subseteq\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$. Corollary 1 implies
$\text{PAAL}[\log^{*}n+\mathcal{O}(1)]\subseteq\text{PSPACE}$. ∎

######  Remark 4.5.

As $\text{PAAL}[\log^{*}n+\mathcal{O}(1)]=\text{PH}$,
$\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$ is closed under Turing reducibility.
Similarly one can show that $\text{PAAL}[\mathcal{O}(\log^{*}n)]$ is closed
under Turing reducibility. After Anke invokes the booster step, Boris will
guess the accepting computation together with all of the oracle answers. Anke
then can challenge Boris on either the validity of the computation (without
challenging the oracle) or challenge one of the oracle answers. Both
challenges can be done in the same fashion as in Theorem 4.4 but the latter
needs one additional step to initiate the challenge of the oracle algorithm.

In addition, we also get the following corollary about polynomial-time Turing
reducibility. We recall that a polynomial-time Turing reduction from problem
$A$ to problem $B$ is an algorithm to solve $A$ in a polynomial number of
steps by making a polynomial number of calls to an oracle solving $B$.

######  Corollary 3.

$\text{PAAL}[\mathcal{O}(\log^{*}n)]$ is closed under polynomial-time Turing
reducibility.

###### Proof.

After Anke invokes the booster step, Boris will guess the accepting
computation together with all of the oracle answers. Anke then can challenge
Boris on either the validity of the computation (without challenging the
oracle) or challenge one of the oracle answers. Both challenges can be done in
the same fashion as in Theorem 4.4 but the latter needs one additional step to
initiate the challenge of the oracle algorithm. ∎

In order to obtain the next corollary, we use the fact that the problem of
deciding $\text{TQBF}_{f}$ – the class of true quantified Boolean formulas
with $\log^{*}n+f(n)+\mathcal{O}(1)$ alternations – does not belong to any
fixed level of the polynomial hierarchy (PH) when PH does not collapse.

######  Corollary 4.

If PH does not collapse and $f$ is a logspace computable increasing and
unbounded function, then
$\text{AAL}[\log^{*}n+f(n)+\mathcal{O}(1)]\not\subseteq\text{PH}$.

###### Proof.

Suppose PH does not collapse. Let $\text{TQBF}_{f}$ be the problem
$\\{\phi:\phi~{}\mbox{is a}$ true fully quantified Boolean formula with
$\log^{*}|\phi|+f(|\phi|)+\mathcal{O}(1)$ alternations $\mbox{of
quantifiers}\\}$, and consider any Boolean formula. The computation with
choice of variables is placed in $f(n)$ rounds of Anke and Boris moves
followed by $\log^{*}n+\mathcal{O}(1)$ moves to evaluate the formula.
Furthermore, if the formula has more than $f(n)$ alternations (and is thus
invalid), any of the two players can challenge this in the first round and
then it takes $\log^{*}n+\mathcal{O}(1)$ rounds to do the logspace computation
of $f(n)$ and to verify that the formula does not belong to $\text{TQBF}_{f}$.
∎

Finally, we observe that if $\text{PH}=\text{PSPACE}$, then (i) by Theorem
4.4, $\text{PH}=\text{PAAL}[\mathcal{O}(\log^{*}n)]=\text{PSPACE}$; (ii) by
Proposition 3, $\text{P}\not\subseteq\text{AAL}[\mathcal{O}(\log^{*}n)]$; thus
$\text{AAL}[\mathcal{O}(\log^{*}n)]$ would be properly contained in
$\text{PAAL}[\mathcal{O}(\log^{*}n)]$.

######  Proposition 4.

If $\text{PH}=\text{PSPACE}$, then
$\text{AAL}[\mathcal{O}(\log^{*}n)]\subset\text{PAAL}[\mathcal{O}(\log^{*}n)]$.

######  Theorem 4.6.

If $f$ is monotonically increasing and unbounded, then
$\text{AAL}[\log^{*}n\linebreak[3]-f(n)]=\text{REG}$.

###### Proof.

Assume that there is an AARM such that for each word $w$ there is either for
Anke or for Boris a winning strategy of $\log^{*}n-f(n)$ steps. Then by the
tower lemma, the resulting size of the dfa is $\mathcal{O}(\log\log n)$ for
almost all $n$ and input words of length $n$. Thus the combined two dfas have
at most size $poly(\log\log n)$ and there is no word $w$ on which not exactly
one accepts in the given time. Now assume that for a given dfa of sufficient
large $n$, there is a word $w$ where neither player succeeds in
$\log^{*}n-f(n)$ rounds, where the $n$ is fixed. Due to the pumping lemma, on
words of arbitary length with this property, one can pump down these words
until they have size below $n$. However, such short words with this property
do not exist by assumption. Thus for this fixed $n$, all words of arbitrary
length are accepted by computations of length $\log^{*}n-f(n)$. Thus the
language is actually in $\text{AAL}[\mathcal{O}(1)]$ and in REG. ∎

##  5 Variants of AARMs and PAARMs

We conclude by discussing the computational power of several variants of AARMs
and PAARMs. The first variant, which was alluded to earlier, is the use of
unbounded automatic relations as update instructions. More precisely, this
means that for the update automaton, there is no constant $c$ such that for
any given input parameter, the difference between the length of each possible
output and that of the input parameter is at most $c$. In contrast to Theorem
3.2, one can show that if an AARM is allowed to use unbounded automatic
relations as update instructions, then the class of languages recognised in
time $\log^{*}n+\mathcal{O}(1)$ is precisely the class E3SETS – the class
$\text{DTIME}(2^{n})\cup\text{DTIME}\left(2^{2^{n}}\right)\cup\text{DTIME}\left(2^{2^{2^{n}}}\right)\cup\ldots$
of all sets computed by an elementary recursive function.

######  Theorem 5.1.

Let $\text{UAAL}[f(n)]$ denote the class of languages recognised in time
$f(n)$ by an AARM that uses unbounded automatic relations as update
instructions. Then $\text{E3SETS}=\text{UAAL}[\log^{*}n+\mathcal{O}(1)]$.

###### Proof.

We first show that
$\text{E3SETS}\subseteq\text{UAAL}[\log^{*}n+\mathcal{O}(1)]$. The main idea
of the proof is based on Lemma 2. As shown in the lemma, an AARM can verify
the validity of a transition between two Turing machine configurations in
$\log^{*}n+\mathcal{O}(1)$ steps, where $n$ is the length of the shorter
configuration. Suppose that the running time of a Turing machine $M$ is at
most $2^{n}$ for any given input of length $n$. The set of all pairs $(x,y)$
such that $y$ represents a (possibly partial) computation history of $M$ is an
automatic relation, and so it can be used to update the (unbounded) AARM
register. For any given input, Anke guesses the full computation history of
the Turing machine; this can be represented by a string of length
$\mathcal{O}(2^{n})$. An argument similar to that in the proof of Lemma 2 then
shows that an AARM can verify in
$\log^{*}\left(\mathcal{O}(2^{n})\right)+\mathcal{O}(1)\leq\log^{*}\left(2^{2^{n}}\right)+\mathcal{O}(1)=\log^{*}n+2+\mathcal{O}(1)=\log^{*}n+\mathcal{O}(1)$
steps whether or not the guessed computation history is valid. A similar
argument applies if the running time of the Turing machine is
$2^{2^{2^{\ldots}}}$ for any given number of exponentiations. One can clock
the steps done with a computation of $\log^{*}n$ for input size $n$ (taking
$\log^{*}n$ steps) and then run a constant number of additional steps, ending
with either Anke winning or Boris winning if the timebound is not kept.

Next, we show that
$\text{UAAL}[\log^{*}n+\mathcal{O}(1)]\subseteq\text{E3SETS}$. Given any
language recognised by an unbounded AARM with time complexity
$\log^{*}n+\mathcal{O}(1)$, as shown in the proof of Theorem 4.4, if $c$ is
the number of states of the update automaton, then a dfa of size at most
$\text{Tower}(\log^{*}n+\mathcal{O}(1),c)$ recognises whether or not a given
player wins within $\log^{*}n+\mathcal{O}(1)$ steps. This dfa can be computed
in $\text{Tower}(\log^{*}n+\mathcal{O}(1),c)$ time, and so the given language
belongs to E3SETS. ∎

######  Remark 1.

Suppose that $f$ is LOGSPACE computable, increasing and unbounded; an example
of such a function is $\log(\log^{*}n)$. Then
$\text{AAL}[\log^{*}n+f(n)+\mathcal{O}(1)]$ contains the class
$\text{NSPACE}[\log n\cdot f(n)]$ and $\text{UAAL}[\log^{*}n+f(n)+1]$ contains
a language not in E3SETS. The first result shows that under the assumption
$\text{PH}=\text{LOGSPACE}$, the class
$\text{AAL}[\log^{*}n+f(n)+\mathcal{O}(1)]$ contains a language outside PH and
but still in PSPACE.

One might be interested in PAARM-programs for which the number of alternations
is constant but a player can do more than one automatic function step in a
single turn. In particular, we can show that if, after the booster step the
number of alternation is just two, then every language in NLOGSPACE, which is
closed under complementation, can be recognised in $\mathcal{O}(\log\log n)$
steps. After padding the input, Boris will run the nondeterministic logspace
computation where he uses location number for the input cell read in a step.
Boris can code this computation in the padded space, where each configuration
step is of logarithmic size. Now Anke verifies the computation, which can be
done in $\mathcal{O}(\log\log n)$ deterministic steps. The idea is to guess
the two symbols from two successive logspace computation steps which
contradict a Turing machine computation (that is, there are errors in the
Turing machine computation). After that, Anke verifies that the positions of
the error symbols are indeed correct by marking off every other symbol in each
logspace sized protocol. The marking off of steps is repeated until all
symbols except the errors in the logspace sized protocols are marked off,
while maintaining the same parities of the errors’ positions. It is easy to
see that Anke needs $\mathcal{O}(\log\log n)$ marking off steps in total, and
one more step to confirm the error.

Another possible variant of an AARM uses transducers as basic operations
instead of bounded automatic relations. We define an Alternating Transducer
Register Machine (ATRM) and a Polynomial-Size Padded Alternating Transducer
Register Machine (PATRM) similarly to an AARM and a PAARM respectively. When
using bounded automatic relations, the “bottleneck” of the computational
power, as shown in this paper, lies in the string comparison, which needs
$\mathcal{O}(\log^{*}n)$ steps by the Log-Star Lemma and its extension. This,
however, does not apply when transducers are used as the string comparison can
be done in constantly many transducer steps. Thus, we can show that not only
an NP-complete problem is recognised by ATRM in constantly many steps but also
PH is contained in PATRM in constantly many steps. In fact, denoting the class
of languages recognised by an ATRM in time $t(n)$ by $\text{UATL}[t(n)]$, one
can show the following.

######  Theorem 5.2.

$\text{UATL}[\mathcal{O}(1)]$ is the union of the classes in the arithmetical
hierarchy.

###### Proof.

We first note that the class R.E. of recursively enumerable languages
coincides with the class of languages obtained by applying constantly many
transducer steps with existential guessing [20, Lemma 3.1]. The alternating
closure then gives that $\text{UATL}[\mathcal{O}(1)]$ is equal to the whole
class of languages in the arithmetical hierarchy. ∎

Note that the arithmetical hierarchy consists of undecidable sets (except for
the lowest level). Thus, owing to Theorem 5.2, we believe that transducers are
too powerful to be used as basic operations and that the use of bounded
automatic relations as basic operations gives a more appropriate model of
computation.

The main results on complexity classes defined by AARMs are summed up in
Figure 1 while those on complexity classes defined by PAARMs are summed up in
Figure 2. For any function $f$, $\text{AAL}[f(n)]$ denotes the class of
languages recognised by an AARM in $f(n)$ time. Arrows are labelled with
references to the corresponding results or definitions; well-known inclusions
can be found in standard textbooks [16, 25] or the Complexity Zoo
(https://complexityzoo.net/Complexity_Zoo). Table 1 also summarises the main
results.

$\text{AAL}[o(\log^{*}n)]$REG$\text{AAL}[\log^{*}n+\mathcal{O}(1)]$CNF-SAT

$\in$

Thm 3.4NLOGSPACE$\bigcup_{k}\text{AAL}[\mathcal{O}(n^{k})]$PSPACE$\text{DSPACE}[\mathcal{O}(n\cdot\log^{*}n)]$Thm 4.6, Thm 3.4Thm 3.3Thm 3.5Thm 4.6Cor 1Defn 1 Figure 1: Relationships between complexity classes/CNF-SAT. A solid arrow from $X$ to $Y$ means that $X$ is a proper subset of $Y$. A double-headed solid arrow between $X$ and $Y$ means that $X$ is equal to $Y$. If $X$ is a subset of $Y$ but it is not known whether they are equal sets, then the arrow is dashed. PH$\text{AAL}[\log^{*}n+\mathcal{O}(1)]$$\text{PAAL}[\log^{*}n+\mathcal{O}(1)]$$\text{AAL}[$o$(\log^{*}n)]$$\text{PAAL}[$o$(\log^{*}n)]$PSPACEREG (assuming PH = LOGSPACE) Prop 4 (assuming $\text{PH}=\text{PSPACE}$) Thm 4.4Thm 4.4Thm 3.4Cor 2Thm 4.6 Figure 2: Relationships between complexity classes. Step Numbers | Criterion
---|---
|  AAL |  PAAL |  UAAL
$\mathcal{O}(1),\,$o$(\log^{*}n)$ |  $=\text{REG}$ |  $=\text{REG}$ |  $=\text{REG}$
$\log^{*}n+\mathcal{O}(1)$ |  $\supseteq\text{LOGSPACE}$ |  $=\text{PH}$ |  $=\text{E3SETS}$
$poly(n)$ |  $=\text{PSPACE}$ |  $=\text{PSPACE}$ |  E3SETS $\subset\text{UAAL}\subset$ E4SETS
Table 1: Summary of results. E3SETS denotes the class of all sets computed by
an elementary function and E4SETS denotes the class of all sets computed by
functions on level 4 of the Grzegorczyk Hierarchy.

## References

  * [1] Scott Aaronson.  $\text{P}\mathop{=}\limits^{?}\text{NP}$.  In John Forbes Nash, Jr., Michael Th. Rassias (Eds.).  Open Problems in Mathematics, pages 1–122.  Cham, Springer Cham.
  * [2] Achim Blumensath.  Automatic structures.  Diploma thesis, RWTH Aachen University, 1999.
  * [3] Achim Blumensath and Erich Grädel.  Automatic structures.  In Proceedings of IEEE Symposium on Logic in Computer Science (LICS), page 51–62, 2000.
  * [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.  On a decision method in restricted second order arithmetic.  Proceedings of the International Congress on Logic, Methodology and Philosophy of Science, Stanford University Press, Stanford, California, 1960.
  * [6] J. Richard Büchi and Lawrence H. Landweber.  Definability in the monadic second order theory of successor.  The Journal of Symbolic Logic, 34:166–170, 1966.
  * [7] John Case, Sanjay Jain, Samuel Seah and Frank Stephan.  Automatic functions, linear time and learning.  Logical Methods in Computer Science, 9(3), 2013.
  * [8] Ashok Chandra, Dexter Kozen and Larry Stockmeyer.  Alternation.  Journal of the Association of Computing Machinery, 28(1):114–133, 1981.
  * [9] Ashok Chandra and Larry Stockmeyer.  Alternation.  In 17th Annual Symposium on Foundations of Computer Science (FOCS 1976), pages 98–108, 1976.
  * [10] Robert Floyd and Donald Knuth.  Addition machines.  SIAM Journal on Computing, 19:329–340, 1990.
  * [11] Martin Fürer.  Alternation and the Ackermann case of the decision problem.  L’Enseignement Mathématique, II(XXVII):137–162, 1981.
  * [12] Ziyuan Gao, Sanjay Jain, Zeyong Li, Ammar Fathin Sabili and Frank Stephan.  Models of computation with automatic functions as primitive steps.  Theoretical Computer Science, 2022.  https://doi.org/10.1016/j.tcs.2022.04.038.
  * [13] Fred Hennie.  One-tape, off-line Turing machine computations.  Information and Control, 8:553–578, 1965.
  * [14] Bernard R. Hodgson.  Théories décidables par automate fini.  PhD thesis, Université de Montréal, 1976.
  * [15] Bernard Hodgson.  Décidabilité par automate fini.  Annales des sciences mathématiques du Québec, 7:39–57, 1983\.
  * [16] John Hopcroft and Jeffrey Ullman.  Introduction to Automata Theory, Languages, and Computation.  Addison-Wesley Publishing Company, Maaschusetts, 1979.
  * [17] 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.
  * [18] Bakhadyr Khoussainov and Anil Nerode.  Automatic presentations of structures.  In International Workshop on Logic and Computational Complexity, volume 960, pages 367–392, 1995.
  * [19] 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.
  * [20] Alexandru Mateescu, Arto Salomaa, Kai Salomaa and Sheng Yu.  P, NP and the Post Correspondence Problem.  Information and Computation, 121(2):135–142, 1995.
  * [21] Michael O. Rabin and Dana Scott.  Finite Automata and their Decision Problems,  IBM Journal of Research and Development, 3:115–125, 1959.
  * [22] 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.
  * [23] Anthony W. Lin and Philipp Rümmer.  Regular model checking revisited.  Technical Report, 2020.
  * [24] John C. Shepherdson and H. E. Sturgis.  Computability of recursive functions.  Journal of the Association of Computing Machinery, 10:217–255, 1963.
  * [25] Michael Sipser.  Introduction to the Theory of Computation.  Cengage Learning, third edition, 2013.
  * [26] Frank Stephan.  Automatic structures – recent results and open questions.  In Third International Conference on Science and Engineering in Mathematics, Chemistry and Physics, volume 622/1 (Paper 012013) of Journal of Physics: Conference Series, 2015.
  * [27] Frank Stephan.  Methods and Theory of Automata and Languages.  School of Computing, National University of Singapore, 2016.