|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050304,
author = {Leung, Hing},
title = {On a Family of Nondeterministic Finite Automata},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {235--244},
keywords = {finite automata, sweeping automata, descriptional
complexity},
abstract = {In this paper, we study the succinctness properties of a
family of one-way $n$-state nondeterministic finite automata
$A_n$ over a two-letter alphabet. It is shown that the
smallest equivalent deterministic finite automaton has $2^n$
states, the smallest equivalent polynomially ambiguous
nondeterministic finite automaton has $2^n - 1$ states, and
any equivalent nondegenerate sweeping automaton has at least
$2^n$ states. We conjecture that the family $A_n$ can be used
to show that the complexity class L (deterministic
logarithmic space) is properly contained in NL
(nondeterministic logarithmic space), and any equivalent
two-way deterministic finite automaton would require an
exponential number of states.}
}