Saddle point method in the analysis of pattern statistics for regular languages

Jianyi Lin, M. Goldwurm, M. Vignati

Risultato della ricerca: Contributo in libroContributo a convegno

Abstract

In a recent work we have determined the local limit distribution of pattern statistics representing the number of occurrences of a symbol in words of length n in a regular language generated at random according to a suitable stochastic model. Such a model is defined by a finite automaton with weights in ℝ+, consisting of two primitive components, having some transition from the first to the second component. In the present work we extend those results to the case when there is no communication among the components, and hence the associated formal series is the sum of two rational series recognized by finite state automata with primitive transition matrix. We obtain local limit laws of Gaussian type when there is a dominant component or when, in equipotent case, the main terms of mean value and variance are equal. On the contrary, if these terms are not the same then the local limit distribution is a convex combination of Gaussian laws. All convergence rates of our limits are of the order O(n−1/2). This completes the analysis of local limit laws of symbol statistics under a bicomponent stochastic model1.
Lingua originaleEnglish
Titolo della pubblicazione ospiteCEUR Workshop Proceedings
Pagine78-90
Numero di pagine13
Volume2504
Stato di pubblicazionePubblicato - 2019
Evento20th Italian Conference on Theoretical Computer Science, ICTCS 2019 - ita
Durata: 9 set 201911 set 2019

Serie di pubblicazioni

NomeCEUR WORKSHOP PROCEEDINGS

Convegno

Convegno20th Italian Conference on Theoretical Computer Science, ICTCS 2019
Cittàita
Periodo9/9/1911/9/19

Keywords

  • Limit distributions
  • Local limit laws
  • Pattern statistics
  • Rational formal series
  • Saddle Point Method

Fingerprint

Entra nei temi di ricerca di 'Saddle point method in the analysis of pattern statistics for regular languages'. Insieme formano una fingerprint unica.

Cita questo