Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

While deterministic finite automata seem to be well understood, surprisingly

many important problems

concerning nondeterministic finite automata (nfa's) remain open.

One such problem area is the study of different measures of nondeterminism in

finite automata and the

estimation of the sizes of minimal nondeterministic finite automata. In this

paper the ...
more >>>

Till Tantau

Kummer's cardinality theorem states that a language is recursive

if a Turing machine can exclude for any n words one of the

n + 1 possibilities for the number of words in the language. It

is known that this theorem does not hold for polynomial-time

computations, but there ...
more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>

Scott Aaronson, Andrew Drucker

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Michael Blondin, Andreas Krebs, Pierre McKenzie

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

Zachary Remscrim

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

Zachary Remscrim

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>