Minimal NFA Problems are Hard (Q4277533)
From MaRDI portal
scientific article; zbMATH DE number 495784
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal NFA Problems are Hard |
scientific article; zbMATH DE number 495784 |
Statements
Minimal NFA Problems are Hard (English)
0 references
7 February 1994
0 references
NP-complete
0 references
regular languages
0 references
finite-state machines
0 references
finite automata
0 references
PSPACE-complete
0 references
nondeterminism
0 references