Bibliography

[Ab 89] D.M. ABRAHAMSON, Generalized string-matching, SIAM J. Comput. 16 (1989) 77-83.

[Ah 80] A.V. AHO, Pattern matching in strings, in: (Book, editor, Formal Language Theory—perspectives and open problems, Academic Press, 1980) 325-347.

[Ah 90] A.V. AHO, Algorithms for finding patterns in strings, in: (J. VAN LEEUWEN, editor, Handbook of Theoretical Computer Science, vol A, Algorithms and complexity, Elsevier, Amsterdam, 1990) 255-300.

[AC 75] A.V. AHO, M. CORASICK, Efficient string-matching: an aid to bibliographic search, Comm. ACM 18 (1975) 333-340.

[AHU 76] A.V. AHO, D.S. HIRSCHBERG, J.D. ULLMAN, Bounds on the complexity of the longest common subsequence problem, J. ACM 23 (1976) 1-12.

[AHU 74] A.V. AHO, J.E. HOPCROFT, J.D. ULLMAN, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass. 1974.

[AHU 83] A.V. AHO, J. E. HOPCROFT, J.D. ULLMAN, Data structures and algorithms, Addison-Wesley, Reading, Mass. 1983.

[AKW 88] A.V. AHO, B.W. KERNIGHAN & P.J. WEINBERGER, The AWK Programming Language, Addison-Wesley, Reading, Mass., 1988.

[ASU 86] A.V. AHO, R.SETHI, J.D. ULLMAN, Compilers - Principles, Techniques and Tools, Addison-Wesley, Reading, Mass., 1986.

[AD 86] L. ALLISON, T.I. DIX, A bit string longest common subsequence algorithm, Inf. Process. Lett. 23 (1986) 305-310.

[AB 92] A. AMIR, G. BENSON, Two-dimensional periodicity and its application, in: (Proc. Symp. On Discrete Algorithms, 1992) 440-452.

[ABF 92a] A. AMIR, G. BENSON, M. FARACH, Alphabet-independent two-dimensional matching, in: (Proc. 24th ACM Symp. on Theory Of Computing, 1992) 59-68.

[ABF 92b] A. AMIR, G. BENSON, M. FARACH, Optimal parallel twodimensional pattern matching, 1992, manuscript.

[AF 91] A. AMIR, M. FARACH, Efficient 2-dimensional approximate matching of non- rectangular figures, in: (Proc. Symp. On Discrete Algorithms, 1991) 212-223.

[AL 91] A. AMIR, G.M. LANDAU, Fast parallel and serial multidimensional approximate array matching, Theoret. Comput. Sci. 81 (1991) 97-115.

[ALV 92] A. AMIR, G.M. LANDAU, U. VISHKIN, Efficient pattern matching with scaling, J. Algorithms 13 (1992) 2-32.

[An 80] D. ANGLUIN, Finding patterns common to a set of strings, J. Comput. Syst. Sci. 21 (1980) 46-62.

[Ap 85] A. APOSTOLICO, The myriad virtues of suffix trees, in: [AG 85] 85-96.

[Ap 86] A. APOSTOLICO, Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings, Inf. Process. Lett. 23 (1986) 63-69.

[Ap 87] A. APOSTOLICO, Remark on the Hsu-Du new algorithm for the longest common subsequence problem, Inf. Process. Lett. 25 (1987) 235-236.

[Ap 92] A. APOSTOLICO, Fast Parallel Detection of Squares in Strings, Algorithmica 8 (1992) 285-319.

[AALF 88] A. APOSTOLICO, M.J. ATALLAH, L.L. LARMORE, H.S. MCFADDIN, Efficient parallel algorithms for string editing and related problems, Report CSD-TR-724, Purdue University, 1988.

[ABG 92] A. APOSTOLICO, D. BRESLAUER, Z. GALIL, Optimal Parallel Algorithms for Periods, Palindromes and Squares, in: (ICALP’92, LNCS, Springer-Verlag, 1992).

[ABG 92] A. APOSTOLICO, S. BROWNE, C. GUERRA, Fast linearspace computations of longest common subsequences, Theoret. Comput. Sci. 92 (1992) 3-17.

[AC 91] A. APOSTOLICO, M. CROCHEMORE, Optimal canonization of all substrings of a string, Information and Computation 95, 1 (1991) 76-95.

[AC 90] A. APOSTOLICO, M. CROCHEMORE, Fast parallel Lyndon factorization and applications, Information and Computation, (1990). To appear.

[AG 85] A. APOSTOLICO, Z. GALIL, editors, Combinatorial Algorithms on Words, NATO Advanced Science Institutes, Series F, vol. 12, Springer-Verlag, Berlin, 1985.

[AG 84] A. APOSTOLICO, R. GIANCARLO, Pattern matching machine implementation of a fast test for unique decipherability, Inf. Process. Lett. 18 (1984) 155-158.

[AG 86] A. APOSTOLICO, R. GIANCARLO, The Boyer-Moore-Galil string searching strategies revisited, SIAM J.Comput. 15 (1986) 98-105.

[AG 87] A. APOSTOLICO, C. GUERRA, The longest common subsequence problem revisited. Algorithmica 2 (1987) 315-336.

[AILSV 88] A. APOSTOLICO, C. ILIOPOULOS, G.M. LANDAU, B. SCHIEBER, U. VISHKIN, Parallel construction of a suffix tree with applications, Algorithmica 3 (1988) 347- 365.

[AP 83] A. APOSTOLICO, F.P. PREPARATA, Optimal off-line detection of repetitions in a string, Theoret. Comput. Sci. 22 (1983) 297-315.

[AP 85] A. APOSTOLICO, F.P. PREPARATA, Structural properties of the string statistics problem, J. Comput. Syst. Sci. 31 (1985) 394-411.

[AKLMT 89] M.J. ATALLAH, S.R. KOSARAJU, L.L. LARMORE, G.L. MILLER, S-H. TENG, Constructing trees in parallel, Report CSD-TR-883, Purdue University, 1989.

