
We present new results on realtime alternating, private alternating, and
quantum alternating automaton models. Firstly, we show that the emptiness
problem for alternating onecounter automata on unary alphabets is undecidable.
Then, we present two equivalent definitions of realtime private alternating
finite automata (PAFAs). We show that the emptiness problem is undecidable for
PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages,
including the unary squares language, which seems to be difficult even for some
classical counter automata with twoway input. Regarding quantum finite
automata (QFAs), we show that the emptiness problem is undecidable both for
universal QFAs on general alphabets, and for alternating QFAs with two
alternations on unary alphabets. On the other hand, the same problem is
decidable for nondeterministic QFAs on general alphabets. We also show that the
unary squares language is recognized by alternating QFAs with two alternations.

Quantum computing is a new model of computation, based on quantum physics.
Quantum computers can be exponentially faster than conventional computers for
problems such as factoring. Besides fullscale quantum computers, more
restricted models such as quantum versions of finite automata have been
studied. In this paper, we survey various models of quantum finite automata and
their properties. We also provide some open questions and new directions for
researchers.
Keywords: quantum finite automata, probabilistic finite automata,
nondeterminism, bounded error, unbounded error, state complexity, decidability
and undecidability, computational complexity

We show that oneway quantum onecounter automaton with zeroerror is more
powerful than its probabilistic counterpart on promise problems. Then, we
obtain a similar separation result between Las Vegas oneway probabilistic
onecounter automaton and oneway deterministic onecounter automaton.
We also obtain new results on classical counter automata regarding language
recognition. It was conjectured that oneway probabilistic one blindcounter
automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz:
Superiority of oneway and realtime quantum machines. RAIRO  Theor. Inf. and
Applic. 46(4): 615641 (2012)]. We show that this conjecture is false, and also
show several separation results for blind/nonblind counter automata.

We examine inkdots placed on the input string as a way of providing advice to
finite automata, and establish the relations between this model and the
previously studied models of advised finite automata. The existence of an
infinite hierarchy of classes of languages that can be recognized with the help
of increasing numbers of inkdots as advice is shown. The effects of different
forms of advice on the succinctness of the advised machines are examined. We
also study randomly placed inkdots as advice to probabilistic finite automata,
and demonstrate the superiority of this model over its deterministic version.
Even very slowly growing amounts of space can become a resource of meaningful
use if the underlying advised model is extended with access to secondary
memory, while it is famously known that such small amounts of space are not
useful for unadvised oneway Turing machines.

We introduce the affine OBDD model and show that zeroerror affine OBDDs can
be exponentially narrower than boundederror unitary and probabilistic OBDDs on
certain problems. Moreover, we show that Las Vegas unitary and probabilistic
OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain
the same results by considering the automata versions of these models.

We investigate the minimum cases for realtime probabilistic machines that can
define uncountably many languages with bounded error. We show that logarithmic
space is enough for realtime PTMs on unary languages. On binary case, we follow
the same result for double logarithmic space, which is tight. When replacing
the worktape with some limited memories, we can follow uncountable results on
unary languages for two counters.

We investigate the width complexity of nondeterministic unitary OBDDs
(NUOBDDs). Firstly, we present a generic lower bound on their widths based on
the size of strong 1fooling sets. Then, we present classically cheap functions
that are expensive for NUOBDDs and vice versa by improving the previous gap. We
also present a function for which neither classical nor unitary nondeterminism
does help. Moreover, based on our results, we present a width hierarchy for
NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic
Boolean operations negation, union, and intersection.

We investigate the computational power of affine automata (AfAs) introduced
in [4]. In particular, we present a simpler proof for how to change the
cutpoint for any affine language and a method how to reduce error in bounded
error case. Moreover, we address to the question of [4] by showing that any
affine language can be recognized by an AfA with certain limitation on the
entries of affine states and transition matrices. Lastly, we present the first
languages shown to be not recognized by AfAs with boundederror.

It is well known that the emptiness problem for binary probabilistic automata
and so for quantum automata is undecidable. We present the current status of
the emptiness problems for unary probabilistic and quantum automata with
connections with Skolem's and positivity problems. We also introduce the
concept of linear recurrence automata in order to show the connection
naturally. Then, we also give possible generalizations of linear recurrence
relations and automata on vectors.

Polynomialtime constantspace quantum Turing machines (QTMs) and
logarithmicspace probabilistic Turing machines (PTMs) recognize uncountably
many languages with bounded error (Say and Yakary\i lmaz 2014,
arXiv:1411.7647). In this paper, we investigate more restricted cases for both
models to recognize uncountably many languages with bounded error. We show that
double logarithmic space is enough for PTMs on unary languages in sweeping
reading mode or logarithmic space for oneway head. On unary languages, for
quantum models, we obtain middle logarithmic space for counter machines. For
binary languages, arbitrary small nonconstant space is enough for PTMs even
using only counter as memory. For counter machines, when restricted to
polynomial time, we can obtain the same result for linear space. For
constantspace QTMs, we follow the result for a restricted sweeping head,
known as restarting realtime.

