Unambiguous and Co-Nondeterministic Computations of Finite Automata and
Pushdown Automata Families and the Effects of Multiple Counters

Tomoyuki Yamakami111Present Affiliation: Faculty of Engineering, University of
Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan

###### Abstract

Nonuniform families of polynomial-size finite automata and pushdown automata
respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL.
We examine the behaviors of unambiguous and co-nondeterministic computations
produced by such families of automata operating multiple counters. As its
consequences, we obtain various collapses of the complexity classes of
families of promise problems solvable by finite and pushdown automata families
when all valid instances are limited to either polynomially long strings or
unary strings. A key technical ingredient of our proofs is an inductive
counting of reachable vertices of each computation graph of finite and
pushdown automata that operate multiple counters simultaneously.

##  1 Background and Challenging Questions

This section will provide background knowledge on the topics of this work,
raise important open questions, and give their solutions.

###  1.1 Two Important Open Questions in Nonuniform Polynomial State
Complexity Theory

_Nondeterministic computation_ has played an important role in computational
complexity theory as well as automata theory. Associated with such
computation, there are two central and crucial questions to resolve. (i) Can
any co-nondeterministic computation be simulated on an appropriate
nondeterministic machine? (ii) Can any nondeterministic machine be made
unambiguous? In the polynomial-time setting, these questions correspond to the
famous $\mathrm{NP}=?\mathrm{co}\mbox{-}\mathrm{NP}$ and
$\mathrm{NP}=?\mathrm{UP}$ questions. In this work, we attempt to resolve
these questions in the setting of nonuniform polynomial state complexity
classes.

We quickly review the origin and the latest progress of the study of
nonuniform state complexity classes. Apart from a standard uniform model of
finite automata, Berman and Lingas [1] and Sakoda and Sipser [14] considered,
as a “collective” model of computations, nonuniform families of two-way finite
automata indexed by natural numbers and they studied the computational power
of these families of finite automata having _polynomial size_ (i.e., having
polynomially many inner states). Unlike Boolean circuit families, these
automata are allowed to take “arbitrarily” long inputs. Of those families of
polynomial-size finite automata, Sakoda and Sipser focused on the models of
two-way deterministic finite automata (or 2dfa’s, for short) and two-way
nondeterministic finite automata (or 2nfa’s). They introduced the complexity
classes, dubbed as $2\mathrm{D}$ and $2\mathrm{N}$, which consist of all
families of “promise” problems222A _promise problem_ over alphabet $\Sigma$ is
a pair $(A,R)$ satisfying that $A,R\subseteq\Sigma^{*}$ and $A\cap
R=\varnothing$. A _language_ $L$ over $\Sigma$ can be identified with a unique
promise problem having the form $(L,\Sigma^{*}-L)$. solvable respectively by
nonuniform families of polynomial-size 2dfa’s and 2nfa’s. As their natural
extensions, nonuniform families of two-way deterministic pushdown automata (or
2dpda’s) and two-way nondeterministic pushdown automata (or 2npda’s) running
in polynomial time have also been studied lately [17, 21]. Similarly to
$2\mathrm{D}$ and $2\mathrm{N}$, these pushdown automata models induce two
corresponding complexity classes of promise problem families, denoted
respectively by $2\mathrm{DPD}$ and $2\mathrm{NPD}$. Since an introduction of
nonuniform polynomial-size finite automata families, various machine types
(such as deterministic, nondeterministic, alternating, probabilistic, and
quantum) have been studied in depth [3, 8, 9, 10, 11, 16, 17, 18, 19, 21].

An importance of polynomial-size finite automata families comes from their
close connection to decision problems in the nonuniform variants of the log-
space complexity classes $\mathrm{L}$ and $\mathrm{NL}$, when all promised (or
valid) instances given to underlying finite automata are limited to
polynomially long strings (where this condition is referred to as a
_polynomial ceiling_) [10], or when all valid instances are limited to unary
strings [11]. In a similar fashion, $2\mathrm{DPD}$ and $2\mathrm{NPD}$ are
closely related to the nonuniform versions of $\mathrm{LOGDCFL}$ and
$\mathrm{LOGCFL}$ [17] when all valid instances are only polynomially long,
where $\mathrm{LOGCFL}$ (resp., $\mathrm{LOGDCFL}$) is the collection of all
languages log-space many-one reducible to context-free (resp., deterministic
context-free) languages. These strong correspondences to standard
computational complexity theory provide one of the good reasons to investigate
the fundamental properties of various types of nonuniform automata families in
hopes of achieving a better understanding of parallel complexity classes, such
as $\mathrm{L}$, $\mathrm{NL}$, $\mathrm{LOGDCFL}$, and $\mathrm{LOGCFL}$, in
the nonuniform setting.

For nonuniform finite and pushdown automata families, nevertheless, the
aforementioned two central open questions (i)–(ii) correspond to the
$2\mathrm{N}=?2\mathrm{U}$, $2\mathrm{N}=?\mathrm{co}\mbox{-}2\mathrm{N}$,
$2\mathrm{NPD}=?2\mathrm{UPD}$, and
$2\mathrm{NPD}=?\mathrm{co}\mbox{-}2\mathrm{NPD}$ questions. Unfortunately,
these four equalities are not known to hold at this moment. It is therefore
desirable to continue the study on the behaviors of finite and pushdown
automata families in order to deepen our understandings of these machine
families and to eventually resolve those four central questions.

Figure 1: Containments among nonuniform polynomial state complexity classes
shown in this work. Remark that the collapse
$2\mathrm{U}/\mathrm{poly}=2\mathrm{N}/\mathrm{poly}$ comes from [19] and
$2\mathrm{U}/\mathrm{unary}=2\mathrm{N}/\mathrm{unary}=\mathrm{co}\mbox{-}2\mathrm{N}/\mathrm{unary}$
are drawn from [4, 5] in Section 4.

###  1.2 New Challenges and Main Contributions

The primary purpose of this work is to present “partial” solutions to the four
important questions raised in Section 1.1 associated with $2\mathrm{N}$ and
$2\mathrm{NPD}$ by studying the computational power of nonuniform families of
polynomial-size finite and pushdown automata in depth.

In the course of our study, we further look into the key role of “counters”,
each of which is essentially a stack manipulating only a single symbol, say,
“$1$” except for the bottom marker $\bot$. Since the total number of $1$s in a
counter can be viewed as a natural number, the counter is able to “count”, as
its name suggests. For the first time, we supplement multiple counters to the
existing models of nonuniform finite and pushdown automata families. We remark
that, for short runtime computation, counters are significantly weaker333With
exponential overhead, 2-counter automata can simulate a Turing machine [12] in
functionality than full-scale stacks. Even though, the proper use of counters
can help us not only trace the tape head location but also count the number of
steps.

By appending multiple counters to finite and pushdown automata, we obtain the
machine models of _counter automata_ and _counter pushdown automata_. Two
additional complexity classes, $2\mathrm{NCT}_{k}$ and $2\mathrm{NPDCT}_{k}$
are naturally obtained by taking families of polynomial-size nondeterministic
counter automata and counter pushdown automata operating $k$ counters.

The use of multiple counters makes it possible to show in Section 3 that
$2\mathrm{N}$ and $\mathrm{co}\mbox{-}2\mathrm{N}$ coincide and that 4
counters are enough (namely,
$2\mathrm{NCT}_{4}=\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}$). This result further
leads to the equivalence between $\mathrm{co}\mbox{-}2\mathrm{N}$ and
$2\mathrm{N}$ in Section 4.3 when all promise problem families are restricted
to having polynomial ceilings. Under the same restriction, we will show that
$\mathrm{co}\mbox{-}2\mathrm{NPD}$ and $2\mathrm{NPD}$ also coincide. Our
results are briefly summarized in Fig. 1, in which the suffix
“$/\mathrm{poly}$” refers to the polynomial ceiling restriction and the suffix
“$/\mathrm{unary}$” refers to the restriction to unary input strings. To
obtain some of the equalities in the figure, we will exploit a close
connection between _parameterized decision problems_ and families of promise
problems, which was first observed in [18] and then fully developed in [17,
19, 21].

##  2 Preliminaries: Notions and Notation

We briefly explain fundamental notions and notation used in the rest of this
work.

###  2.1 Numbers, Languages, and Pushdown Automata

