Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with finite automata:
TR00-076 | 24th August 2000
Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

Measures of Nondeterminism in Finite Automata

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 >>>

TR03-024 | 25th February 2003
Till Tantau

Weak Cardinality Theorems for First-Order Logic

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 >>>

TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

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 >>>

TR11-008 | 27th January 2011
Scott Aaronson, Andrew Drucker

Advice Coins for Classical and Quantum Computation

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 >>>

TR12-090 | 2nd July 2012
Michael Blondin, Andreas Krebs, Pierre McKenzie

The Complexity of Intersecting Finite Automata Having Few Final States

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 >>>

ISSN 1433-8092 | Imprint