The smallest automation recognizing the subwords of a text
- Blumer, A.
- Blumer, J.
- Haussler, D.
- Ehrenfeucht, A.
- Chen, M.T.
- Seiferas, J.
DOIAbstract
AbstractLet a partial deterministic finite automaton be a DFA in which each state need not have a transition edge for each letter of the alphabet. We demonstrate that the smallest partial DFA for the set of all subwords of a given word w, |w|>2, has at most 2|w|−2 states and 3|w|−4 transition edges, independently of the alphabet size. We give an algorithm to build this smallest partial DFA from the input w on-line in linear time
Add to ORKG