The set of all _natural numbers_ (including $0$) is denoted $\mathbb{N}$ and
the positive-integer set $\mathbb{N}-\\{0\\}$ is expressed as
$\mathbb{N}^{+}$. Given two integers $m$ and $n$ with $m\leq n$, the notation
$[m,n]_{\mathbb{Z}}$ denotes the _integer set_ $\\{m,m+1,m+2,\ldots,n\\}$. As
a special case, we write $[n]$ for $[1,n]_{\mathbb{Z}}$ when
$n\in\mathbb{N}^{+}$. In this work, all _polynomials_ must have nonnegative
coefficients and all _logarithms_ are taken to the base $2$ with the notation
$\log{0}$ being treated as $0$. The _power set_ of a set $S$ is denoted ${\cal
P}(S)$.

Given an alphabet $\Sigma$ and a number $n\in\mathbb{N}$, the notation
$\Sigma^{n}$ (resp., $\Sigma^{\leq n}$) denotes the set of all strings over
$\Sigma$ of length exactly $n$ (resp., at most $n$). The _empty string_ is
always denoted $\varepsilon$.

As a basic machine model, we use _two-way nondeterministic finite automata_
(or 2nfa’s, for short) that make neither $\varepsilon$-moves444An
$\varepsilon$-move of an automaton refers to the case where the automaton
makes a transition without reading any input symbol. nor stationary moves.
This means that input tape heads of 2nfa’s always move to adjacent tape cells
without stopping at any tape cells. Given a finite automaton $M$, the _state
complexity_ $sc(M)$ of $M$ is the total number of inner states used for $M$.

Another important machine model is _two-way nondeterministic pushdown
automata_ (or 2npda’s) $N$ over alphabet $\Sigma$ with a stack alphabet
$\Gamma$ including the bottom marker $\bot$. Notice that $N$ is allowed to
make _$\varepsilon$ -moves_ whereas 2nfa’s make no $\varepsilon$-moves. The
_stack-state complexity_ $ssc(N)$ of $N$ denotes the product
$|Q|\cdot|\Gamma^{\leq e}|$, which turns out to be a useful complexity measure
[17, 21], where $Q$ is a set of inner states and $e$ is the _push size_ (i.e.,
the maximum length of pushed strings into the stack at any single push
operation).

A _counter_ is a special kind of (pushdown) stack whose alphabet consists only
of a single symbol, say, “$1$” except for $\bot$. In this work, we freely
equip multiple counters to finite automata and pushdown automata. These
machines are respectively called _counter automata_ and _counter pushdown
automata_. We conveniently abbreviate a _two-way nondeterministic counter
automaton_ as a 2ncta and a _two-way nondeterministic counter pushdown
automaton_ as a 2npdcta.

###  2.2 Promise Problems and Nonuniform Families

Unlike the notion of languages, _promise problems_ over alphabet $\Sigma$ are
formally of the form $(A,R)$ satisfying that $A,R\subseteq\Sigma^{*}$ and
$A\cap R=\varnothing$. We say that a 1nfa (1ncta, 1npda, or 1npdcta) $M$
_solves_ $(A,R)$ if (i) for any $x\in A$, $M$ accepts $x$ (i.e., there exists
an accepting computation path of $M$ on $x$) and (ii) for any $x\in R$, $M$
rejects $x$ (i.e., all computation paths of $M$ on $x$ are rejecting). Any
string in $A\cup R$ is said to be _promised_ or _valid_. Since we do not
impose any further condition on all strings outside of $A\cup R$, it suffices
to focus only on the promised strings in our later discussion.

For any nondeterministic machine models discussed in Section 2.1, a machine is
said to be _unambiguous_ if it has at most one accepting computation path on
each promised instance. For other instances, there is no restriction on the
number of accepting/rejecting computation paths.

Throughout this work, we consider any “family” ${\cal L}$ of promise problems
$(L_{n}^{(+)},L_{n}^{(-)})$ over a common fixed alphabet $\Sigma$ indexed by
natural numbers $n\in\mathbb{N}$. Such a family ${\cal L}$ is said to have a
_polynomial ceiling_ if there exists a polynomial $p$ such that
$L_{n}^{(+)}\cup L_{n}^{(-)}\subseteq\Sigma^{\leq p(n)}$ holds for all indices
$n\in\mathbb{N}$. Given a complexity class ${\cal C}$ of families of promise
problems, if we restrict our attention to only promise problem families in
${\cal C}$ having a polynomial ceiling, then we obtain the subclass of ${\cal
C}$, expressed as ${\cal C}/\mathrm{poly}$. Moreover, when all promise
problems are restricted to the ones over unary alphabets, we obtain the
subclass ${\cal C}/\mathrm{unary}$. Those exotic notations come from [8, 9]
and are adopted in [11, 16, 17, 18, 19, 21].

A family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of 2nfa’s (resp., 2npda’s)
over alphabet $\Sigma$ is of _polynomial size_ if there exists a polynomial
$p$ satisfying $sc(M_{n})\leq p(n)$ (resp., $ssc(M_{n})\leq p(n)$) for all
$n\in\mathbb{N}$. Similar notions are definable for other machine models, such
as 2dfa’s, 2ncta’s, 2npda’s, 2npdcta’s, and 2dpdcta’s.

Given a family ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of
promise problems, a family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of
nondeterministic machines, and a polynomial $p$, we say that $M_{n}$ _solves
$(L_{n}^{(+)},L_{n}^{(-)})$ within time $p(n,|x|)$_ if (1) for any $x\in
L_{n}^{(+)}$, there exists an accepting computation path of $M_{n}$ on $x$
having length at most $p(n,|x|)$ and (2) for any $x\in L_{n}^{(-)}$, there is
no accepting computation path of $M_{n}$ on $x$ but there is a rejecting
computation path of having length at most $p(n,|x|)$. Moreover, ${\cal M}$ is
said to _solve ${\cal L}$ in polynomial time_ if there is a polynomial $p$
such that, for all indices $n\in\mathbb{N}$, $M_{n}$ solves
$(L_{n}^{(+)},L_{n}^{(-)})$ within time $p(n,|x|)$. We define $2\mathrm{N}$ as
the collection of all families of promise problems solvable by nonuniform
families of polynomial-size 2nfa’s in polynomial time.555As shown by Geffert
et al. [4], in the case of 2dfa’s and 2nfa’s, removing the “polynomial time”
requirement does not change the definitions of $2\mathrm{D}$ and
$2\mathrm{N}$. By replacing these 2nfa’s with 2dfa’s, 2dpda’s, and 2npda’s, we
respectively obtain $2\mathrm{D}$, $2\mathrm{DPD}$, and $2\mathrm{NPD}$. For
any $k\in\mathbb{N}^{+}$, we further define $2\mathrm{NCT}_{k}$ and
$2\mathrm{NPDCT}_{k}$ using $k$-counter 2ncta’s and $k$-counter
2npdcta’s,666We remark that, with the use of multiple counters, it is possible
to force 2ncta’s and 2npdcta’s to halt within polynomial time on _all
computation paths_. respectively. When $k=1$, we tend to drop the subscript
“$k$” and write, e.g., $2\mathrm{NCT}$ instead of $2\mathrm{NCT}_{1}$. The
notation $\mathrm{co}\mbox{-}{\cal L}$ denotes
$\\{(L_{n}^{(-)},L_{n}^{(+)})\\}_{n\in\mathbb{N}}$. Given a complexity class
${\cal C}$ of promise problem families, such as $2\mathrm{N}$ and
$2\mathrm{NPD}$, $\mathrm{co}\mbox{-}{\cal C}$ expresses the class
$\\{\mathrm{co}\mbox{-}{\cal L}\mid{\cal L}\in{\cal C}\\}$. It follows that
$2\mathrm{D}=\mathrm{co}\mbox{-}2\mathrm{D}$ and
$2\mathrm{DPD}=\mathrm{co}\mbox{-}2\mathrm{DPD}$.

In addition, the use of unambiguous 1nfa’s and unambiguous 2npda’s introduces
the complexity classes $2\mathrm{U}$ and $2\mathrm{UPD}$, respectively, and
their multi-counter variants $2\mathrm{UCT}_{k}$ and $2\mathrm{UPDCT}_{k}$. It
then follows that $2\mathrm{D}\subseteq 2\mathrm{DPD}\subseteq
2\mathrm{UPD}\subseteq 2\mathrm{UPDCT}$ and $2\mathrm{U}\subseteq
2\mathrm{N}\subseteq 2\mathrm{NCT}\subseteq 2\mathrm{NPD}\subseteq
2\mathrm{NPDCT}$.

###  2.3 Reducing the Number of Counters in Use

