The finite automata approaches in stringology

Holub, Jan

Kybernetika, Tome 48 (2012) no. 3, pp. 386-401

Abstract (VO)

We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).

Détail

Classification : 62A10, 93E12
Keywords: exact pattern matching; approximate pattern matching; finite automata; dynamic programming; bitwise parallelism; suffix automaton; border array; degenerate symbol

Bibliographie

[1] Abrahamson, K.: Generalized string matching. SIAM J. Comput. 16 (1987), 6, 1039–1051. | DOI | MR | Zbl

[2] Aho, A. V., Corasick, M. J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18 (1975), 6, 333–340. | DOI | MR | Zbl

[3] Allauzen, C., Crochemore, M., Raffinot, M.: Factor oracle: A new structure for pattern matching. In: SOFSEM'99, Theory and Practice of Informatics (J. Pavelka, G. Tel, and M. Bartošek, eds.), Milovy 1999, Lect. Notes Comput. Sci. 1725 (1999), Springer-Verlag, Berlin, pp. 295–310. | MR | Zbl

[4] Antoniou, P., Holub, J., Iliopoulos, C. S., Melichar, B., Peterlongo, P.: Finding common motifs with gaps using finite automata. In: Implementation and Application of Automata (O. H. Ibarra and H.-C. Yen, eds.), Lect. Notes Comput. Sci. 4094 (2006), Springer-Verlag, Heidelberg, pp. 69–77. | MR | Zbl

[5] Baeza-Yates, R. A., Gonnet, G. H.: A new approach to text searching. Commun. ACM 35 (1992), 10, 74–82. | DOI

[6] Baker, B. S.: Parameterized duplication in strings: algorithms and an application to software maintenance. SIAM J. Comput. 26 (1997), 5, 1343–1362. | DOI | MR | Zbl

[7] Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., Chen, M. T., Seiferas, J.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40 (1985), 1, 31–44. | DOI | MR | Zbl

[8] Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., McConnel, R.: Complete inverted files for efficient text retrieval and analysis. J. Assoc. Comput. Mach. 34 (1987), 3, 578–595. | DOI | MR

[9] Boyer, R. S., Moore, J. S.: A fast string searching algorithm. Commun. ACM 20 (1977), 10, 762–772. | DOI | Zbl

[10] Cambouropoulos, E., Crochemore, M., Iliopoulos, C. S., Mouchard, L., Pinzon, Y. J.: Algorithms for computing approximate repetitions in musical sequences. In: Proc. Tenth Australian Workshop on Combinatorial Algorithms (R. Raman and J. Simpson, eds.), AWOCA'99, School of Computing, Curtin University of Technology, Perth 1999, pp. 129–144. | Zbl

[11] Commentz-Walter, B.: A string matching algorithm fast on the average. In: Proc. 6th International Colloquium on Automata, Languages and Programming (H. A. Maurer, ed.), Graz 1979, Lect. Notes Comput. Sci. 71 (1979), Springer-Verlag, Berlin, pp. 118–132. | Zbl

[12] Crochemore, M.: Transducers and repetitions. Theor. Comput. Sci. 45 (1986), 1, 63–86. | DOI | MR | Zbl

[13] Damerau, F.: A technique for computer detection and correction of spelling errors. Commun. ACM 7 (1964), 3, 171–176. | DOI

[14] Dömölki, B.: An algorithm for syntactical analysis. Comput. Linguistics 3 (1964), 29–46, 1964.

[15] Fischer, M. J., Paterson, M.: String matching and other products. In: Proc. SIAM-AMS Complexity of Computation (R. M. Karp, ed.), Providence 1974, pp. 113–125. | MR | Zbl

[16] Fredriksson, K., Mozgovoy, M.: Efficient parameterized string matching. Inf. Process. Lett. 100 (2006), 3, 91–96. | DOI | MR | Zbl

[17] Galil, Z.: Open problems in stringology. In: Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), NATO ASI Series F 12 (1985), Springer-Verlag, Berlin, pp. 1–8. | MR | Zbl

[18] Hamming, R. W.: Error detecting and error correcting codes. The Bell System Techn. J. 29 (1950), 2, 147–160. | MR

[19] Holub, J.: Bit parallelism-NFA simulation. In: Implementation and Application of Automata (B. W. Watson and D. Wood, eds.), Lect. Notes in Comput. Sci. 2494 (2002), Springer-Verlag, Heidelberg, pp. 149–160. | Zbl

[20] Holub, J.: Finite automata in pattern matching. In: Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications (M. Elloumi and A. Y. Zomaya, eds.), John Wiley and Sons, 2011, pp. 51–71.

[21] Holub, J., Kadlec, T.: NFA simulation using deterministic state cache. In: London Algorithmics 2008: Theory and Practice (J. Chan, J. W. Daykin, and M. S. Rahman, eds.), College Publications 2009, pp. 152–166.

[22] Holub, J., Melichar, B.: Implementation of nondeterministic finite automata for approximate pattern matching. In: Proc. 3rd International Workshop on Implementing Automata, Rouen 1998, pp. 74–81.

[23] Holub, J., Melichar, B.: Approximate string matching using factor automata. Theor. Comput. Sci. 249 (2000), 2, 30–311. | DOI | MR | Zbl

[24] Holub, J., Smyth, W. F.: Algorithms on indeterminate strings. In: Proc. 14th Australasian Workshop On Combinatorial Algorithms (M. Miller and K. Park, eds.), Seoul National University, Seoul 2003, pp. 36–45.