[Ba 88] S. BAASE, Computer Algorithms—Introduction to Design and Analysis, Addison-Wesley, Reading, Mass., 1988. 2nd edition.

[Ba 89] R.A. BAEZA-YATES, Improved string searching, Software— Practice and Experience 19 (1989) 257-271.

[BCG 93] R.A. BAEZA-YATES, C. CHOFFRUT, G.H. GONNET, On Boyer-Moore automata, Algorithmica (1993). To appear.

[BG 89] R.A. BAEZA-YATES, G.H. GONNET, Efficient text searching of regular expressions, in: (AUSIELLO, DEZANI-CIAN-CAGLINI, RONCHI DELLA ROCCA, editors, Automata, Languages and Programming, Lecture Notes in Computer Science 372, Springer-Verlag, Berlin, 1989) 46-62.

[BG 92] R.A. BAEZA-YATES, G.H. GONNET, A new approach to text searching, Comm. ACM 35, 10 (1992) 74-82.

[BGR 90] R.A. BAEZA-YATES, G.H. GONNET, M. RÉGNIER, Analysis of Boyer-Moore type string searching algorithms, in: (Proc. of 1st ACM-SIAM Symposium on Discrete Algorithms, American Mathematical Society, Providence, 1990) 328-343.

[BR 90] R.A. BAEZA-YATES, M. RÉGNIER, Fast algorithms for twodimensional and multiple pattern matching, in: (R. KARLS-SON, J. GILBERT, editors, Proc. 2nd Scandinavian Workshop in Algorithmic Theory, Lecture Notes in Computer Science 447, Springer-Verlag, Berlin, 1990) 332-347.

[BR 92] R.A. BAEZA-YATES, M. RÉGNIER, Average running time of the Boyer-Moore- Horspool algorithm, Theoret. Comput. Sci. 92 (1992) 19-31.

[Ba 93] B. BAKER, A theory of parameterized pattern matching: algorithms and applications, in: (STOC’93, 1993).

[Ba 78] T.P. BAKER, A technique for extending rapid exact-match string-matching to arrays of more than one dimension, SIAM J.Comput. 7 (1978) 533-541.

[Ba 81] G. BARTH, An alternative for the implementation of the Knuth-Morris-Pratt algorithm, Inf. Process. Lett. 13 (1981) 134-137.

[Ba 84] G. BARTH, An analytical comparison of two string searching algorithms, Inf. Process. Lett. 18 (1984) 249-256.

[Ba 85] G. BARTH, Relating the average-case cost of the brute-force and the Knuth- Morris-Pratt string-matching algorithm, in: [AG 85] 45-58.

[BEM 79] D. BEAN, A. EHRENFEUCHT, G. MCNULTY, Avoidable patterns in strings of symbols, Pacific Journal of Math. 85 (1979) 261-294.

[BBC 92] D. BEAUQUIER, J. BERSTEL, P. CHRÉTIENNE, Éléments d’algorithmique, Masson, Paris, 1992.

[BCW 90] T.C. BELL, J.G. CLEARY, I.H. WITTEN, Text Compression, Prentice Hall, Englewood Cliffs, New Jersey, 1990.

[BSTW 86] J.L. BENTLEY, D.D. SLEATOR, R.E. TARJAN, V.K. WEI, A locally adaptive data compression scheme, Commun. ACM 29, 4 (1986) 320-330.

[BBGSV 89] O. BERKMAN, D. BRESLAUER, Z. GALIL, B. SCHIEBER, U. VISHKIN, Highly parallelizable problems, in: (Proc. 21st ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1989) 309-319.

[BP 85] J. BERSTEL, D. PERRIN, Theory of codes, Academic Press, Orlando, Florida, 1985.

[Bi 77] R.S. BIRD, Two-dimensional pattern-matching, Inf. Process. Lett. 6 (1977) 168- 170.

[BR 87] M.J. BISHOP & C.J. RAWLINGS, Nucleic acid and protein sequence analysis: a practical approach, IRL Press Limited, Oxford, England, 1987.

[BBEHM 83] A. BLUMER, J. BLUMER, A. EHRENFEUCHT, D. HAUSSLER, R. MCCONNELL, Linear size finite automata for the set of all subwords of a word: an outline of results, Bull. Europ. Assoc. Theoret. Comput. Sci. 21 (1983) 12-20.

[BBEHCS 85] A. BLUMER, J. BLUMER, A. EHRENFEUCHT, D. HAUSSLER, M.T. CHEN, J. SEIFERAS, The smallest automaton recognizing the subwords of a text, Theoret. Comput. Sci. 40 (1985) 31-55.

[BBEHM 87] A. BLUMER, J. BLUMER, A. EHRENFEUCHT, D. HAUSSLER, R. MCCONNELL, Complete inverted files for efficient text retrieval and analysis, J. ACM 34 (1987) 578-595.

[Bl 87] J.A. BLUMER, How much is that DAWG in the window? a moving window algorithm for the directed acyclic word graph, J. Algorithms 8 (1987) 451-469.

[Bo 80] K. BOOTH, Lexicographically least circular strings, Inf. Process. Lett. 10 (1980) 240-242.

[BM 77] R.S. BOYER, J.S. MOORE, A fast string searching algorithm, Comm. ACM 20 (1977) 762-772.

[BG 90] D. BRESLAUER, Z. GALIL, An optimal O(log log n) time parallel string-matching algorithm, SIAM J.Comput 19, 6 (1990) 1051-1058.

[BCT 93] D. BRESLAUER, L. COLUSSI, L. TONIOLO, Tight comparison bounds for the string prefix-matching problem, Inf. Process. Lett. 47 (1993) 51-57.

[Ca 90] R. CAPOCELLI, editor, Sequences: Combinatorics, Compression, Security and Transmission, Springer-Verlag, New-York, 1990.

