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

Hermann Gruber, Markus Holzer

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from ...
more >>>

Viliam Geffert, Abuzer Yakaryilmaz

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