Name
Abstract | ||
|---|---|---|
Let 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. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1016/0304-3975(85)90157-4 | THEORETICAL COMPUTER SCIENCE |
DocType | Volume | Issue |
Journal | 40 | 1 |
ISSN | Citations | PageRank |
0304-3975 | 72 | 18.70 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Blumer | 1 | 72 | 18.70 |
| J. Blumer | 2 | 72 | 18.70 |
| David Haussler | 3 | 8327 | 3068.93 |
| A. Ehrenfeucht | 4 | 1823 | 497.83 |
| M.T. Chen | 5 | 72 | 18.70 |
| J. Seiferas | 6 | 72 | 18.70 |