[CSV 93] R. CAPOCELLI, A. DE SANTIS, U. VACCARO, editors, Sequences II, Springer- Verlag, New-York, 1993.

[CL 90] W.I. CHANG, E.L. LAWLER, Approximate String-matching in Sublinear Expected Time, in: (FOCS’90).

[CS 85] M.T. CHEN, J. SEIFERAS, Efficient and elegant subword tree construction, in: [AG 85] 97-107.

[Ch 90] C. CHOFFRUT, An optimal algorithm for building the Boyer-Moore automaton, Bull. Europ. Assoc. Theoret. Comput. Sci. 40 (1990) 217-225.

[CR 87a] M. CHROBAK, W. RYTTER, Remarks on string-matching and one-way multihead automata, Inf. Process. Lett. 24 (1987) 325-329.

[CR 87b] M. CHROBAK, W. RYTTER, Unique decipherability for partially commutative alphabets, Fundamenta Informaticae (1987) 323-336.

[CS 75] V. CHVATAL, D. SANKOFF, Longest common subsequence of two random sequences, J. Appl. Prob. 12 (1975) 306-315.

[Co 88] R. COLE, Parallel merge sort, SIAM J.Comput. 17 (1988) 770-785.

[Co 90] R. COLE, A new proof of the linearity of the Boyer-Moore string-matching algorithm, in: (Maryland Theoretical Science Day, 1990).

[Co 91] R. COLE, Tight bounds on the complexity of the Boyer-Moore algorithm, in: (Proceedings of the second annual ACM-SIAM Symposium on Discrete Algorithms, 1991) 224-233, and SIAM J.Comput. to appear.

[C-R 93b] R. COLE, M. CROCHEMORE, Z. GALIL, L. GASIENIEC, R. HARIHARAN, S. MUTHUKRISHNAN, K. PARK, W. RYT-TER, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, in: (FOCS’93, 1993).

[CH 92] R. COLE, R. HARIHARAN, Tighter bound on the exact complexity of string- matching, in: (FOCS’92) 600-609.

[CGG 90] L. COLUSSI, Z. GALIL, R. GIANCARLO, On the exact complexity of string- matching, in: (Proc. 31st Symposium on Foundations of Computer Science, IEEE, 1990) 135-143.

[Co 79] B. COMMENTZ-WALTER, A string-matching algorithm fast on the average, in: (Automata, Languages and Programming, 6th, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1979) 118-132.

[CD 89] C. CONSEL, O. DANVY, Partial evaluation of pattern matching in strings, Inf. Process. Lett. 30 (1989) 79-86.

[Co 72] S.A. COOK, Linear time simulation of deterministic two-way pushdown automata, Information Processing 71 (1972) 75-80.

[CH 84] G.V. CORMACK, R.N.S. HORSPOOL, Algorithms for adaptive Huffman codes, Inf. Process. Lett. 18 (1984) 159-165.

[CLR 89] T.H. CORMEN, C.E. LEIRSERSON, R.L. RIVEST, Introduction to Algorithms, The MIT Press, Cambridge, Mass., 1989.

[Cr 81] M. CROCHEMORE, An optimal algorithm for computing the repetitions in a word, Inf. Process. Lett. 12 (1981) 244-250.

[Cr 83] M. CROCHEMORE, Recherche linéaire d’un carré dans un mot, C. R. Acad. Sc. Paris, t. 296 (1983) Série 1, 781-784.

[Cr 85] M. CROCHEMORE, Optimal factor transducers, in: [AG 85] 31-43.

[Cr 86] M. CROCHEMORE, Transducers and repetitions, Theoret. Comput. Sci. 45 (1986) 63-86.

[Cr 87] M. CROCHEMORE, Longest common factor of two words, in: (EHRIG, KOWALSKI, LEVI & MONTANARI, editors, TAP-SOFT’87, vol 1, Springer-Verlag, Berlin, 1987) 26-36.

[Cr 88] M. CROCHEMORE, String-Matching with Constraints, in: (M. CHYTIL, L. JANIGA, & V. KOUBEK, editors, Mathematical Foundations of Computer Science 1988, Lecture Notes in Computer Science 324, Springer-Verlag, Berlin, 1988) 44-58.

[Cr 89a] M. CROCHEMORE, Data compression with substitution, in: [GP 89] 1-16.

[Cr 89b] M. CROCHEMORE, Automata and algorithms, in: (J-E. PIN, editor, Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science 386, Springer-Verlag, Berlin, 1989) 166-175.

[Cr 89c] M. CROCHEMORE, String-matching and periods, Bul. Euro. Assoc. Theor. Comput. Sci. 39 (1989) 149-153.

[Cr 92] M. CROCHEMORE, String-Matching on Ordered Alphabets, Theoret. Comput. Sci. 92 (1992) 33-47.

[C-R 92] M. CROCHEMORE, A. CZUMAJ, L. GASIENIEC, S. JA-ROMINEK, T. LECROQ, W. PLANDOWSKI, W. RYTTER, Speeding up two string-matching algorithms, in: (A. Finkel and M. Jantzen editors, 9th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Berlin, 1992) 589-600.

[C-R 93a] M. CROCHEMORE, A. CZUMAJ, L. GASIENIEC, S. JA-ROMINEK, T. LECROQ, W. PLANDOWSKI, W. RYTTER, Fast multi-pattern matching, Rapport I.G.M. 93-3, Université de Marne la Vallée, 1993.

[CGPR 93] M. CROCHEMORE, L. GASIENIEC, W. RYTTER, Twodimensional pattern matching by sampling, Inform. Process. Lett. (1993). To appear.

[CN 90] M. CROCHEMORE, J. NÉRAUD, Unitary monoid with two generators: an algorithmic point of view, in: (A. ARNOLD, editor, CAAP’90, Lecture Notes in Computer Science 431, Springer-Verlag, Berlin, 1990) 117-131.

