Probabilistic models for pattern statistics

Massimiliano Goldwurm; Roberto Radicioni

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 2, page 207-225
  • ISSN: 0988-3754

Abstract

top
In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences between these two stochastic models and their relationship with the rational probabilistic measures.

How to cite

top

Goldwurm, Massimiliano, and Radicioni, Roberto. "Probabilistic models for pattern statistics." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 207-225. <http://eudml.org/doc/249702>.

@article{Goldwurm2006,
abstract = { In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences between these two stochastic models and their relationship with the rational probabilistic measures. },
author = {Goldwurm, Massimiliano, Radicioni, Roberto},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Pattern statistics; Markov chains; probabilistic automata; rational formal series.; pattern statistics; rational formal series},
language = {eng},
month = {7},
number = {2},
pages = {207-225},
publisher = {EDP Sciences},
title = {Probabilistic models for pattern statistics},
url = {http://eudml.org/doc/249702},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Goldwurm, Massimiliano
AU - Radicioni, Roberto
TI - Probabilistic models for pattern statistics
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/7//
PB - EDP Sciences
VL - 40
IS - 2
SP - 207
EP - 225
AB - In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences between these two stochastic models and their relationship with the rational probabilistic measures.
LA - eng
KW - Pattern statistics; Markov chains; probabilistic automata; rational formal series.; pattern statistics; rational formal series
UR - http://eudml.org/doc/249702
ER -

References

top
  1. I.N. Bernstein, Modules over a ring of differential operators, study of the fundamental solutions of equations with constant coefficients. Functional Anal. Appl.5 (1971) 1–16 (Russian); pages 89–101 (English).  
  2. J. Berstel and C. Reutenauer, Rational Series and their Languages. Springer-Verlag, New York, Heidelberg, Berlin (1988).  Zbl0668.68005
  3. A. Bertoni, C. Choffrut, M. Goldwurm and V. Lonati, On the number of occurrences of a symbol in words of regular languages. Theoret. Comput. Sci.302 (2003) 431–456.  Zbl1044.68083
  4. A. Bertoni, C. Choffrut, M. Goldwurm and V. Lonati, Local limit properties for pattern statistics and rational models. Theory. Comput. Syst.39 (2006) 209–235.  Zbl1101.68085
  5. J. Bourdon and B. Vallée, Generalized pattern matching statistics. Mathematics and computer science II: algorithms, trees, combinatorics and probabilities, in Proc. of Versailles Colloquium. Birkhauser (2002) 249–265  Zbl1034.68024
  6. A. Denise, Génération aléatoire et uniforme de mots de langages rationnels. Theoret. Comput. Sci.159 (1996) 43–63.  
  7. P. Flajolet, P. Zimmerman and B. Van Cutsem, A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci.132 (1994) 1–35.  Zbl0799.68143
  8. M. Goldwurm and V. Lonati, Pattern occurrences in multicomponent models, in Proc. 22nd STACS. Lect. Notes Comput. Sci.3404 (2005) 680–692.  Zbl1118.68524
  9. G. Hansel and D. Perrin, Rational probability measures. Theoret. Comput. Sci.65 (1989) 171–188 (french version in Mots, edited by M. Lothaire, Hermes (1990) 335–357).  Zbl0669.60005
  10. M. Iosifescu, Finite Markov Processes and Their Applications. J. Wiley and Son (1980).  Zbl0436.60001
  11. P. Jacket and W. Szpankowski, Analytic approach to pattern matching, Chap. 7 in Applied Combinatorics on Words. Cambridge University Press (2005).  
  12. J.G. Kemeny and J.L. Snell, Finite Markov Chains. Van Nostrand (1960).  Zbl0089.13704
  13. L. Lipshitz, D-finite power series. J. Algebra122 (1989) 353–373.  Zbl0695.12018
  14. P. Nicodème, B. Salvy and P. Flajolet, Motif statistics. Theoret. Comput. Sci.287 (2002) 593–617.  Zbl1061.68118
  15. A. Paz, Introduction to Probabilistic Automata. Academic Press (1971).  Zbl0234.94055
  16. M. Régnier and W. Szpankowski, On pattern frequency occurrences in a Markovian sequence. Algorithmica22 (1998) 621–649.  Zbl0918.68108
  17. A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978).  Zbl0377.68039
  18. E. Seneta, Non-negative Matrices and Markov Chains. Springer-Verlag (1981).  Zbl0471.60001
  19. R.P. Stanley, Differentiably finite power series. Eur. J. Combin.1 (1980) 175–188.  Zbl0445.05012

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.