In this work we study a nonlinear generalization based on affine
transformations of probabilistic and quantum automata proposed recently by
D\'iazCaro and Yakary{\i}lmaz \cite{DCY16A} referred as affine automata.
First, we present efficient simulations of probabilistic and quantum automata
by means of affine automata which allows us to characterize the class of
exclusive stochastic languages. Then, we initiate a study on the succintness of
affine automata. In particular, we show that an infinite family of unary
regular languages can be recognized by 2state affine automata but the state
numbers of quantum and probabilistic automata cannot be bounded. Finally, we
present the characterization of all (regular) unary languages recognized by
twostate affine automata.

We introduce a quantumlike classical computational model, called affine
computation, as a generalization of probabilistic computation. After giving the
basics of affine computation, we define affine finite automata (AfA) and
compare it with quantum and probabilistic finite automata (QFA and PFA,
respectively) with respect to three basic language recognition modes. We show
that, in the cases of bounded and unbounded error, AfAs are more powerful than
QFAs and PFAs, and, in the case of nondeterministic computation, AfAs are more
powerful than PFAs but equivalent to QFAs.

Determining the minimum number of states required by a finite automaton to
separate a given pair of different words is an important problem. In this
paper, we consider this problem for quantum automata (QFAs). We show that
2state QFAs can separate any pair of words in nondeterministic acceptance mode
and conjecture that they can separate any pair also with zeroerror. Then, we
focus on (a more general problem) separating a pair of two disjoint finite set
of words. We show that QFAs can separate them efficiently in nondeterministic
acceptance mode, i.e. the number of states is two to the power of the size of
the small set. Additionally, we examine affine finite automata (AfAs) and show
that two states are enough to separate any pair with zeroerror. Moreover, AfAs
can separate any pair of disjoint finite sets of words with onesided bounded
error efficiently like QFAs in nondeterministic mode.

We present several new results on minimal space requirements to recognize a
nonregular language: (i) realtime nondeterministic Turing machines can
recognize a nonregular unary language within weak $\log\log n$ space, (ii)
$\log\log n$ is a tight space lower bound for accepting general nonregular
languages on weak realtime pushdown automata, (iii) there exist unary
nonregular languages accepted by realtime alternating onecounter automata
within weak $\log n$ space, (iv) there exist nonregular languages accepted by
twoway deterministic pushdown automata within strong $\log\log n$ space, and,
(v) there exist unary nonregular languages accepted by twoway onecounter
automata using quantum and classical states with middle $\log n$ space and
bounded error.

We study a model where two opposing provers debate over the membership status
of a given string in a language, trying to convince a weak verifier whose coins
are visible to all. We show that the incorporation of just two qubits to an
otherwise classical constantspace verifier raises the class of debatable
languages from at most $\mathsf{NP}$ to the collection of all Turingdecidable
languages (recursive languages). When the verifier is further constrained to
make the correct decision with probability 1, the corresponding class goes up
from the regular languages up to at least $\mathsf{E}$. We also show that the
quantum model outperforms its classical counterpart when restricted to run in
polynomial time, and demonstrate some noncontextfree languages which have
such short debates with quantum verifiers.

We continue the systematic investigation of probabilistic and quantum finite
automata (PFAs and QFAs) on promise problems by focusing on unary languages. We
show that boundederror QFAs are more powerful than PFAs. But, in contrary to
the binary problems, the computational powers of LasVegas QFAs and
boundederror PFAs are equivalent to deterministic finite automata (DFAs).
Lastly, we present a new family of unary promise problems with two parameters
such that when fixing one parameter QFAs can be exponentially more succinct
than PFAs and when fixing the other parameter PFAs can be exponentially more
succinct than DFAs.