[CP 91] M. CROCHEMORE, D. PERRIN, Two-way string-matching, J. ACM 38, 3 (1991) 651-675.

[CR 90] M. CROCHEMORE, W. RYTTER, Parallel construction of minimal suffix and factor automata, Inform. Process. Lett. 35 (1990) 121-128.

[CR 91a] M. CROCHEMORE, W. RYTTER, Efficient parallel algorithms to test square- freeness and factorize strings, Inf. Process. Lett. 38 (1991) 57-60.

[CR 91c] M. CROCHEMORE, W. RYTTER, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoret. Comput. Sci 88 (1991) 59-82.

[CR 92] M. CROCHEMORE, W. RYTTER, Note on two-dimensional pattern matching by optimal parallel algorithms, in: (Parallel Image Analysis, A. Nakamura, M. Nivat, A. Saoudi, P.S.P. Wang, K. Inoue eds, LNCS 654, Springer-Verlag, 1992) 100- 112.

[CR 93] M. CROCHEMORE, W. RYTTER, Cubes, squares and timespace efficient string- searching, Algorithmica (1993). To appear.

[De 79] J. DEKEN, Some limit results for longest common subsequences, Discrete Math. 26 (1979) 17-31.

[DGM 90] M. DUBINER, Z. GALIL, E. MAGEN, Faster tree pattern matching, in: (Proceedings of 31st FOCS, 1990) 145-150.

[Du 79] J-P. DUVAL, Périodes et répétitions des mots du monoïde libre, Theoret. Comput. Sci. 9 (1979) 17-26.

[Du 82] J-P. DUVAL, Relationship between the period of a finite word and the length of its unbordered segments, Discrete Math. 40 (1982) 31-44.

[Du 83] J-P. DUVAL, Factorizing words over an ordered alphabet, J. Algorithms 4 (1983) 363-381.

[EV 88] T. EILAM-TZOREFF, U. VISHKIN, Matching patterns in strings subject to multi- linear transformations, Theoret. Comput. Sci. 60 (1988) 231-254.

[EGGI 90] D. EPPSTEIN, Z. GALIL, R. GIANCARLO, G. ITALIANO, Sparse dynamic programming, J. ACM (1990). To appear.

[Fa 73] N. FALLER, An adaptive system for data compression, in: (Record of the 7th Asilomar Conference on Circuits, Systems, and Computers, 1973) 593-597.

[FT 87] Z.R. FENG, T. TAKAOKA, On improving the average case of the Boyer-Moore string-matching algorithm, J. Inf. Process. 10, 3 (1987) 173-177.

[FT 89] Z.R. FENG, T. TAKAOKA, A technique for two-dimensional pattern matching, Comm. ACM 32 (1989) 1110-1120.

[FW 65] N.J. FINE, H.S. WILF, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965) 109-114.

[FP 74] M.J. FISCHER, M.S. PATERSON, String-matching and other products, in: (R.M. KARP, editor, Proc. of SIAM-AMS conference on Complexity of Computation, American Mathematical Society, Providence, R.I., 1974) 113-125.

[Fr 75] M.L. FREDMAN, On computing the length of longest increasing subsequences, Discrete Math. 11 (1975) 29-35.

[Ga 76] Z. GALIL, Two fast simulations which imply fast stringmatching and palindrome- recognition algorithms, Inf. Process. Lett. 4, 4 (1976) 85-87.

[Ga 77] Z. GALIL, Some open problems in the theory of computations as questions about two-way deterministic pushdown automaton languages, Math. Syst. Theory 10 (1977) 211-228.

[Ga 78] Z. GALIL, Palindrome recognition in real time by a multitape Turing machine, J. Comput. Syst. Sci. 16 (1978) 140-157.

[Ga 79] Z. GALIL, On improving the worst case running time of the Boyer-Moore string searching algorithm, Comm. ACM 22 (1979) 505-508.

[Ga 81] Z. GALIL, String-matching in real time, J. ACM 28 (1981) 134-149.

[Ga 85a] Z. GALIL, Open problems in stringology, in: [AG 85] 1-12.

[Ga 85b] Z. GALIL, Optimal parallel algorithm for string-matching, Information and Control 67, (1985) 144-157.

[Ga 92] Z. GALIL, A constant-time optimal parallel string-matching algorithm, in: (Proc. 24th ACM Symp. on Theory Of Computing, 1992).

[GG 87] Z. GALIL, R. GIANCARLO, Parallel string-matching with k mismatches, Theoret. Comput. Sci. 51 (1987) 341-348.

[GG 88] Z. GALIL, R. GIANCARLO, Data structures and algorithms for approximate string- matching, J. Complexity 4 (1988) 33-72.

[GG 89] Z. GALIL, R. GIANCARLO, Speeding up dynamic programming with applications to molecular biology, Theoret. Comput. Sci. 64 (1989) 107-118.

[GP 89] Z. GALIL, K. PARK, An improved algorithm for approximate string-matching, in: (AUSIELLO, DEZANI-CIANCAGLINI, RONCHI DELLA ROCCA, editors, Automata, Languages and Programming, Lecture Notes in Computer Science 372, Springer-Verlag, Berlin, 1989) 394-404.

[GP 92a] Z. GALIL, K. PARK, Dynamic programming with convexity, concavity and sparsity, Theoret. Comput. Sci. 92 (1992) 49-76.

[GP 92b] Z. GALIL, K. PARK, Truly alphabet-independent twodimensional matching, in: (Proc. 33rd Annual IEEE Symposium on the Foundations of Computer Science, 1992) 247-256.

[GR 90] Z. GALIL, Y. RABANI, On the space requirement of the fastest algorithms for computing edit distance with convex or concave gap costs, Theoret. Comput. Sci (1990). To appear.

[GS 78] Z. GALIL, J. SEIFERAS, A linear-time on-line recognition algorithm for ”Palstars”, J. ACM 25 (1978) 102-111.