[25] Holub, J., Smyth, W. F., Wang, S.: Hybrid pattern-matching algorithms on indeterminate strings. In: London Stringology Day and London Algorithmic Workshop 2006 (J. Daykin, M. Mohamed, and K. Steinhoefel, eds.) King's College London Series Texts in Algorithmics 2007, pp. 115–133.

[26] Holub, J., Smyth, W. F., Wang, S.: Fast pattern-matching on indeterminate strings. J. Discret. Algorithms 6 (2008), 1, 37–50. | DOI | MR | Zbl

[27] Holub, J., Špiller, P.: Practical experiments with NFA simulation. In: Proc. Eindhoven FASTAR Days 2004 (L. Cleophas and B. W. Watson, eds.), TU Eindhoven 2004, The Finite Automata Approaches in Stringology 15, pp. 73–95.

[28] Hopcroft, J. E., Ullman, J. D.: Introduction to automata, languages and computations. Addison-Wesley, Reading 1979. | MR

[29] Huffman, D. A.: The synthesis of sequential switching circuits. J. Franklin Inst. 257 (1954), 161–190, 275–303. | DOI | MR | Zbl

[30] Huffman, D. A.: A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Engrs 40 (1952), 9, 1098–1101. | Zbl

[31] Iliopoulos, C. S., Jayasekera, I., Melichar, B., Šupol, J.: Weighted degenerated approximate pattern matching. In: Proc. 1st International Conference on Language and Automata Theory and Applications, Tarragona 2007.

[32] Kleene, S. C.: Representation of events in nerve nets and finite automata. Automata Studies (1956), 3–42. | MR

[33] Knuth, D. E., Morris, J. H., Jr, Pratt, V. R.: Fast pattern matching in strings. SIAM J. Comput. 6 (1977), 2, 323–350. | DOI | MR | Zbl

[34] Kurtz, S.: Reducing the space requirements of suffix trees. Softw. Pract. Exp. 29 (1999), 13, 1149–1171. | DOI

[35] Lahoda, J., Melichar, B.: Pattern matching in text coded by finite translation automaton. In: Proc. 7th International Multiconference Information Society (M. Heričko et al., eds.), Institut Jožef Stefan, Ljubljana 2004, pp. 212–214.

[36] Lahoda, J., Melichar, B.: General pattern matching on regular collage system. In: Proc. Prague Stringology Conference'05 (J. Holub and M. Šimánek, eds.), Czech Technical University in Prague 2005, pp. 153–162.

[37] Levenshtein, V. I.: Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl. 6 (1966), 707–710. | MR

[38] McCulloch, W. S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5 (1943), 115–133. | DOI | MR | Zbl

[39] Mealy, G. H.: A method for synthetizing sequential circuits. Bell System Techn. J. 34 (1955), 5, 1045–1079. | DOI | MR

[40] Melichar, B.: Repetitions in text and finite automata. In: Proc. Eindhoven FASTAR Days 2004 (L. Cleophas and B. W. Watson, eds.), TU Eindhoven 2004, pp. 1–46.

[41] Melichar, B., Holub, J.: 6D classification of pattern matching problems. In: Proceedings of the Prague Stringology Club Workshop'97 (J. Holub, ed.), Czech Technical University in Prague, 1997, pp. 24–32. Collaborative Report DC-97-03.

[42] Melichar, B., Holub, J., Polcar, T.: Text searching algorithms. Vol. I: Forward string matching. Textbook for course Text Searching Algorithms, 2005.

[43] Moore, E. F.: Gedanken experiments on sequential machines. Automata Studies (1965), 129–153. | MR

[44] Morris, J. H., Jr, Pratt, V. R.: A Linear Pattern-Matching Algorithm. Report 40, University of California, Berkeley 1970.

[45] Navarro, G., Raffinot, M.: A bit-parallel approach to suffix automata: Fast extended string matching. In: Proc. 9th Annual Symposium on Combinatorial Pattern Matching (M. Farach-Colton, ed.), Lect. Notes in Comput. Sci. 1448, Piscataway, NJ, 1998. Springer-Verlag, Berlin, pp. 14–33. | MR

[46] Rabin, M. O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3 (1959) 114–125. | DOI | MR | Zbl

[47] Sellers, P. H.: The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms 1 (1980), 4, 359–373. | DOI | MR | Zbl

[48] Shyamasundar, R. K.: A Simple String Matching Algorithm. Technical Report, Tata Institute of Fundamental Research 1976.

[49] M. Šimůnek, Melichar, B.: Borders and finite automata. In: Implementation and Application of Automata (O. H. Ibarra and H.-C. Yen, eds.), Lecture Notes in Comput. Sci. 4094, Springer-Verlag, Heidelberg 2006, pp. 58–68. | MR | Zbl

[50] Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms 6 (1985), 1–3, 132–137. | DOI | MR | Zbl

[51] Voráček, M., Vagner, L., Rahman, S., Iliopoulos, C. S.: The constrained longest common subsequence problem for degenerate strings. In: Implementation and Application of Automata (J. Holub and J. Žďárek, eds.), Lecture Notes in Comput. Sci. 4783, Springer-Verlag, Heidelberg 2007, pp. 309–311. | Zbl

[52] Wu, S., Manber, U.: Fast text searching allowing errors. Commun. ACM 35 (1992), 10, 83–91. | DOI

[53] Ziv, J., Lempel, A.: Compression of individual sequences via variable length coding. IEEE Trans. Inf. Theory 24 (1978), 530–536. | DOI | MR