It is possible to reduce the number of counters in use on multi-counter
automata and multi-counter pushdown automata. Minsky [12] earlier demonstrated
how to simulate a Turing machine on a 2-counter automaton with exponential
overhead. Since we cannot use the same simulation technique due to its large
overhead, we need to take another, more direct approach toward
$2\mathrm{NCT}_{k}$ and $2\mathrm{NPDCT}_{k}$. Even without the requirement of
polynomial ceiling, it is possible in general to reduce the number of counters
in use down to “4” for 2ncta’s and “3” for 2npdcta’s as shown below.

###### Proposition 2.1

For any constants $k,k^{\prime}\in\mathbb{N}$ with $k\geq 4$ and
$k^{\prime}\geq 3$, $2\mathrm{NCT}_{k}=2\mathrm{NCT}_{4}$ and
$2\mathrm{NPDCT}_{k^{\prime}}=2\mathrm{NPDCT}_{3}$. The same holds for the
deterministic case.

A core of the proof of Proposition 2.1 is the following lemma on the
simulation of every pair of counters by a single counter with the heavy use of
an appropriately defined “pairing” function. Let ${\cal
M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ denote any polynomial-size family of 2ncta’s
or of 2npdcta’s running in time, in particular, $(n|x|)^{t}$ for a fixed
constant $t\in\mathbb{N}^{+}$. This ${\cal M}$ satisfies the following lemma.

###### Lemma 2.2

There exists a fixed deterministic procedure by which any single move of
push/pop operations of two counters of $M_{n}$ can be simulated by a series of
operations with one counter with the help of 3 extra counters. These extra 3
counters are emptied after each simulation and thus they are reusable for any
other purposes. If we freely use a stack during this simulation procedure,
then we need only two extra counters instead of three. The state complexity of
the procedure is $n^{O(1)}$.

Proof of Proposition 2.1.  We first look into the case of $2\mathrm{NCT}_{k}$
for every $k\geq 4$ and we wish to prove in the following that
$2\mathrm{NCT}_{k}\subseteq 2\mathrm{NCT}_{4}$.

Let ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ denote any nonuniform family of
polynomial-size $k$-counter 2ncta’s running in polynomial time, where $M_{n}$
has the form
$(Q_{n},\Sigma,k,\\{1,\bot\\},\delta_{n},q_{0,n},\bot,Q_{acc,n},Q_{rej,n})$.
Take two polynomials $p_{1}$ and $p_{2}$ such that $|Q_{n}|\leq p_{1}(n)$ and
$M_{n}$ halts within time $p_{2}(n,|x|)$ for any $n\in\mathbb{N}$ and any
$x\in\Sigma^{*}$.

In what follows, we fix $n$ and $x$ arbitrarily. We abbreviate
$p_{2}(n,p_{1}(n))+1$ as $p$ and consider the pairing function $\langle
i_{1},i_{2}\rangle_{p}$ defined as $\langle i_{1},i_{2}\rangle_{p}=i_{1}\cdot
p+i_{2}$ for any $i_{1},i_{2}\in[0,p-1]_{\mathbb{Z}}$.

We first group together all counters into pairs and apply Lemma 2.2 to
simulate each pair of counters by a single counter with the help of three
extra reusable counters, say, CT1–CT3. We repeat this process until there
remains one counter other than CT1–CT3. Since there are only four counters
left unremoved, this shows that $2\mathrm{NCT}_{k}\subseteq
2\mathrm{NCT}_{4}$.

Next, we intend to show that $2\mathrm{NPDCT}_{k^{\prime}}\subseteq
2\mathrm{NPDCT}_{3}$ for any $k^{\prime}\geq 3$. In this case, we follow the
same argument as described above by removing counters except for CT1–CT3.
Finally, four counters are left unremoved. As shown in Lemma 2.2, we can
further reduce the number of counters to three. This is because we can utilize
a stack, which is originally provided by an underlying pushdown automaton.
$\Box$

It is not clear that “4” and “3” are the smallest numbers supporting
Proposition 2.1 for 2ncta’s and 2npdcta’s, respectively. We may conjecture
that $2\mathrm{NCT}_{i}\neq 2\mathrm{NCT}_{i+1}$ and $2\mathrm{NPDCT}_{j}\neq
2\mathrm{NPDCT}_{j+1}$ for all $i\in[3]$ and $j\in[2]$.

##  3 Reachability with No Polynomial Ceiling Bounds

Let us consider the question raised in Section 1.1 on the closure property
under complementation, namely, the
$2\mathrm{N}=?\mathrm{co}\mbox{-}2\mathrm{N}$ question. Unfortunately, we do
not know its answer. With the presence of “counters”, however, it is possible
to provide a complete solution to this question.

###### Theorem 3.1

For any constant $k\geq 4$, $\mathrm{co}\mbox{-}2\mathrm{NCT}_{k}\subseteq
2\mathrm{NCT}_{4}$.

###### Corollary 3.2

$2\mathrm{NCT}_{4}=\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}$.

A key to the proof of Theorem 3.1 is the following lemma.

###### Lemma 3.3

For any constant $k\in\mathbb{N}^{+}$,
$\mathrm{co}\mbox{-}2\mathrm{NCT}_{k}\subseteq 2\mathrm{NCT}_{5k+12}$.

The proof of Theorem 3.1 is described as follows. By Proposition 2.1, it
suffices to consider the case of $k=4$. We then obtain
$\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}\subseteq 2\mathrm{NCT}_{32}$ by Lemma
3.3. Proposition 2.1 again leads to $2\mathrm{NCT}_{32}\subseteq
2\mathrm{NCT}_{4}$. Therefore, $\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}\subseteq
2\mathrm{NCT}_{4}$ follows. By taking the “complementation” of the both sides
of this inclusion, we also obtain
$2\mathrm{NCT}_{4}\subseteq\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}$. Corollary
3.2 is thus obtained.

To prove Lemma 3.3, we wish to use an algorithmic technique known as
_inductive counting_. This intriguing technique was discovered independently
by Immerman [6] and Szelepcsényi [15] in order to prove that
$\mathrm{NL}=\mathrm{co}\mbox{-}\mathrm{NL}$.

For the description of the proof of Lemma 3.3, we introduce the following
special notion of (internal) configurations for a family
$\\{M_{n}\\}_{n\in\mathbb{N}}$ of the $n$th $k$-counter 2ncta $M_{n}$ running
in time polynomial, say, $r(n,|x|)$. A _configuration_ of $M_{n}$ on input $x$
is of the form $(q,l,\vec{m})$ with $q\in Q$, $l\in[0,|x|+1]_{\mathbb{Z}}$,
and $\vec{m}=(m_{1},m_{2},\ldots,m_{k})\in\mathbb{N}^{k}$. This form indicates
that $M_{n}$ is in inner state $q$, scanning the $l$th tape cell, and
$M_{n}$’s $i$th counter holds a number $m_{i}$ for each index $i\in[k]$. We
abbreviate as $CONF_{n,|x|}$ the configuration space
$Q_{n}\times[0,|x|+1]_{\mathbb{Z}}\times[0,r(n,|x|)]_{\mathbb{Z}}^{k}$. Given
two configurations $c_{1}$ and $c_{2}$ of $M_{n}$ on $x$, the notation
$c_{1}\vdash_{x}c_{2}$ means that $c_{2}$ is “reachable” from $c_{1}$ by
making a single move of $M_{n}$ on $x$. We abbreviate as
$c_{1}\vdash_{x}^{t-1}c_{t}$ a chain of transitions
$c_{1}\vdash_{x}c_{2}\vdash_{x}\cdots\vdash_{x}c_{t}$. Moreover,
$\vdash^{*}_{x}$ denotes the transitive closure of $\vdash_{x}$.

Proof of Lemma 3.3.  Let $k\in\mathbb{N}^{+}$ and let ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be any family in
$\mathrm{co}\mbox{-}2\mathrm{NCT}_{k}$. Since $\mathrm{co}\mbox{-}{\cal L}\in
2\mathrm{NCT}_{k}$, there is a nonuniform family
$\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size $k$-counter 2ncta’s that
solves $\mathrm{co}\mbox{-}{\cal L}$ in polynomial time. Since the runtime of
$M_{n}$ is polynomially bounded for all valid instances $x$, there is a
polynomial $r$ such that the value $r(n,|x|)$ upper-bounds the runtime of
$M_{n}$ on valid input $x$ for any index $n\in\mathbb{N}$. Note that each
counter must hold only a number between $0$ and $r(n,|x|)$.

