Transducers and repetitions. (English) Zbl 0615.68053

Crochemore, Maxime

Theor. Comput. Sci. 45, 63-86 (1986).

The factor transducer of a word associates to each of its factors (or subwords) their first occurrence. Optimal bounds on the size of minimal factor transducers together with an algorithm for building them are given. Analogous results and a simple algorithm are given for the case of subsequential suffix transducers. Algorithms are applied to repetition searching in words.

MSC:

68Q45

Formal languages and automata

Keywords:

factor transducer of a word; subsequential suffix transducers; Algorithms; repetition searching in words

References:

[1]	Aho, A. V.; Corasick, M. J., Efficient string matching: An aid to bibliographic research, Comm. ACM, 18, 6, 333-340 (1975) · Zbl 0301.68048
[2]	Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0207.01701
[3]	Aho, A. V.; Ullman, J. D., Principles of Compiler Design (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0165.32001
[4]	Apostolico, A.; Preparata, F. P., Optimal off-line detection of repetitions in a string, Theoret. Comput. Sci., 22, 297-315 (1983) · Zbl 0497.68052
[5]	Berstel, J., Transduction and Context-Free Languages (1979), Teubner: Teubner Stuttgart
[6]	Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; Chen, M. T.; Seiferas, J., The smallest automation recognizing the subwords of a text, Theoret. Comput. Sci., 40, 1, 31-56 (1985) · Zbl 0574.68070
[7]	Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; McConnell, R., Finite automata for the set of all subwords of a word: An outline of results, Bull. Europ. Assoc. Theoret. Comput. Sci., 21, 12-20 (1983)
[8]	Boyer, R. S.; Moore, J. S., A fast string searching algorithm, Comm. ACM, 20, 10, 762-772 (1977) · Zbl 1219.68165
[9]	Crochemore, M., Recherche linéaire d’un carré dans un mot, C.R. Acad. Sci., Paris, 296, 781-784 (1983), série I · Zbl 0522.68074
[10]	Crochemore, M., Optimal factor transducers, (Proc. NATO Advanced Research Workshop on Combinatorial Algorithms on Words. Proc. NATO Advanced Research Workshop on Combinatorial Algorithms on Words, Maratea, Italy (1984)), 31-43
[11]	Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern-matching in strings, SIAM J. Comput., 6, 2, 323-350 (1977) · Zbl 0372.68005
[12]	Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[13]	Main, M.; Lorentz, R., An \(O(n\) log \(n)\) algorithm for finding repetition in a string, (Tech. Rept. CS-79-056 (1979), Washington State Univ: Washington State Univ Pullman)
[14]	Main, M.; Lorentz, R., Linear time recognition of square-free strings, (Proc. NATO Advanced Research Workshop on Combinatorial Algorithms on Words. Proc. NATO Advanced Research Workshop on Combinatorial Algorithms on Words, Maratea, Italy (1984)), 271-278
[15]	McCreight, E. M., A space-economical suffix-tree construction algorithm, J. ACM, 23, 2, 262-272 (1976) · Zbl 0329.68042
[16]	Morris, J. H.; Pratt, V. R., A linear pattern-matching algorithm, (Tech. Rept. 40 (1970), Comput. Center, Univ. of California: Comput. Center, Univ. of California Berkeley)
[17]	Rodeh, M., A fast test for unique decipherability based on suffix-tree, IEEE Trans. Inform. Theory, IT-28, 4, 648-651 (1982)
[18]	Slisenko, A. O., Determination in real time of all the periodicities in a word, Soviet Math. Dokl., 21, 2, 392-395 (1980) · Zbl 0442.68033
[19]	Weiner, P., Linear pattern-matching algorithms, (Proc. 14th Ann. Symp. on Switching and Automata Theory (1973)), 1-11
[20]	Ziv, J.; Lempel, A., Compression of individual sequences via variable-rate coding, IEEE Trans. Inform. Theory, IT-24, 5, 530-536 (1978) · Zbl 0392.94004