[GS 80] Z. GALIL, J. SEIFERAS, Saving space in fast string-matching, SIAM J.Comput. 9 (1980) 417-438.

[GS 81] Z. GALIL, J. SEIFERAS, Linear-time string-matching using only a fixed number of local storage locations, Theoret. Comput. Sci. 13 (1981) 331-336.

[GS 83] Z. GALIL, J. SEIFERAS, Time-space optimal string-matching, J. Comput. Syst. Sci. 26 (1983) 280-294.

[Ga 78] R.G. GALLAGER, Variations on a theme by Huffman, I.E.E.E. Trans. Inform. Theory IT 24, 6 (1978) 668-674.

[GMS 80] J. GALLANT, D. MAIER, J.A. STORER, On finding minimal length superstrings, J. Comput. Syst. Sci. 20 (1980) 50-58.

[GJ 79] M.R. GAREY, D.S. JOHNSON, Computers and intractability: a guide to the theory of NP-completeness, Freeman, New York, 1979.

[Gi 93] R. GIANCARLO, The suffix tree of a square matrix, with applications, in: (Proc. Symp. On Discrete Algorithms, 1993). GR 86] A. GIBBONS, W. RYTTER, On the decidability of some problems about rational subsets of free partially commutative monoids, Theoret. Comput. Sci. 48 (1986) 329-337.

[GR 88] A. GIBBONS, W. RYTTER, Efficient parallel algorithms, Cambridge University Press, Cambridge, 1988.

[GR 89] A. GIBBONS, W. RYTTER, Optimal parallel algorithm for dynamic expression evaluation and application to context-free recognition, Information and Computation 81, 1 (1989) 32-45.

[GB 91] G.H. GONNET, R. BAEZA-YATES, Handbook of algorithms and data structures, Addison-Wesley, Reading, Mass., 1991.

[Gr 91] M. GROSS, Constructing lexicon-grammars, in: (B.T.S. Atkins & A. Zampolli eds, Computational approaches to the lexicon, Oxford University Press, 1991).

[GP 89] M. GROSS, D. PERRIN, editors, Electronic Dictionaries and Automata in Computational Linguistics, Lecture Notes in Computer Science 377, Springer- Verlag, Berlin, 1989.

[GO 80] L.J. GUIBAS, A.M. ODLYZKO, A new proof of the linearity of the Boyer-Moore string searching algorithm, SIAM J.Comput. 9 (1980) 672-682.

[GO 81a] L.J. GUIBAS, A.M. ODLYZKO, Periods in strings, J. Comb. Th. A 30 (1981) 19- 42.

[GO 81b] L.J. GUIBAS, A.M. ODLYZKO, String overlaps, pattern matching and non- transitive games, J. Comb. Th. A 30 (1981) 183-208.

[HD 80] P.A.V. HALL, G.R. DOWLING, Approximate string-matching, ACM Comput.Surv. 12 (1980) 381-402.

[Ha 93] C. HANCART, On Simon’s string searching algorithm, Inf. Process. Lett. 47 (1993).

[HPS 92] G. HANSEL, D. PERRIN, I. SIMON, Compression and entropy, in: (STACS 92, A. Finkel and M. Jantzen eds., LNCS 577, Springer-Verlag, 1992) 515-528.

[HT 84] D. HAREL, R.E. TARJAN, Fast algorithms for finding nearest common ancestors, SIAM J.Comput. 13 (1984) 338-355.

[Ha 71] M.C. HARRISON, Implementation of the substring test by hashing, Comm. ACM 14, 12 (1971) 777-779.

[HR 85] A. HARTMAN, M. RODEH, Optimal Parsing of Strings, in: [AG 85] 155-167.

[HY 92] K. HASHIGUCHI, K. YAMADA, Two recognizable stringmatching problems over free partially commutative monoids, Theoret. Comput. Sci. 92 (1992) 77-86.

[HC 86] J-J. HÉBRARD, M. CROCHEMORE, Calcul de la distance par les sous-mots, R.A.I.R.O. Informatique Théorique 20 (1986) 441-456.

[He 87] G. HELD, Data Compression - Techniques and Applications, Hardware and Software Considerations, John Wiley & Sons, New York, NY, 1987. 2nd edition.

[Hi 75] D.S. HIRSCHBERG, A linear-space algorithm for computing maximal common subsequences, Comm. ACM 18, 6 (1975) 341-343.

[Hi 77] D.S. HIRSCHBERG, Algorithms for the longest common subsequence problem. J. ACM 24 (1977) 664-675.

[Hi 78] D.S. HIRSCHBERG, An information theoretic lower bound for the longest common subsequence problem, Inf. Process. Lett. 7 (1978) 40-41.

[HL 87a] D.S. HIRSCHBERG, L.L. LARMORE, New applications of failure functions, J. ACM 34 (1987) 616-625.

[HL 87b] D.S. HIRSCHBERG, L.L. LARMORE, The set LCS problem, Algorithmica 2 (1987) 91-95.

[HO 82] C.M. HOFFMAN, M.J. O’DONNELL, Pattern matching in trees, J. ACM 29, 1 (1982) 68-95.

[HU 79] J.E. HOPCROFT, J.D. ULLMAN, Introduction to automata, languages and computations, Addison-Wesley, Reading, Mass. (1979).

[Ho 80] R.N. HORSPOOL, Practical fast searching in strings, Software— Practice and Experience 10 (1980) 501-506.

[HD 84] W.J. HSU, M.W. DU, New algorithms for the LCS problem, J. Comput. Syst. Sci. 29 (1984) 133-152.

[Hu 51] D.A. HUFFMAN, A method for the construction of minimum redundancy codes, Proceedings of the I.R.E. 40 (1951) 1098-1101.

[Hu 88] A. HUME, A tale of two greps, Software—Practice and Experience 18 (1988) 1063-1072.

[HS 91] A. HUME, D.M. SUNDAY, Fast string searching, Software— Practice and Experience 21, 11 (1991) 1221-1248.