Our goal is to build a $(5k+12)$-counter 2ncta $P_{n}$, which solves the
promise problem $(L_{n}^{(+)},L_{n}^{(-)})$ for each index $n\in\mathbb{N}$. A
basic idea of constructing such a machine $P_{n}$ is to provide a procedure of
deciding nondeterministically whether $M_{n}$ rejects input $x$; in other
words, whether all computation paths of $M_{n}$ on $x$ reach non-accepting
inner states. For this purpose, we need to “count” the number of rejecting
computation paths of $M_{n}$ on $x$. If this number matches the total number
of computation paths, then we know that $M_{n}$ rejects $x$. From this follows
${\cal L}\in 2\mathrm{NCT}_{5k+12}$.

We arbitrarily fix a number $n$ and a valid input $x$. In what follows, we
deal with configurations of the form $(q,l,\vec{m})$ in $CONF_{n,|x|}$. It is
important to note that, with the use of additional $k+1$ counters, we can
“enumerate” all elements in $CONF_{n,|x|}$, ensuring a linear order on
$CONF_{n,|x|}$. This fact makes it possible for us to select the elements of
$CONF_{n,|x|}$ sequentially one by one in the following construction of
$P_{n}$. For each number $i\in[0,r(n,|x|)]_{\mathbb{Z}}$, we define
$V_{i}=\\{(q,l,\vec{m})\in
CONF_{n,|x|}\mid(q_{0},0,\vec{0})\vdash_{x}^{i}(q,l,\vec{m})\\}$ and set
$N_{i}=|V_{i}|$. We wish to calculate the value $N_{r(n,|x|)}$ by inductively
calculating $N_{i}$ for each $i\in[0,r(n,|x|)]_{\mathbb{Z}}$ using additional
counters.

Hereafter, we intend to calculate $N_{i}$ inductively in the following
fashion. Let $i$ denote an arbitrary number in $[0,r(n,|x|)]_{\mathbb{Z}}$. We
need another counter, say, CT1 to remember the value $i$. Since $0\leq
N_{i}\leq|CONF_{n,|x|}|=|Q_{n}|(r(n,|x|)+1)^{k}(|x|+2)$, we need to remember
the value $N_{i}$ using an additional counter, say, CT2. When $i=0$, $N_{0}$
clearly equals $1$. Assume that $1\leq i\leq r(n,|x|)$. We use two parameters
$c$ and $d$, ranging over $[0,|CONF_{n,|x|}|]_{\mathbb{Z}}$, whose values are
stored into two extra counters, say, CT3 and CT4. Furthermore, we need to
remember the current location of $M_{n}$’s tape head using another counter,
say, CT5. To hold $\vec{m}$, we only need extra $k$ counters, called
eCT1–eCT$k$. During the following inductive procedure, we must empty the
additionally introduced counters and reuse them to avoid a continuous
introduction of new counters.

Initially, we set $c=0$ in CT3. In a sequential way described above, we pick
the elements $(q,l,\vec{m})$ from $CONF_{n,|x|}$ one by one. We store
$(q,l,\vec{m})$ into CT5 and eCT1–eCT$k$, where $q$ is remembered in the form
of inner states. For each element $(q,l,\vec{m})$, we select
nondeterministically either the process (1) or the process (2) described
below, and execute it. After all elements $(q,l,\vec{m})$ are selected
sequentially and either (1) or (2) is executed properly, we define
$\hat{N}_{i}$ to be the current value of $c$ (by removing the content of CT3
into CT2 to empty CT3).

To utilize the stored values of $i$, $N_{i}$, $l$, and $\vec{m}$, however, we
need to copy them into extra $k+3$ counters, say, CT1′, CT2′, CT5′, and
eCT1′–eCT$k^{\prime}$ (by bypassing another extra counter, say, CT10) and use
these copied counters in the following process.

(1) Choose nondeterministically a computation path, say, $\gamma$ of $M_{n}$
on $x$ and check whether $(q_{0},0,\vec{0})\vdash_{x}^{i}(q,l,\vec{m})$ is
true on this path $\gamma$. This is done by first returning a tape head to the
start cell (i.e., the leftmost tape cell), preparing additional $k+1$
counters, say, CT5′′ and eCT1′′–eCT$k^{\prime\prime}$, emptying them, and then
simulating $M_{n}$ on $x$ for the first $i$ steps using CT1′ and these new
counters. Let $(p,h,\vec{s})$ denote the configuration reached after $i$ steps
from $(q_{0},0,\vec{0})$. We then compare between $(p,h,\vec{m})$ and
$(q,l,\vec{m})$ by simultaneously decrementing the corresponding counters
CT5′, eCT1′–eCT$k^{\prime}$, CT5′′, and eCT1′′–eCT$k^{\prime\prime}$. If the
comparison is successful, then we increment the value of $c$ by one.
Otherwise, we reject $x$ and halt.

(2) Initially, we set $d=0$ in CT4. In the aforementioned sequential way, we
pick the elements $(p,h,\vec{s})$ from $CONF_{n,|x|}$ one by one. For each
selected element $(p,h,\vec{s})$, we need to store $(p,h,\vec{s})$ in other
$k+1$ counters and copy their contents into the existing $k+1$ counters (as in
(1)). For the simulation of $M_{n}$, to avoid introducing more counters, we
reuse CT5′′ and eCT1′′–eCT$k^{\prime\prime}$. Follow nondeterministically a
computation path, say, $\xi$ and check whether
$(q_{0},0,\vec{0})\vdash_{x}^{i-1}(p,h,\vec{s})$ is true on $\xi$. As in (1),
this is done by the use of the counters. If this is true, then we increment
$d$ by one. We then check whether $(p,h,\vec{s})\vdash_{x}(q,l,\vec{m})$. If
so, reject $x$ and halt. After all elements $(p,h,\vec{s})$ are properly
processed without halting, we check whether $d$ matches $\hat{N}_{i-1}$. If
not, reject $x$ and halt.

Assume that the above inductive procedure ends after $i$ reaches $r(n,|x|)$.
We sequentially pick all elements $(z,t,\vec{e})$ from
$(Q_{n}-Q_{acc,n})\times[0,|x|+1]_{\mathbb{Z}}\times[0,r(n,|x|)]_{\mathbb{Z}}^{k}$
one by one, store one into CT5 and eCT1–eCT$k$, and conduct the same procedure
as described above, except for the following point. At the end of the
procedure, instead of defining $\hat{N}_{r(n,|x|)+1}$, we check whether $c$
equals $\hat{N}_{r(n,|x|)}$. If so, then we accept $x$; otherwise, we reject
$x$.

It is possible to prove that, in a certain computation path of $P_{n}$, the
value $\hat{N}_{i}$ correctly represents $N_{i}$ for any index
$i\in[0,r(n,|x|)]_{\mathbb{Z}}$. The correctness of the value of $\hat{N}_{i}$
can be proven by induction on $i$ as in [6]. Therefore, $P_{n}$ correctly
solves $(L_{n}^{(+)},L_{n}^{(-)})$. The above procedure can be implemented on
an appropriate 2ncta with the total of $5(k+1)+7$ counters. Thus, ${\cal L}$
belongs to $2\mathrm{NCT}_{5k+12}$. $\Box$

##  4 Effects of Polynomial Ceiling Bounds

We will see significant effects given by the restriction onto polynomially
long input strings.

###  4.1 Elimination of Counters

In Section 2.3, we have discussed how to reduce the number of counters down to
three or four. In the presence of polynomial ceilings, it is further possible
to eliminate all counters from counter automata and counter pushdown automata.

###### Theorem 4.1

Let $k$ be an arbitrary constant in $\mathbb{N}^{+}$. (1)
$2\mathrm{NCT}_{k}/\mathrm{poly}=2\mathrm{N}/\mathrm{poly}$. (2)
$2\mathrm{NPDCT}_{k}/\mathrm{poly}=2\mathrm{NPD}/\mathrm{poly}$. The same
statement holds even if underlying nondeterministic machines are changed to
deterministic ones.

###### Proof.

