×

Pattern statistics and Vandermonde matrices. (English) Zbl 1160.68412

Summary: We determine some limit distributions of pattern statistics in rational stochastic models. We present a general approach to analyze these statistics in rational models having an arbitrary number of strongly connected components. We explicitly establish the limit distributions in most significant cases; they are characterized by a family of unimodal density functions defined by means of confluent Vandermonde matrices.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Berstel, J.; Reutenauer, C., Rational Series and their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005
[2] Bertoni, A.; Choffrut, C.; Goldwurm, M.; Lonati, V., On the number of occurrences of a symbol in words of regular languages, Theoret. Comput. Sci., 302, 1-3, 431-456 (2003) · Zbl 1044.68083
[3] J. Bourdon, B. Vallée, Generalized pattern matching statistics, Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities. Proc. Versailles Colloquium, Birkhauser, 2002, pp. 249-265.; J. Bourdon, B. Vallée, Generalized pattern matching statistics, Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities. Proc. Versailles Colloquium, Birkhauser, 2002, pp. 249-265.
[4] Csàki, F. G., Some notes on the inversion of confluent Vandermonde matrices, IEEE Trans. Automat. Control, 20, 154-157 (1975) · Zbl 0299.93008
[5] de Falco, D.; Goldwurm, M.; Lonati, V., Frequency of symbol occurrences in bicomponent stochastic models, Theoret. Comput. Sci., 327, 3, 269-300 (2004) · Zbl 1071.68056
[6] Flajolet, P., Mathematical methods in the analysis of algorithms and data structures, (Börger, E., Trends in Theoretical Computer Science (1988), Computer Science Press: Computer Science Press Rock Ville, MD), 225-304
[7] Gnedenko, B. V., The Theory of Probability (1976), Mir Publishers: Mir Publishers Moscow, (translated by G. Yankovsky) · Zbl 0191.46702
[8] Goldwurm, M., Probabilistic estimation of the number of prefixes of a trace, Theoret. Comput. Sci., 92, 249-268 (1992) · Zbl 0747.68034
[9] Grabner, P.; Rigo, M., Additive functions with respect to numeration systems on regular languages, Monatshefte für Mathematik, 139, 205-219 (2003) · Zbl 1125.11008
[10] Guibas, L. J.; Odlyzko, A. M., Maximal prefix-synchronized codes, SIAM J. Appl. Math., 35, 401-418 (1978) · Zbl 0394.94024
[11] Guibas, L. J.; Odlyzko, A. M., String overlaps, pattern matching, and nontransitive games, J. Combin. Theory. Ser. A, 30, 2, 183-208 (1981) · Zbl 0454.68109
[12] P. Henrici, Applied and Computational Complex Analysis, Vol. 1, Wiley, UK, 1974.; P. Henrici, Applied and Computational Complex Analysis, Vol. 1, Wiley, UK, 1974. · Zbl 0313.30001
[13] P. Jokinen, E. Ukkonen, Two algorithms for approximate string matching in static texts, Proc. MFCS’91, Lecture Notes in Computer Science, Vol. 520, Springer, Berlin, 1991, pp. 240-248.; P. Jokinen, E. Ukkonen, Two algorithms for approximate string matching in static texts, Proc. MFCS’91, Lecture Notes in Computer Science, Vol. 520, Springer, Berlin, 1991, pp. 240-248. · Zbl 0776.68047
[14] Lancaster, P.; Tismenetsky, M., The Theory of Matrices (1985), Academic Press: Academic Press New York · Zbl 0516.15018
[15] Luther, U.; Rost, K., Matrix exponentials and inversions of confluent Vandermonde matrices, Electron. Trans. Numer. Anal., 18, 91-100 (2004) · Zbl 1065.34001
[16] Nicodeme, P.; Salvy, B.; Flajolet, P., Motif statistics, Theoret. Comput. Sci., 287, 2, 593-617 (2002) · Zbl 1061.68118
[17] Prum, B.; Rudolphe, F.; Turckheim, E., Finding words with unexpected frequencies in deoxyribonucleic acid sequence, J. Roy. Statist. Soc. Ser. B, 57, 205-220 (1995) · Zbl 0817.92012
[18] Régnier, M.; Szpankowski, W., On pattern frequency occurrences in a Markovian sequence, Algorithmica, 22, 4, 621-649 (1998) · Zbl 0918.68108
[19] Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[20] Sedgewick, R.; Flajolet, P., An Introduction to the Analysis of Algorithms (1996), Addison-Wesley: Addison-Wesley Reading, MA
[21] Seneta, E., Non-negative Matrices and Markov Chains (1981), Springer: Springer New York, Heidelberg, Berlin · Zbl 0471.60001
[22] E. Sutinen, W. Szpankowski, On the collapse of q-gram filtration, Proc. FUN with Algorithms, Elba, 1998, pp. 178-193.; E. Sutinen, W. Szpankowski, On the collapse of q-gram filtration, Proc. FUN with Algorithms, Elba, 1998, pp. 178-193.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.