[HS 77] J.W. HUNT, T.G. SZYMANSKI, A fast algorithm for computing longest common subsequences, Comm. ACM 20 (1977) 350-353.

[IS 93] R. IDURY, A. SCHÄFFER, Multiple matching of rectangular patterns, in: (STOC’93, 1993).

[IS 92] C.S. ILIOPOULOS, W.F. SMYTH, Optimal algorithms for computing the canonical form of a circular string, Theoret. Comput. Sci. 92 (1992) 87-105.

[J 92] J. JÁjÁ, An introduction to Parallel Algorithms, Addison-Wesley, Reading, Mass., 1992.

[Ja 92] K. JANTKE, Polynomial time inference of general pattern languages, in: (STACS’92, Lecture Notes in Computer Science 166, 1992) 314-325.

[Jo 77] N.D. JONES, A note on linear time simulation of deterministic two-way pushdown automata. Inf. Process. Lett. 6, 4 (1977) 110-112.

[KMR 72] R.M. KARP, R.E. MILLER, A.L. ROSENBERG, Rapid identification of repeated patterns in strings, arrays and trees, in: (Proc. 4th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1972) 125-136.

[KR 87] R.M. KARP, M.O. RABIN, Efficient randomized patternmatching algorithms, IBM J. Res.Dev. 31 (1987) 249-260.

[KLP 89] Z.M. KEDEM, G.M. LANDAU, K.V. PALEM, Optimal parallel suffix-prefix matching algorithm and applications, in: (Proc. ACM Symposium on Parallel Algorithms, Association for Computing Machinery, New York, 1989), 388-398.

[KP 89] Z.M. KEDEM, K.V. PALEM, Optimal parallel algorithms for forest and term matching, Theoret. Comput. Sci. (1989).

[Kf 86] A.J. KFOURY, Square-free and overlap-free words, Report, Boston University, 1986.

[KS 92] J.Y. KIM, J. SHAWE-TAYLOR, An approximate stringmatching algorithm, Theoret. Comput. Sci. 92 (1992) 107-117.

[Kl 56] S.C. KLEENE, Representation of events in nerve nets and finite automata, in: (SHANNON and MCCARTHY eds, Automata studies, Princeton University Press, 1956) 3-40.

[Kn 85] D.E. KNUTH, Dynamic Huffman coding, J. Algorithms 6 (1985) 163-180.

[KP 71] D.E. KNUTH, V.R. PRATT, Automata theory can be useful, Report, Stanford University, 1971.

[KMP 77] D.E. KNUTH, J.H. MORRIS Jr, V.R. PRATT, Fast pattern matching in strings, SIAM J.Comput. 6 (1977) 323-350.

[KH 87] KER-I KO, CHIN-MING HUA, A note on the two variable pattern finding problem, J. Comput. Syst. Sci. 34 (1987) 75-86.

[Ko 89] S.R. KOSARAJU, Efficient tree pattern matching, FOCS’89 (1989) 178-183.

[LSV 87] G.M. LANDAU, B. SCHIEBER, U. VISHKIN, Parallel construction of a suffix tree, in: (Automata, Languages and Programming, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1987) 314-325.

[LV 86a] G.M. LANDAU, U. VISHKIN, Introducing efficient parallelism into approximate string-matching, STOC 18 (1986) 220-230.

[LV 86b] G.M. LANDAU, U. VISHKIN, Efficient string-matching with k mismatches, Theoret. Comput. Sci. 43 (1986) 239-249.

[LV 88] G.M. LANDAU, U. VISHKIN, Fast string-matching with k differences, J. Comput. Syst. Sci. 37 (1988) 63-78.

[LV 89] G.M. LANDAU, U. VISHKIN, Fast parallel and serial approximate string-matching, J. Algorithms 10 (1989) 158-169.

[Le 92] T. LECROQ, A variation on the Boyer-Moore algorithm, Theoret. Comput. Sci. 92 (1992) 119-144.

[LZ 76] A. LEMPEL, J. ZIV, On the Complexity of Finite Sequences, I.E.E.E. Trans. Inform.Theory IT 22, 1 (1976) 75-81.

[Li 81] L. LIU, On string pattern matching: a new model with a polynomial time algorithm, SIAM J.Comput. 10 (1981) 118-139.

[Lo 83] M. LOTHAIRE, Combinatorics on words, Addison-Wesley, Reading, Mass., 1983.

[LW 75] R. LOWRANCE, R.A. WAGNER, An extension of the stringto-string correction problem, J. ACM 25 (1975) 177-183.

[LS 62] R.C. LYNDON, M.P. SCHTZENBERGER, The equation aM = bNcP in a free group, Michigan Math. J. 9 (1962) 422-432.

[Ma 77] D. MAIER, The complexity of some problems on subsequences and supersequences, J. ACM 25 (1977) 322-336.

[MS 77] D. MAIER, J.A. STORER, A note on the complexity of superstring problem, Report 233, Computer Science Lab., Princetown University, 1977.

[Ma 89] M.G. MAIN, Detecting leftmost maximal periodicities, Discrete Applied Math. 25 (1989) 145-153.

[ML 79] M.G. MAIN, R.J. LORENTZ, An O(n log n) algorithm for finding repetition in a string, TR CS-79-056, Washington State University, Pullman, 1979.

[ML 84] M.G. MAIN, R.J. LORENTZ, An O(n log n) algorithm for finding all repetitions in a string, J. Algorithms (1984) 422-432.

[ML 85] M.G. MAIN, R.J. LORENTZ, Linear time recognition of squarefree strings, in: [AG 85] 271-278.

[MR 80] M.E. MAJSTER, A. RYSER, Efficient on-line construction and correction of position trees, SIAM J.Comput. 9, 4 (1980) 785-807.

[Ma 75] G. MANACHER, A new linear time on-line algorithm for finding the smallest initial palindrome of the string, J. ACM 22 (1975) 346-351.