Here, we prove only (2) since the proof of (1) is in essence similar. Since
$2\mathrm{NPD}\subseteq 2\mathrm{NPDCT}_{k}$ for all $k\geq 1$, we obtain
$2\mathrm{NPD}/\mathrm{poly}\subseteq 2\mathrm{NPDCT}_{k}/\mathrm{poly}$. We
next show that $2\mathrm{NPDCT}_{k}/\mathrm{poly}\subseteq
2\mathrm{NPD}/\mathrm{poly}$. Consider any family ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of promise problems in
$2\mathrm{NPDCT}_{k}/\mathrm{poly}$ over alphabet $\Sigma$. There exists a
polynomial $p$ satisfying $L_{n}^{(+)}\cup L_{n}^{(-)}\subseteq\Sigma^{\leq
p(n)}$ for all $n\in\mathbb{N}$. Take any family
$\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 2npdcta’s that solves ${\cal
L}$ with $k$ counters in time polynomial in $(n,|x|)$. Let $q$ denote a
polynomial such that, for any $n\in\mathbb{N}$ and any promised input
$x\in\Sigma^{*}$, $q(n,|x|)$ upper-bounds the runtime of $M_{n}$ on $x$. Since
$p$ is a ceiling, all the $k$ counters of $M_{n}$ hold the number at most
$q(n,p(n))$ on all “valid” instances. Define $r(n)=q(n,p(n))$. Since $r$ is a
polynomial, it is possible to express the contents of the $k$ counters in the
form of inner states. Therefore, without using any counter, we can simulate
$M_{n}$ on the input $x$ by running an appropriate 2npda whose stack-state
complexity is polynomially bounded. This implies that ${\cal L}\in
2\mathrm{NPD}/\mathrm{poly}$.

The last part of the theorem follows in a similar way as described above. ∎

###### Corollary 4.2

(1) If $2\mathrm{DCT}_{4}=2\mathrm{NCT}_{4}$, then
$\mathrm{L}/\mathrm{poly}=\mathrm{NL}/\mathrm{poly}$. (2) If
$2\mathrm{DPDCT}_{3}=2\mathrm{NPDCT}_{3}$, then
$\mathrm{LOGDCFL}/\mathrm{poly}=\mathrm{LOGCFL}/\mathrm{poly}$.

The proof of this corollary is obtainable from Theorem 4.1 as well as the
following two results. (i)
$2\mathrm{D}/\mathrm{poly}=2\mathrm{N}/\mathrm{poly}$ implies
$\mathrm{L}/\mathrm{poly}=\mathrm{NL}/\mathrm{poly}$ [10]. (ii)
$2\mathrm{DPD}/\mathrm{poly}=2\mathrm{NPD}/\mathrm{poly}$ implies
$\mathrm{LOGDCFL}/\mathrm{poly}=\mathrm{LOGCFL}/\mathrm{poly}$ [17].

###  4.2 Unambiguity of 2N and 2NPD

We turn our attention to the question of whether we can make 2nfa’s and
2npda’s unambiguous. In the simple case of unary inputs, let us recall the
result of Geffert and Pighizzini [5], who showed that any 2nfa can be
simulated by an appropriate 2ufa with a polynomial increase of the state
complexity of the 2nfa. From this follows the collapse of
$2\mathrm{N}/\mathrm{unary}$ to $2\mathrm{U}/\mathrm{unary}$ as stated in Fig.
1.

Next, we look into a relationship between $2\mathrm{NPD}$ and $2\mathrm{UPD}$
when all promise problems are limited to having polynomial ceilings.

###### Theorem 4.3

(1) $2\mathrm{N}/\mathrm{poly}=2\mathrm{U}/\mathrm{poly}$. (2)
$2\mathrm{NPD}/\mathrm{poly}=2\mathrm{UPD}/\mathrm{poly}$.

The statement (1) of Theorem 4.3 was already proven in [19]. However, we do
not know whether $2\mathrm{N}=2\mathrm{U}$ or
$2\mathrm{NCT}_{k}=2\mathrm{UCT}_{k}$ even though (1) holds.

Hereafter, we focus on proving the statement (2) of Theorem 4.3. For this
purpose, we use the nonuniform (i.e., the Karp-Lipton style polynomial-size
advice-enhanced extension) computational model of _two-way auxiliary
unambiguous pushdown automata_ (or aux-2upda’s), which are 2upda equipped with
auxiliary work tapes, and the complexity class
$\mathrm{UAuxPDA,\\!\\!TISP}(n^{O(1)},\log{n})/\mathrm{poly}$ induced by
aux-2upda’s777This means aux-2upda’s running in $n^{O(1)}$ time using
$O(\log{n})$ work space on any promised instance of the form $(x,h(|x|))$,
where $h$ is a polynomially-bounded advice function. that run in time
$n^{O(1)}$ using work space $O(\log{n})$ together with polynomially-bounded
advice functions. Reinhardt and Allender [13] demonstrated that
$\mathrm{LOGCFL}/\mathrm{poly}$ coincides with
$\mathrm{UAuxPDA,\\!\\!TISP}(n^{O(1)},\log{n})/\mathrm{poly}$.

Discovered in [16] was a close connection between parameterized decision
problems and families of promise problems solvable by certain finite automata
families. We quickly review necessary terminology, introduced in [20] and
fully developed in [16, 17, 18, 19, 21]. A _parameterized decision problem_
over alphabet $\Sigma$ is of the form $(L,m)$, where $L\subseteq\Sigma^{*}$
and $m(\cdot)$ is a size parameter (i.e., a mapping of $\Sigma^{*}$ to
$\mathbb{N}$). Any size parameter computable by an appropriate log-space
deterministic Turing machine (DTM) is called a _logspace size parameter_. A
typical example is $m_{\parallel}$ defined as $m_{\parallel}(x)=|x|$ for all
$x\in\Sigma^{*}$. All parameterized decision problems whose size parameters
$m$ satisfy $|x|\leq q(m(x))$ for all $x\in\Sigma^{*}$ form the complexity
class $\mathrm{PHSP}$, where $q$ is an appropriate polynomial depending only
on $m$. See [18] for more information. The notation
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$ denotes the collection of
all parameterized decision problems $(L,m)$ with logspace size parameters $m$
solvable by _two-way auxiliary nondeterministic pushdown automata_ (or
aux-2npda’s) running in time $m(x)^{O(1)}$ and space $O(\log{m(x)})$ with the
use of advice strings of length polynomial in $m(x)$, where $x$ represents an
“arbitrary” input. As a special case, if $m$ is fixed to $m_{\parallel}$, we
obtain $\mathrm{LOGCFL}/\mathrm{poly}$.

