Next:
AL2 LONGEST COMPUTATION
Up:
Automata Theory
Previous:
Automata Theory
AL1 M
INIMUM
C
ONSISTENT
F
INITE
A
UTOMATON
I
NSTANCE
: Two finite sets
P, N
of binary strings.
S
OLUTION
: A deterministic finite automaton
accepting all strings in
P
and rejecting all strings in
N
.
M
EASURE
: Number of states in the automaton.
Bad News:
Not approximable within 2
for any
[
324
].
Comment:
Transformation from M
INIMUM
G
RAPH
C
OLORING
. Not approximable within
for any
[
293
].
Garey and Johnson:
AL8
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
accepting all strings in
P
and rejecting all strings in
N
.
for any
[
324
].
for any
[
293
].