There are different ways of measuring the complexity
of functions that map words to words. Well-known
measures are time and space
complexity.
Enumerability is another possible
measure. It is used in recursion theory, where it
plays a key role in bounded query theory, but also
in resource-bounded complexity theory, especially in
connection with nonuniform computations. This
dissertation transfers enumerability to automata
theory. It is shown that enumerability behaves
similarly in recursion theory and in automata
theory, but differently in complexity theory.
The enumerability of a function f is the
smallest m such that there exists an
m-enumerator for f. An
m-enumerator is a machine that produces, for
every input word w, a set of up to m
possibilities for f(w). By varying the
parameter m and the class of allowed
enumerators, different enumerability classes can be
defined. In recursion theory, one allows arbitrary
Turing machines as enumerators; in automata theory,
only finite automata. A deep structural result that
holds both for finite automata and for Turing
machine enumerability is the following cross
product theorem: if f × g is
(n + m)-enumerable, then either
f is n-enumerable or g is
m-enumerable. In contrast, this theorem does
not hold for polynomial-time enumerability.
Enumerability can be used to quantify the difficulty
of a language A by asking how difficult it is
to enumerate its n-fold characteristic
function \chi_{A}^{n} and
cardinality function
#_{A}^{n}. A language is
(n, m)-verbose if
\chi_{A}^{n} is
m-enumerable. The inclusion structures of
Turing machine and of finite automata verboseness
classes are identical: all (n,
m)-Turing-verbose languages are (h,
k)-Turing-verbose iff all (n,
m)-fa-verbose languages are (h,
k)-fa-verbose. The structure of
polynomial-time verboseness classes is
different.
The enumerability of
#_{A}^{n} has been studied in
detail in recursion theory. Kummer's cardinality
theorem states that if
#_{A}^{n} is
n-enumerable by a Turing machine, then
A must be recursive. Evidence is gathered
that this theorem also holds for finite automata: it
is shown that the nonspeedup theorem, the
cardinality theorem for two words, and the
restricted cardinality theorem all hold for finite
automata. The cardinality theorem does not hold for
polynomial-time computations.
The central
proofs rely on two proof techniques that promise to
be applicable in other situations as well: generic
proofs and branch diagonalisation. Generic proofs
use elementary definitions, a concept from logic, to
define enumerators in terms of other
enumerators. They can be instantiated for all
computational models that are closed under
elementary definitions. Examples of such models are
finite automata, but also Presburger arithmetic and
ordinal number arithmetic. The second technique is a
new diagonalisation method, where machines are
tricked on codes of diagonalisation decision
sequences, rather than on codes of machines. Branch
diagonalisation is not applicable universally, but
where it is applicable, it can be used to
diagonalise against Turing machines, using only
finite automata.
Results on enumerability
classes have applications in unrelated areas, like
finite automata protocol testing, classification
problems where examples are provided, and
separability. An intriguing example of such an
application is the following theorem: if there exist
regular supersets of A × A,
A × \bar A, and \bar A
× \bar A whose intersection is empty,
then A is regular.