Let ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ and ${\cal
K}=\\{({\cal K}_{n}^{(+)},{\cal K}_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be any two
families of promise problems over a common alphabet $\Sigma$. Given a
parameterized decision problem $(L,m)$ over $\Sigma$, we say that ${\cal L}$
is _induced from_ $(L,m)$ if, for any index $n\in\mathbb{N}$,
$L_{n}^{(+)}=L\cap\Sigma_{(n)}$ and
$L_{n}^{(-)}=\overline{L}\cap\Sigma_{(n)}$, where
$\Sigma_{(n)}=\\{x\in\Sigma^{*}\mid m(x)=n\\}$. The family ${\cal K}$ is said
to be an _extension_ of ${\cal L}$ if $L_{n}^{(+)}\subseteq K_{n}^{(+)}$ and
$L_{n}^{(-)}\subseteq K_{n}^{(-)}$ hold for any $n\in\mathbb{N}$. Moreover,
${\cal L}$ is _L-good_ if the set $\\{1^{n}\\#x\mid n\in\mathbb{N},x\in
L_{n}^{(+)}\cup L_{n}^{(-)}\\}$ belongs to $\mathrm{L}$. A collection ${\cal
F}$ of promise problem families is _L-good_ if all elements of ${\cal F}$ has
an $\mathrm{L}$-good extension in ${\cal F}$. From ${\cal L}$, we define
$K_{n}^{(+)}=\\{1^{n}\\#x\mid x\in L_{n}^{(+)}\\}$ and
$K_{n}^{(-)}=\\{1^{n}\\#x\mid x\notin L_{n}^{(+)}\\}\cup S_{n}$ for any
$n\in\mathbb{N}$, where $\Sigma_{\\#}=\Sigma\cup\\{\\#\\}$ and
$S_{n}=\\{z\\#x\mid
z\in\Sigma^{n}-\\{1^{n}\\},x\in(\Sigma_{\\#})^{*}\\}\cup\Sigma^{n}$. Finally,
we say that $(K,m)$ is _induced from_ ${\cal L}$ if
$K=\bigcup_{n\in\mathbb{N}}K_{n}^{(+)}$ and
$m:(\Sigma_{\\#})^{*}\to\mathbb{N}$ satisfies that (i) $m(w)=n$ holds for any
string $w$ of the form $1^{n}\\#x$ with $x\in L_{n}^{(+)}\cup L_{n}^{(-)}$ and
(ii) $m(w)=|w|$ holds for all other strings $w$. Note that $\overline{K}$
equals $\bigcup_{n\in\mathbb{N}}K_{n}^{(-)}$. See [18] for more information.
The $\mathrm{L}$-goodness can be proven for $2\mathrm{NPD}/\mathrm{poly}$,
$2\mathrm{UPD}/\mathrm{poly}$, and
$\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$ in a way similar to [17].
Since the set $\\{1^{n}\\#x\mid x\in\mathbb{N},x\in L_{n}^{(+)}\cup
L_{n}^{(-)}\\}$ does not alter by exchanging between $L_{n}^{(+)}$ and
$L_{n}^{(-)}$, the $\mathrm{L}$-goodness of
$\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$ follows immediately.

In the rest of this work, we succinctly write $\mathrm{LOGUCFL}/\mathrm{poly}$
for $\mathrm{UAuxPDA,\\!\\!TISP}(n^{O(1)},\log{n})/\mathrm{poly}$. Notice that
$\mathrm{LOGCFL}$ is characterized in terms of polynomial-time log-space
aux-2npda’s. This characterization holds even under the presence of advice.

Proof of Theorem 4.3.  The statement (1) was already proven in [19]. Thus, we
focus on the statement (2) and provide its proof. Since unambiguity is a
special case of nondeterminism, $2\mathrm{UPD}$ is obviously contained in
$2\mathrm{NPD}$. In what follows, we intend to prove that
$2\mathrm{NPD}/\mathrm{poly}\subseteq 2\mathrm{UPD}$ because this statement is
logically equivalent to
$2\mathrm{NPD}/\mathrm{poly}=2\mathrm{UPD}/\mathrm{poly}$.

To avoid a cumbersome repetition of the description of “parameterized decision
problems” and “logspace size parameters” given in pages 9–10, we skip the
whole description here.

In the rest of this proof, we succinctly write
$\mathrm{LOGUCFL}/\mathrm{poly}$ for
$\mathrm{UAuxPDA,\\!\\!TISP}(n^{O(1)},\log{n})/\mathrm{poly}$. Let us assert
the following claim concerning $\mathrm{LOGUCFL}/\mathrm{poly}$ and
$2\mathrm{UPD}$. A similar claim was proven first in [18], and later proven in
[19] for $\mathrm{UL}/\mathrm{poly}$ and in [17] for
$\mathrm{LOGCFL}/\mathrm{poly}$. Refer to these references for more precise
information.

###### Claim 4.4

(i) $\mathrm{LOGCFL}\subseteq\mathrm{LOGUCFL}/\mathrm{poly}$ implies
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$.
(ii)
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$
implies $2\mathrm{NPD}/\mathrm{poly}\subseteq 2\mathrm{UPD}$.

It is known that
$\mathrm{LOGCFL}/\mathrm{poly}\subseteq\mathrm{LOGUCFL}/\mathrm{poly}$ [13].
From this fact, Claim 4.4 therefore concludes that
$2\mathrm{NPD}/\mathrm{poly}\subseteq 2\mathrm{UPD}$, as requested.

Hereafter, we wish to give the proof of Claim 4.4. Let us begin with the proof
of Claim 4.4(i). Assume that
$\mathrm{LOGCFL}\subseteq\mathrm{LOGUCFL}/\mathrm{poly}$ and let $(L,m)$
denote any parameterized decision problem in
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$. Since
$m$ is polynomially honest, there is a polynomial $q$ satisfying $|x|\leq
q(m(x))$ for all $x$. We intend to turn $(L,m)$ into its corresponding
language, say, $P$ as follows. Since
$(L,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$, there are a
polynomially-bounded advice function $h$ and an aux-2npda $M_{0}$ such that
$M_{0}$ recognizes the language $\\{(x,h(m(x)))\mid x\in L\\}$ in time
$m(x)^{O(1)}$ and space $O(\log{m(x)})$. We define
$L_{n}^{(+)}=L\cap\Sigma_{(n)}$ and
$L_{n}^{(-)}=\overline{L}\cap\Sigma_{(n)}$, where
$\Sigma_{(n)}=\\{x\in\Sigma^{*}\mid m(x)=n\\}$. The desired set $P$ is defined
by $P=\\{(x,1^{t})\mid x\in L,t\in\mathbb{N},m(x)\leq t\\}$. To show that
$P\in\mathrm{LOGCFL}/\mathrm{poly}$, it suffices to consider the following
algorithm: on input $(x,1^{t})$, first check whether $m(x)\leq t$ using log
space. Otherwise, reject the input immediately. We then run $M_{0}$ on
$(x,h(m(x)))$ by the help of advice string, which must have the form
$h(0)\\#h(1)\\#\cdots\\#h(t)$. Our assumption then guarantees that $P$ belongs
to $\mathrm{LOGUCFL}/\mathrm{poly}$. From this $P$, it is possible to define
an advice function $g$ and an aux-2npda $N$ for which $L$ is recognized by $N$
in time $m(x)^{O(1)}$ using space $O(\log{m(x)})$ with the help of $g$. Hence,
we can conclude that $(L,m)$ falls in
$\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$.

We then prove Claim 4.4(ii). A key to its proof is the following two
statements (a)–(b), which are analogous to [18, Proposition 5.1]. Let ${\cal
L}$ denote any family $\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of
promise problems, let $L$ and $K$ be any two decision problems (or
equivalently, languages) over the common alphabet $\Sigma$, and let $m$ denote
any logspace size parameter over $\Sigma$. We write $({\cal C},{\cal D})$ for
any element of the set
$\\{(\mathrm{LOGCFL},2\mathrm{NPD}),(\mathrm{LOGUCFL},2\mathrm{UPD})\\}$.

  1. (a)

If ${\cal L}$ is induced from $(L,m)$, then
$(L,m)\in\mathrm{para}\mbox{-}{\cal C}/\mathrm{poly}\cap\mathrm{PHSP}$ iff
${\cal L}\in{\cal D}/\mathrm{poly}$.

  2. (b)

If ${\cal L}$ is $\mathrm{L}$-good and $(K,m)$ is induced from ${\cal L}$,
then $(K,m)\in\mathrm{para}\mbox{-}{\cal C}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in{\cal D}/\mathrm{poly}$.

Note that the validity of the above statements (a)–(b) for the first case of
${\cal C}=\mathrm{LOGCFL}$ and ${\cal D}=2\mathrm{NPD}$ comes directly from
[17, Proposition 4.3]. The second case of ${\cal C}=\mathrm{LOGUCFL}$ and
${\cal D}=2\mathrm{UPD}$ will be handled later.

Meanwhile, we set our goal to deriving $2\mathrm{NPD}/\mathrm{poly}\subseteq
2\mathrm{UPD}$ from the inclusion
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$.
Take any family ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of
promise problems in $2\mathrm{NPD}/\mathrm{poly}$ over alphabet $\Sigma$ and
take the parameterized decision problem $(K,m)$ induced from ${\cal L}$. As
remarked earlier, all elements in $2\mathrm{NPD}$ are $\mathrm{L}$-good. By
(b), it thus follows that
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in 2\mathrm{NPD}/\mathrm{poly}$. Hence, we obtain
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$. If
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$,
then we conclude that
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}$. By (b) again,
${\cal L}$ must belong to $2\mathrm{UPD}/\mathrm{poly}$. Therefore, Claim
4.4(ii) is true.

The remaining task is to prove the statement (a)–(b) for the second case of
${\cal C}=\mathrm{LOGUCFL}$ and ${\cal D}=2\mathrm{UPD}$. Following an
argument of [17, 18, 19], we first show (a). Assume that ${\cal L}$ is induced
from $(L,m)$ and that $(L,m)$ is in
$\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}\cap\mathrm{PHSP}$. Take a
polynomially-bounded advice function $h$ and an aux-2upda $M$ that recognizes
$L$ in polynomial time using log space with the help of the advice string
$h(m(x))$ given according to each input $x$. Since
$L_{n}^{(+)}=L\cap\Sigma_{(n)}$ and $L_{n}^{(-)}=\overline{L}\cap\Sigma_{(n)}$
(where $\Sigma_{(n)}=\\{x\mid m(x)=n\\}$), it is possible to convert $M$ with
$h$ working on all inputs $x$ in $\Sigma_{(n)}$ into an appropriate 2nfa
$N_{n}$ by integrating $h$ into $M$ and simulating it on the 2nfa $N_{n}$
using polynomially many inner states. A detailed description is given as a
supporting lemma in [18, Lemma 5.3] for a conversion of a single (quantum)
Turing machine into another two-way (quantum) finite automaton. Notice that
$N_{n}$ is unambiguous since so is $M$ with $h$. Thus, ${\cal L}$ belongs to
$2\mathrm{UPD}$.

On the contrary, assume that ${\cal L}\in 2\mathrm{UPD}/\mathrm{poly}$. Take a
family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 2upda’s
solving ${\cal L}$ in polynomial time. We wish to convert ${\cal M}$ into a
single polynomial-time log-space aux-2upda $N$ solving $(L,m)$ with a
polynomially-bounded advice function $h$. A detailed description is given in
[18, Lemma 5.2] for a conversion of a two-way (quantum) finite automata family
into a (quantum) Turing machine as a supporting lemma.

Next, we intend to prove (b). Assume that ${\cal L}$ is $\mathrm{L}$-good and
$(K,m)$ is induced from ${\cal L}$. If $(K,m)$ is in
$\mathrm{para}\mbox{-}\mathrm{LOGUCFL}/\mathrm{poly}\cap\mathrm{PHSP}$, then
there are a polynomially-bounded advice function $h$ and an aux-2upda $M$ that
solves $(K,m)$ in $O(m(z)^{k})$ time using $O(\log{m(z)})$ space on every
input $z$ of the form $(x,h(m(x)))$. Let $n$ denote an arbitrary number in
$\mathbb{N}$. In a way similar to a conversion of an advised (quantum) Turing
machine into a family of two-way (quantum) finite automata in the proof of
[18, Lemma 5.5], we introduce the following 2nfa $N_{n}$.

We first encode a content of the work tape into an inner state and
approximately define a new transition function of $N_{n}$ so that it simulates
$M$ step by step. Consider arbitrary $n$ and $x\in\Sigma_{(n)}$. Since $m$ and
$h$ are polynomially bounded, the space usage of $N_{n}$ is upper bounded by
$O(\log{m(z)})\subseteq O(\log{n})$ and the runtime of $N_{n}$ is upper-
bounded by $O(m(z)^{k})\subseteq O(n^{k^{\prime}})$ for an appropriate
constant $k^{\prime}>k$. By the definition of $N_{n}$, the family
$\\{N_{n}\\}_{n\in\mathbb{N}}$ turns out to solve ${\cal L}$. We thus conclude
that ${\cal L}\in 2\mathrm{U}/\mathrm{poly}$.

On the contrary, assume that ${\cal L}\in 2\mathrm{UPD}/\mathrm{poly}$. Take a
family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 2upda’s that
solves ${\cal L}$ in polynomial time. Since
$K=\bigcup_{n\in\mathbb{N}}K_{n}^{(+)}$ with $K_{n}^{(+)}=\\{1^{n}\\#x\mid
x\in L_{n}^{(+)}\\}$, we can construct an aux-2npda $N$ that takes an input of
the form $1^{n}\\#x$ and simulates $M_{n}$ on $x$, where a code of $M_{n}$ is
given as an advice string to $N$. Since $M_{n}$ is unambiguous, so is $N_{n}$.
Given in [18] is a detailed description of a conversion of a (quantum) finite
automata family into a (quantum) Turing machine. $\Box$

###  4.3 Complementation of 2N and 2NPD

Let us look into the question raised in Section 1.1 concerning the closure
property under complementation. Geffert, Mereghetti, and Pighizzini [4]
earlier demonstrated a simulation of a “complementary” 2nfa (i.e., a two-way
finite automaton making co-nondeterministic moves) on unary inputs by another
2nfa with a polynomial increase of the state complexity. From this fact, we
instantly conclude that $\mathrm{co}\mbox{-}2\mathrm{N}/\mathrm{unary}$
coincides with $2\mathrm{N}/\mathrm{unary}$ as stated in Fig. 1.

Hereafter, we discuss the complementation closures of $2\mathrm{N}$ and
$2\mathrm{NPD}$ when all valid instances are limited to polynomially long
strings.

###### Theorem 4.5

(1) $2\mathrm{N}/\mathrm{poly}=\mathrm{co}\mbox{-}2\mathrm{N}/\mathrm{poly}$.
(2)
$2\mathrm{NPD}/\mathrm{poly}=\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$

It is important to note that the statement (1) does not require the use of
parameterized version of $\mathrm{NL}$. This is rather a direct consequence of
Theorem 3.1 (and Corollary 3.2) together with Theorem 4.1(1). This fact
exemplifies the strength of the additional use of counters provided to
underlying finite automata.

Proof of Theorem 4.5.  (1) By Corollary 2.2,
$2\mathrm{NCT}_{4}=\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}$ follows. Thus, we
conclude that
$2\mathrm{NCT}_{4}/\mathrm{poly}=\mathrm{co}\mbox{-}2\mathrm{NCT}_{4}/\mathrm{poly}$.
By Theorem 4.1(2), we then obtain
$2\mathrm{N}/\mathrm{poly}=\mathrm{co}\mbox{-}2\mathrm{N}/\mathrm{poly}$.

(2) The proof for $\mathrm{LOGCFL}=\mathrm{co}\mbox{-}\mathrm{LOGCFL}$ in [2]
can be carried over to the advised setting, and thus we obtain
$\mathrm{LOGCFL}/\mathrm{poly}=\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$.
In analogy to Claim 4.4, we intend to assert the following claim.

###### Claim 4.6

(i) $\mathrm{co}\mbox{-}\mathrm{LOGCFL}\subseteq\mathrm{LOGCFL}/\mathrm{poly}$
implies
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$.
(ii)
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$
implies $\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}\subseteq
2\mathrm{NPD}$.

Claim 4.6 clearly leads to
$2\mathrm{NPD}/\mathrm{poly}=\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$
from
$\mathrm{LOGCFL}/\mathrm{poly}=\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$.

The proof of Claim 4.6 is in essence similar to that of Claim 4.4. Let us
prove Claim 4.6(i). Assume that
$\mathrm{co}\mbox{-}\mathrm{LOGCFL}\subseteq\mathrm{LOGCFL}/\mathrm{poly}$. It
is easy to show that this implies
$\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}=\mathrm{LOGCFL}/\mathrm{poly}$.
Let $(L,m)$ denote any parameterized decision problem in
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
over alphabet $\Sigma$. Since $(\overline{L},m)$ belongs to
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$, there are a
polynomially-bounded advice function $h$ and an advised aux-2npda $M$ such
that $M$ recognizes $L$ in time $m(x)^{O(1)}$ using space $O(\log{m(x)})$ with
the help of $h$, where $x$ is a “symbolic” input. We define
$P=\\{(x,1^{t})\mid x\in L,t\in\mathbb{N},m(x)\leq t\\}$. By following an
argument similar to the one for Claim 4.4(i), we can conclude that
$\overline{P}\in\mathrm{LOGCFL}/\mathrm{poly}$. Hence, $P$ belongs to
$\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$. By our assumption, $P$
also belongs to $\mathrm{LOGCFL}/\mathrm{poly}$. Take another advised
aux-2npda $N$ that recognizes $L$ in time $n^{O(1)}$ and space $O(\log|x|)$
with an appropriate polynomially-bounded advice function. Since $m$ is
polynomially honest, $(L,m)$ must belong to
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$.

We next target Claim 4.6(ii). Recall the statements (a)–(b) introduced in the
proof of Theorem 4.3(2). We claim that the same statements (a)–(b) holds for
any element $({\cal C},{\cal D})$ of the set
$\\{(\mathrm{LOGCFL},2\mathrm{NPD}),(\mathrm{co}\mbox{-}\mathrm{LOGCFL},\mathrm{co}\mbox{-}2\mathrm{NPD})\\}$.
Let ${\cal L}$ denote any family
$\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of promise problems, let
$L$ and $K$ be any two decision problems over the common alphabet $\Sigma$,
and let $m$ denote any logspace size parameter over $\Sigma$.

  1. (a)

If ${\cal L}$ is induced from $(L,m)$, then
$(L,m)\in\mathrm{para}\mbox{-}{\cal C}/\mathrm{poly}\cap\mathrm{PHSP}$ iff
${\cal L}\in{\cal D}/\mathrm{poly}$.

  2. (b)

If ${\cal L}$ is $\mathrm{L}$-good and $(K,m)$ is induced from ${\cal L}$,
then $(K,m)\in\mathrm{para}\mbox{-}{\cal C}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in{\cal D}/\mathrm{poly}$.

With the use of the statements (a)–(b), Claim 4.6(ii) is proven as follows.
Assume that
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$.
Take an arbitrary family ${\cal L}$ in
$\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$. This family induces the
parameterized decision problem $(K,m)$. Recall that
$\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$ is $\mathrm{L}$-good. There
exists an $\mathrm{L}$-good extension of ${\cal L}$. By the nature of
$\mathrm{L}$-goodness, the existence of such an extension implies that ${\cal
L}$ itself is also $\mathrm{L}$-good. It then follows by (b) with ${\cal
C}=\mathrm{co}\mbox{-}\mathrm{LOGCFL}$ and ${\cal
D}=\mathrm{co}\mbox{-}2\mathrm{NPD}$ that
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$. Since ${\cal
L}\in\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$, we thus conclude that
$(K,m)$ is in
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$. Our
assumption then yields the containment
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$. By (b) with
${\cal C}=\mathrm{LOGCFL}$ and ${\cal D}=2\mathrm{NPD}$, it follows that
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in 2\mathrm{NPD}/\mathrm{poly}$. Thus, ${\cal L}$ must belong to
$2\mathrm{NPD}/\mathrm{poly}$.

The remaining task is to show the validity of the statements (a)–(b) for any
element $({\cal C},{\cal D})$ of the set
$\\{(\mathrm{LOGCFL},2\mathrm{NPD}),(\mathrm{co}\mbox{-}\mathrm{LOGCFL},\mathrm{co}\mbox{-}2\mathrm{NPD})\\}$.
The first case of ${\cal C}=\mathrm{LOGCFL}$ and ${\cal D}=2\mathrm{NPD}$
comes from [17, Proposition 4.3]. We thus intend to prove the second case of
${\cal C}=\mathrm{co}\mbox{-}\mathrm{LOGCFL}$ and ${\cal
D}=\mathrm{co}\mbox{-}2\mathrm{NPD}$. We first show (a). Assume that ${\cal
L}$ is induced from $(L,m)$ in
$\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$.
Since $\mathrm{co}\mbox{-}{\cal L}$ is also induced from $(\overline{L},m)$
and $(\overline{L},m)$ belongs to
$\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$, it
follows from the first case that
$(\overline{L},m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff $\mathrm{co}\mbox{-}{\cal L}\in 2\mathrm{NPD}/\mathrm{poly}$. By taking
complementation, we obtain the desired relationship stated in (a).

Next, we wish to prove (b). Assume that ${\cal L}$ is $\mathrm{L}$-good and
$(K,m)$ is induced from ${\cal L}$. By the nature of $\mathrm{L}$-goodness,
$\mathrm{co}\mbox{-}{\cal L}$ is also $\mathrm{L}$-good. We succinctly write
$\Sigma_{(n)}$ for $L_{n}^{(+)}\cup L_{n}^{(-)}$ for any $n\in\mathbb{N}$.
Since ${\cal L}$ is $\mathrm{L}$-good, there is a polynomial-time log-space
DTM $N_{0}$ that recognizes $\\{1^{n}\\#x\mid
n\in\mathbb{N},x\in\Sigma_{(n)}\\}$. For any $n\in\mathbb{N}$, let
$S_{n}=\\{z\\#x\mid
z\in\Sigma^{n}-\\{1^{n}\\},x\in(\Sigma_{\\#})^{*}\\}\cup\Sigma^{n}$. Note
that, by the definition of $K$, $K$ has the form
$\bigcup_{n\in\mathbb{N}}K_{n}^{(+)}$, where $K_{n}^{(+)}=\\{1^{n}\\#x\mid
x\in L_{n}^{(+)}\\}$ and $K_{n}^{(-)}=\\{1^{n}\\#x\mid x\notin
L_{n}^{(+)}\\}\cup S_{n}$. It then follows that
$\overline{K}=\bigcup_{n\in\mathbb{N}}K_{n}^{(-)}$. Let $(P,m)$ denote the
parameterized decision problem induced from $\mathrm{co}\mbox{-}{\cal L}$.
Similarly to $K$, $P$ equals $\bigcup_{n\in\mathbb{N}}P_{n}^{(+)}$ with
$P_{n}^{(+)}=\\{1^{n}\\#x\mid x\in L_{n}^{(-)}\\}$ and
$P_{n}^{(-)}=\\{1^{n}\\#x\mid x\notin L_{n}^{(-)}\\}\cup S_{n}$. By applying
[17, Proposition 4.3] to $\mathrm{co}\mbox{-}{\cal L}$, it follows that
$(P,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff $\mathrm{co}\mbox{-}{\cal L}\in 2\mathrm{NPD}/\mathrm{poly}$. By taking
complementation, we conclude that
$(\overline{P},m)\in\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$. Therefore, it
suffices to verify that (*)
$(\overline{K},m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff
$(P,m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$,
because this equivalence shows that
$(\overline{K},m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff $\mathrm{co}\mbox{-}{\cal L}\in 2\mathrm{NPD}/\mathrm{poly}$. Therefore,
we conclude that
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{co}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in\mathrm{co}\mbox{-}2\mathrm{NPD}/\mathrm{poly}$.

Hereafter, we intend to verify (*) by assume that $m$ is polynomially honest.
Assume that
$(\overline{K},m)\in\mathrm{para}\mbox{-}\mathrm{LOGCFL}/\mathrm{poly}$. It is
not difficult to show that
$(K_{n}^{(-)}-S_{n})\cap\Sigma_{(n)}=P_{n}^{(+)}\cap\Sigma_{(n)}$
($=\\{1^{n}\\#x\mid x\in\Sigma_{(n)}\cap L_{n}^{(-)}\\}$) for any
$n\in\mathbb{N}$. Therefore, if $x\in\bigcup_{n\in\mathbb{N}}\Sigma_{(n)}$,
then it follows that $x\in\overline{K}-\bigcup_{n\in\mathbb{N}}S_{n}$ iff
$x\in P$. Since $\bigcup_{n\in\mathbb{N}}S_{n}$ is in $\mathrm{L}$, this
equivalence relation leads to (*), as requested.

This completes the entire proof of the theorem. $\Box$

## References

  * [1] P. Berman and A. Lingas. On complexity of regular languages in terms of finite automata. Report 304, Inst. Comp. Sci., Polish Academy of Science, Warsaw (1977)
  * [2] A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM J. Comput. 18 (1989) 559–578.
  * [3] V. Geffert. An alternating hierarchy for finite automata. Theor. Comput. Sci. 445, 1–24 (2012).
  * [4] V. Geffert, C. Mereghetti, and G. Pighizzini. Complementing two-way finite automata. Inf. Comput. 205, 1173–1187 (2007)
  * [5] V. Geffert and G. Pighizzini. Two-way unary automata versus logarithmic space. Inform. Comput. 209, 1016–1025 (2011)
  * [6] N. Immerman. Nondeterministic space is closed under complement. SIAM J. Comput. 17 (1988) 935–938.
  * [7] J. Hartmanis and S. R. Mahaney. Languages simultaneously complete for one-way and two-way log-tape automata. SIAM J. Comput. 10, 383–390 (1981)
  * [8] C. A. Kapoutsis. Size complexity of two-way finite automata. In the Proc. of DLT 2009, LNCS, vol. 5583, pp. 47–66, Springer (2009)
  * [9] C. A. Kapoutsis. Minicomplexity. J. Automat. Lang. Combin. 17 (2012) 205–224.
  * [10] C. A. Kapoutsis. Two-way automata versus logarithmic space. Theory Comput. Syst. 55 (2014) 421–447.
  * [11] C. A. Kapoutsis and G. Pighizzini. Two-way automata characterizations of L/poly versus NL. Theory Comput. Syst. 56 (2015) 662–685.
  * [12] M. L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliff, NJ (1967)
  * [13] K. Reinhardt and E. Allender. Making nondeterminism unambiguous. SIAM J. Comput. 29, 1118–1181 (2000)
  * [14] W. J. Sakoda and M. Sipser. Nondeterminism and the size of two-way finite automata. In the Proc. of STOC 1978, pp. 275–286 (1978)
  * [15] R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279–284.
  * [16] T. Yamakami. State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. Theor. Comput. Sci. 798, 2–22 (2019)
  * [17] T. Yamakami. Parameterizations of logarithmic-space reductions, stack-state complexity of nonuniform families of pushdown automata, and a road to the LOGCFL$\subseteq$LOGDCFL/poly question. Available at arXiv:2108.12779, 2021.
  * [18] T. Yamakami. Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Inf. Comput. 286, article 104783 (2022)
  * [19] T. Yamakami. Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata. In the Proc. of RP 2022, LNCS, vol. 13608, pp. 77–92, Springer (2022). A corrected and expanded version is available at arXiv:2311.09979.
  * [20] T. Yamakami. The 2CNF Boolean formula satsifiability problem and the linear space hypothesis. J. Comput. Syst. Sci. 136, 88–112 (2023)
  * [21] T. Yamakami. Power of counting by nonuniform families of polynomial-size finite automata. In the Proc. of FCT 2023, LNCS, vol. 14292, pp. 421–435, Springer (2023). A corrected and expanded version is available at arXiv:2310.18965.