About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Šimánek, Milan
The factor automaton. (English). Kybernetika, vol. 38 (2002), issue 1, pp. [105]-111
MSC: 68P05, 68Q45, 68W05 | MR 1899850 | Zbl 1265.68092
Keywords:
searching algorithm; data structures; factor automaton
Summary:
This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. Nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.
References:
[1] Crochemore M., Rytter W.: Text Algorithms, Chapter 6, Subword graphs. Oxford University Press, Oxford 1994 MR 1307378
[3] Melichar B.: The construction of factor automata. In: Workshop’98, vol. 1, Czech Technical University, Prague 1997, pp. 189–190
[4] Šimánek M.: Operations on factor automaton. In: Workshop ’98, vol. 1, Czech Technical University, Prague 1997, pp. 207–208
[5] Šimánek M.: The factor automaton. In: Proceedings of the Prague Stringology Club Workshop’98, Czech Technical University Prague, 1998, pp. 102–106
[6] Šimánek M.: Operations on Factor Automata. Postgraduate Study Report DC-PSR-98-02, Czech Technical University Prague 1998, 38 pp
Partner of
EuDML logo