[Ma 76] G. MANACHER, An application of pattern matching to a problem in geometrical complexity, Inf. Process. Lett. 5 (1976) 6-7.

[Ma 89] U. MANBER, Introduction to algorithms, Addison-Wesley, Reading, Mass., 1989.

[MM 90] U. MANBER, E. MYERS, Suffix arrays: a new method for online string searches, in: (Proc. of 1st ACM-SIAM Symposium on Discrete Algorithms, American Mathematical Society, Providence, 1990) 319-327.

[MP 80] W.J. MASEK, M.S. PATERSON, A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20, 1 (1980) 18-31.

[McC 76] E.M. MCCREIGHT, A space-economical suffix tree construction algorithm, J. ACM 23, 2 (1976) 262-272.

[Mo 84] B. MONIEN, Deterministic two-way one-head pushdown automata are very powerful, Inf. Process. Lett. 18, 3 (1984) 239-242.

[MP 70] J.H. MORRIS Jr, V.R. PRATT, A linear pattern-matching algorithm, Report 40, University of California, Berkeley, 1970.

[Mo 68] D.R. MORRISON, PATRICIA - practical algorithm to retrieve information coded in alphanumeric, J. ACM 15 (1968) 514-534.

[My 86] E.W. MYERS, An O(ND) difference algorithm and its variations, Algorithmica 1 (1986) 251-266.

[MM 89] E.W. MYERS, W.MILLER, Approximate matching of regular expressions, Bull. Math. Biol. 51 (1989) 5-37.

[NKY 82] N. NAKATSU, Y. KAMBAYASHI, S. YAJIMA, A longest common subsequence algorithm suitable for similar text strings, Acta Informatica 18 (1982) 171-179.

[Ne 92] M. NELSON, The Data Compression Book, M&T Publishing, Inc., Redwood City, California, 1992.

[NC 92] J. NÉRAUD, M. CROCHEMORE, A string-matching interpretation of the equation xmyn = zp, Theoret. Comput. Sci. 92 (1992) 145-164.

[Pe 85] D. PERRIN, Words over a partially commutative alphabet, in: [AG 85] 329-340.

[Pe 90] D. PERRIN, Finite automata, in: (J. VAN LEEUWEN, editor, Handbook of Theoretical Computer Science, vol B, Formal models and semantics, Elsevier, Amsterdam, 1990) 1-57.

[Qu 92] R.W. QUONG, Fast average-case pattern matching by multiplexing sparse tables, Theoret. Comput. Sci. 92 (1992) 165-179.

[RS 59] M.O. RABIN, D. SCOTT, Finite automata and their decision problems, IBM J. Research and Development 3 (1959) 114-125. Reprinted in: (E.F. MOORE ed, Sequential machines: selected papers, Addison-Wesley, Reading, Mass., 1964) 63-91.

[Ra 85] M.O. RABIN, Discovering repetitions in strings, in: [AG 85] 279-288.

[Ré 89] M. RÉGNIER, Knuth-Morris-Pratt algorithm: an analysis, in: (MFCS’89, Lecture Notes in Computer Science 379, Springer-Verlag, Berlin, 1989) 431-444.

[RR 93] M. RÉGNIER, L. ROSTAMI, A unifying look at d-dimensional periodicities and space coverings, in: (Combinatorial Pattern Matching, 1993).

[RS 85] A. RESTIVO, S. SALEMI, Some decision results on nonrepetitive words, in: [AG 85] 289-295.

[Re 92] D. REVUZ, Minimization of acyclic deterministic automata in linear time, Theoret. Comput. Sci. 92 (1992) 181-189.

[Ri 77] R.L. RIVEST, On the worst case behavior of string searching algorithms, SIAM J.Comput. 6, 4 (1977) 669-674.

[RT 85] Y. ROBERT, M. TCHUENTE, A systolic array for the longest common subsequence problem, Inf. Process. Lett. 21 (1885) 191-198.

[RPE 81] M. RODEH, V.R. PRATT, S. EVEN, Linear algorithm for data compression via string-matching, J. ACM 28 (1981) 16-24.

[Ry 80] W. RYTTER, A correct preprocessing algorithm for Boyer-Moore string searching, SIAM J.Comput. 9 (1980) 509-512.

[Ry 85] W. RYTTER, The complexity of two-way pushdown automata and recursive programs, in: [AG 85] 341-356.

[Ry 86] W. RYTTER, The space complexity of the unique decipherability problem, Inf. Process. Lett. 23 (1986) 1-3.

[Ry 88] W. RYTTER, On efficient computations of costs of paths of a grid graph, Inf. Process. Lett. 29 (1988) 71-74.

[Ry 89] W. RYTTER, On the parallel transformations of regular expressions to nondeterministic finite automata, Inf. Process. Lett. 31 (1989) 103-109.

[RD 90] W. RYTTER, K. DIKS, On optimal parallel computations for sequences of brackets, in: [Ca 90] 92-105.

[Sa 89] G. SALTON, Automatic Text Processing, Addison-Wesley, Reading, Mass., 1989.

[SK 83] D. SANKOFF, J.B. KRUSKAL, Time Warps, String Edits and Macromolecules: the Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, Mass., 1983.

[Sc 88] R. SCHABACK. On the expected sublinearity of the Boyer-Moore string searching algorithm, SIAM J.Comput. 17 (1988) 648-658.

[SV 88] B. SCHIEBER, U. VISHKIN, On finding lowest common ancestors: simplification and parallelization, SIAM J.Comput. 17 (1988) 1253-1262.

[Se 88] R. SEDGEWICK, Algorithms, Addison-Wesley, Reading, Mass., 1988. 2nd edition.

[SG 77] J. SEIFERAS, Z. GALIL, Real time recognition of substring repetition and reversal, Math. Syst. Theory 11 (1977) 111-146.

[Se 77] S.M. SELKOW, The tree to tree editing problem, Inf. Process. Lett. 6 (1977) 184- 186.