Stochastic languages are the languages recognized by probabilistic finite
automata (PFAs) with cutpoint over the field of real numbers. More general
computational models over the same field such as generalized finite automata
(GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin
proved the set of stochastic languages to be uncountable presenting a single
2state PFA over the binary alphabet recognizing uncountably many languages
depending on the cutpoint. In this paper, we show the same result for unary
stochastic languages. Namely, we exhibit a 2state unary GFA, a 2state unary
QFA, and a family of 3state unary PFAs recognizing uncountably many languages;
all these numbers of states are optimal. After this, we completely characterize
the class of languages recognized by 1state GFAs, which is the only nontrivial
class of languages recognized by 1state automata. Finally, we consider the
variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive
cutpoint, and present some results on their expressive power.

Although polynomialtime probabilistic Turing machines can utilize
uncomputable transition probabilities to recognize uncountably many languages
with bounded error when allowed to use logarithmic space, it is known that such
"magic coins" give no additional computational power to constantspace versions
of those machines. We show that adding a few quantum bits to the model changes
the picture dramatically. For every language $L$, there exists such a twoway
quantum finite automaton that recognizes a language of the same Turing degree
as $L$ with bounded error in polynomial time. When used as verifiers in
publiccoin interactive proof systems, such automata can verify membership in
all languages with bounded error, outperforming their classical counterparts,
which are known to fail for the palindromes language.

Promise problems were mainly studied in quantum automata theory. Here we
focus on state complexity of classical automata for promise problems. First, it
was known that there is a family of unary promise problems solvable by quantum
automata by using a single qubit, but the number of states required by
corresponding oneway deterministic automata cannot be bounded by a constant.
For this family, we show that even twoway nondeterminism does not help to save
a single state. By comparing this with the corresponding state complexity of
alternating machines, we then get a tight exponential gap between twoway
nondeterministic and oneway alternating automata solving unary promise
problems. Second, despite of the existing quadratic gap between Las Vegas
realtime probabilistic automata and oneway deterministic automata for language
recognition, we show that, by turning to promise problems, the tight gap
becomes exponential. Last, we show that the situation is different for oneway
probabilistic automata with twosided boundederror. We present a family of
unary promise problems that is very easy for these machines; solvable with only
two states, but the number of states in twoway alternating or any simpler
automata is not limited by a constant. Moreover, we show that oneway
boundederror probabilistic automata can solve promise problems not solvable at
all by any other classical model.

A twoway deterministic finite state automaton with one counter (2D1CA) is a
fundamental computational model that has been examined in many different
aspects since sixties, but we know little about its power in the case of unary
languages. Up to our knowledge, the only known unary nonregular languages
recognized by 2D1CAs are those formed by strings having exponential length,
where the exponents form some trivial unary regular language. In this paper, we
present some nontrivial subsets of these languages. By using the input head as
a second counter, we present simulations of twoway deterministic finite
automata with linearly bounded counters and linearspace Turing machines. We
also show how a fixedsize quantum register can help to simplify some of these
languages. Finally, we compare unary 2D1CAs with twocounter machines and
provide some insights about the limits of their computational power.

We present five examples where quantum finite automata (QFAs) outperform
their classical counterparts. This may be useful as a relatively simple
technique to introduce quantum computation concepts to computer scientists. We
also describe a modern QFA model involving superoperators that is able to
simulate all known QFA and classical finite automaton variants.

We construct zeroerror quantum finite automata (QFAs) for promise problems
which cannot be solved by boundederror probabilistic finite automata (PFAs).
Here is a summary of our results:
 There is a promise problem solvable by an exact twoway QFA in exponential
expected time, but not by any boundederror sublogarithmic space probabilistic
Turing machine (PTM).
 There is a promise problem solvable by an exact twoway QFA in quadratic
expected time, but not by any boundederror $ o(\log \log n) $space PTMs in
polynomial expected time. The same problem can be solvable by a oneway Las
Vegas (or exact twoway) QFA with quantum head in linear (expected) time.
 There is a promise problem solvable by a Las Vegas realtime QFA, but not by
any boundederror realtime PFA. The same problem can be solvable by an exact
twoway QFA in linear expected time but not by any exact twoway PFA.
 There is a family of promise problems such that each promise problem can be
solvable by a twostate exact realtime QFAs, but, there is no such bound on the
number of states of realtime boundederror PFAs solving the members this
family.
Our results imply that there exist zeroerror quantum computational devices
with a \emph{single qubit} of memory that cannot be simulated by any finite
memory classical computational model. This provides a computational perspective
on results regarding ontological theories of quantum mechanics \cite{Hardy04},
\cite{Montina08}. As a consequence we find that classical automata based
simulation models \cite{Kleinmann11}, \cite{Blasiak13} are not sufficiently
powerful to simulate quantum contextuality. We conclude by highlighting the
interplay between results from automata models and their application to
developing a general framework for quantum contextuality.

We define a model of advised computation by finite automata where the advice
is provided on a separate tape. We consider several variants of the model where
the advice is deterministic or randomized, the input tape head is allowed
realtime, oneway, or twoway access, and the automaton is classical or
quantum. We prove several separation results among these variants, demonstrate
an infinite hierarchy of language classes recognized by automata with
increasing advice lengths, and establish the relationships between this and the
previously studied ways of providing advice to finite automata.

The minimum amount of resources to recognize a nonregular language is a
fundamental research topic in theoretical computer science which has been
examined for different kinds of resources and many different models. In this
note, we focus on unary languages and space complexity on counters. Our model
is twoway onecounter automaton with quantum and classical states (2QCCA),
which is a twoway finite automaton with onecounter (2DCA) augmented with a
fixed size quantum register or a twoway finite automaton with quantum and
classical states (2QCFA) augmented with a classical counter. It is known that
any 2DCA using a sublinear space on its counter can recognize only regular
languages \cite{DG82B}. In this note, we show that boundederror 2QCCAs can
recognize a nonregular unary language by using logarithmic space on its
counters for the members. Note that it is still an open problem whether
boundederror 2QCFA can recognize a nonregular unary language.

We examine the minimum amount of memory for realtime, as opposed to oneway,
computation accepting nonregular languages. We consider deterministic,
nondeterministic and alternating machines working within strong, middle and
weak space, and processing general or unary inputs. In most cases, we are able
to show that the lower bounds for oneway machines remain tight in the
realtime case. Memory lower bounds for nonregular acceptance on other devices
are also addressed. It is shown that increasing the number of stacks of
realtime pushdown automata can result in exponential improvement in the total
amount of space usage for nonregular language recognition.