|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050307,
author = {Kappes, Martin},
title = {Descriptional Complexity of Deterministic Finite Automata
with Multiple Initial States},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {269--278},
keywords = {finite automata, nondeterminism},
abstract = {We study the descriptional complexity of finite automata
with multiple initial states and a deterministic transition
function. The model is compared to ordinary deterministic and
nondeterministic finite automata. It allows to use
nondeterminism in practical applications and still provides
in some cases exponential savings in the number of states
compared to the smallest deterministic finite automaton.
Using another acceptance criterion, even exponential savings
over nondeterministic finite automata are achievable while
the implementation remains easy.}
}