Glushkov construction

GPTKB entity

Statements (14)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:alsoKnownAs position automaton construction
gptkbp:field automata theory
theoretical computer science
gptkbp:hasProperty produces automata with at most n+1 states for regular expressions of length n
https://www.w3.org/2000/01/rdf-schema#label Glushkov construction
gptkbp:input regular expression
gptkbp:introducedIn 1961
gptkbp:namedAfter gptkb:Victor_Glushkov
gptkbp:output ε-free nondeterministic finite automaton
gptkbp:relatedTo Thompson's construction
gptkbp:usedFor converting regular expressions to nondeterministic finite automata
gptkbp:bfsParent gptkb:Victor_Glushkov
gptkbp:bfsLayer 6