Local limit laws for symbol statistics in bicomponent rational models

Massimiliano Goldwurm*, Jianyi Lin, Marco Vignati

*Autore corrispondente per questo lavoro

Risultato della ricerca: Contributo in rivistaArticolo in rivistapeer review

Abstract

We study the local limit distribution of the number of occurrences of a symbol in words of length n generated at random in a regular language according to a rational stochastic model. We present an analysis of the main local limits when the finite state automaton defining the stochastic model consists of two primitive components. The limit distributions depend on several parameters and conditions, such as the main constants of mean value and variance of our statistics associated with the two components, and the existence of communications from the first to the second component. The convergence rate of these results is always of order $O(n^-1/2)$. For the same statistics we also prove an analogous $O(n^-1/2)$ convergence rate of the Gaussian local limit law whenever the stochastic model consists of one primitive component.
Lingua originaleEnglish
pagine (da-a)N/A-N/A
Numero di pagine18
RivistaTheoretical Computer Science
Volume970
DOI
Stato di pubblicazionePubblicato - 2023

Keywords

  • Automata and formal languages
  • Limit distributions
  • Regular languages
  • Pattern statistics
  • Rational series
  • Local limit laws

Fingerprint

Entra nei temi di ricerca di 'Local limit laws for symbol statistics in bicomponent rational models'. Insieme formano una fingerprint unica.

Cita questo