The society Informatikforum Stuttgart e.V. (infos)
has donated the Best Paper award
of the DLT 2009 conference.
The infos Best Paper award goes to
Galina Jiraskova
for her paper "Magic Numbers and Ternary Alphabet"!
for her paper "Magic Numbers and Ternary Alphabet"!
Abstract:
A number d is magic for n,
if there is no minimal nondeterministic finite automaton of n states
whose equivalent minimal deterministic finite automaton has d states.
We show that in the case of a ternary alphabet,
there are no magic numbers.
For all n and d satisfying that
n ≤ d ≤ 2n,
we describe an n-state nondeterministic finite automaton
with a three-letter input alphabet
that needs d deterministic states.
|