We give asymptotic estimates of the frequency of occurrences of a symbol in a random word Generated by any bicomponent stochastic model. More precisely, we consider the random variable Y-n representing the number of occurrences of a given symbol in a word of length n generated at random; the stochastic model is defined by a rational formal series r having a linear representation with two primitive components. This model includes the case when r is the product or the sum of two primitive rational formal series. We obtain asymptotic evaluations for the mean value and the variance of Yn and its limit distribution.

Frequency of symbol occurrences in bicomponent stochastic models / D. de Falco, M. Goldwurm, V. Lonati. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 327:3(2004), pp. 269-300. ((Intervento presentato al 7. convegno International Conference on Developments in Language Theory tenutosi a Szeged nel 2003.

Frequency of symbol occurrences in bicomponent stochastic models

D. de Falco
Primo
;
M. Goldwurm
Secondo
;
V. Lonati
Ultimo
2004

Abstract

We give asymptotic estimates of the frequency of occurrences of a symbol in a random word Generated by any bicomponent stochastic model. More precisely, we consider the random variable Y-n representing the number of occurrences of a given symbol in a word of length n generated at random; the stochastic model is defined by a rational formal series r having a linear representation with two primitive components. This model includes the case when r is the product or the sum of two primitive rational formal series. We obtain asymptotic evaluations for the mean value and the variance of Yn and its limit distribution.
automata and formal languages; limit distributions; pattern statistics; rational formal series
Settore INF/01 - Informatica
Settore MAT/06 - Probabilita' e Statistica Matematica
2004
Article (author)
File in questo prodotto:
File Dimensione Formato  
duec_def1.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 540.77 kB
Formato Adobe PDF
540.77 kB Adobe PDF Visualizza/Apri
1-s2.0-S0304397504004827-main.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 500.23 kB
Formato Adobe PDF
500.23 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/4914
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
social impact