[Se 74a] P.H. SELLERS, An algorithm for the distance between two finite sequences, J. Comb. Th. A 16 (1974) 253-258.

[Se 74b] P.H. SELLERS, On the theory and computation of evolutionary distances, SIAM J. Appl. Math. 26 (1974) 787-793.

[Se 80] P.H. SELLERS, The theory and computation of evolutionary distances: pattern recognition, J. Algorithms 1 (1980) 359-373.

[Se 85] I. SEMBA, An efficient string searching algorithm, J. Inf. Process. 8 (1985) 101- 109.

[Sh 81] Y. SHILOACH, Fast canonization of circular strings, J. Algorithms 2 (1981) 107- 121.

[SV 81] Y. SHILOACH, U. VISHKIN, Finding a maximum, merging and sorting in parallel computation model, J. Algorithms 2 (1981) 88-102.

[Sl 83] A.O. SLISENKO, Detection of periodicities and string-matching in real time, J. Sov. Math. 22, 3 (1983) 1326-1387.

[Sm 82] G. DE V. SMIT, A comparison of three string-matching algorithms, Software - Practice and Experience 12 (1982) 57-66.

[Sm 90] P.D. SMITH, An introduction to text processing, The MIT Press, Cambridge, Mass., 1990.

[Sp 86] J-C. SPEHNER, La reconaissance des facteurs d’un mot dans un texte, Theoret. Comput. Sci. 48 (1986) 35-52.

[St 77] J.A. STORER, NP-completeness results concerning data compression, Report 234, Princetown University, 1977.

[SS 78] J.A. STORER, T.G. SZYMANSKI, The macro model for data compression, in: (Proc. 10th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1978) 30-39.

[St 88] J.A. STORER, Data Compression, Methods and Theory, Computer Science Press, Rockville, MD, 1988.

[Su 90] D.M. SUNDAY, A very fast substring search algorithm, Comm. ACM 33, 8 (1990) 132-142.

[TU 88] J. TARHIO, E. UKKONEN, A greedy approximation algorithm for constructing shortest common superstrings, Theoret. Comput. Sci. 57 (1988) 131-146.

[TU 90] J. TARHIO, E. UKKONEN, Boyer-Moore approach to approximate string-matching, in: (Proc. 2nd Scandinavian Workshop in Algorithmic Theory, Lecture Notes in Computer Science 447, Springer-Verlag, Berlin, 1990).

[Th 68] K. THOMPSON, Regular expression search algorithm, Comm. ACM 11 (1968) 419-422.

[Ti 84] W.F. TICHY, The string to string correction problem with block moves, ACM Trans. Comput. Syst. 2 (1984) 309-321.

[Uk 85a] E. UKKONEN, Finding approximate patterns in strings, J. Algorithms 6 (1985) 132-137.

[Uk 85b] E. UKKONEN, Algorithms for approximate string-matching, Information and Control 64 (1985) 100-118.

[Uk 92] E. UKKONEN, Approximate string-matching with q-grams and maximal matches, Theoret. Comput. Sci. 92 (1992) 191-211.

[Uk 92] E. UKKONEN, Constructing suffix trees on-line in linear time, in: (IFIP’92).

[UW 93] E. UKKONEN, D. WOOD, Approximate string-matching with suffix automata, Algorithmica (1993). To appear.

[Vi 85] U. VISHKIN, Optimal parallel pattern matching in strings, Information and Control 67 (1985) 91-113.

[Vi 91] U. VISHKIN, Deterministic sampling - A new technique for fast pattern matching, SIAM J.Comput. 20, 1 (1991) 22-40.

[Vi 87] J.S. VITTER, Design and analysis of dynamic Huffman codes, J. ACM 34 (1987) 825-845.

[Wa 74] R.A. WAGNER, Order-n correction for regular languages, Comm. ACM 17, 6 (1974) 265-268.

[Wa 75] R.A. WAGNER, On the complexity of extended string-to-string correction problem, in: (Proc. 7th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1975) 218-223.

[WF 74] R.A. WAGNER, M.J. FISCHER, The string-to-string correction problem, J. ACM 21 (1974) 168-178.

[Wa 89] M.S. WATERMAN, Mathematical methods for DNA sequences, CRC Press, Boca Raton, Florida, 1989.

[We 73] P. WEINER, Linear pattern matching algorithms, in: (Proc. 14th IEEE Annual Symposium on Switching and Automata Theory, Institute of Electrical Electronics Engineers, New York, 1973) 1-11.

[We 84] T.A. WELCH, A Technique for High-Performance Data Compression, I.E.E.E. Computer 17,6 (1984) 8-19.

[WNC 87] I.H. WITTEN, R.M. NEAL, J.G. CLEARY, Arithmetic coding for data compression, Commun. ACM 30, 6 (1987) 520-540.

[WC 76] C.K. WONG, A.K. CHANDRA, Bounds for the string editing problem, J. ACM 23 (1976) 13-16.

[WM 92] S. WU, U. MANBER, Fast text searching allowing errors, Comm. ACM 35, 10 (1992) 83-91.

[Ya 79] A.C. YAO, The complexity of pattern matching for a random string, SIAM J.Comput. 8 (1979) 368-387.

[Zi 92] M. ZIPSTEIN, Data compression with factor automata, Theoret. Comput. Sci. 92 (1992) 213-221.

[ZC 89] M. ZIPSTEIN, M. CROCHEMORE, Transducteurs arithmétiques, Rapport L.I.T.P. 89-12, Université Paris 7, 1989.

[ZL 77] J. ZIV, A. LEMPEL, A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory 23 (1977) 337-343.

[ZL 78] J. ZIV, A. LEMPEL, Compression of individual sequences via variable length- coding, IEEE Trans. Inform. Theory 24 (1978) 530-536.

[ZP 92] U. ZWICK, M.S. PATERSON, Lower bounds for stringmatching in the sequential comparison model, 1992, manuscript.