Local limit laws for symbol statistics in bicomponent rational models

DOI10.1016/J.TCS.2023.114051MaRDI QIDQ6168079zbMATH OpenOpenAlexFDO

Authors Massimiliano Goldwurm, Jianyi Lin, Marco Vignati

Publication date 8 August 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.09478

zbMATH Keywords

limit distributionsrational seriesregular languagesautomata and formal languageslocal limit lawspattern statistics

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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})$. We also prove an analogous $O(n^{-1/2})$ convergence rate to a Gaussian density of the same statistic whenever the stochastic models only consists of one (primitive) component.

Cites work

• scientific article; zbMATH DE number 3905045 (Why is no real title available?)
• scientific article; zbMATH DE number 3680816 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 2051177 (Why is no real title available?)
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)
• scientific article; zbMATH DE number 946251 (Why is no real title available?)
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Analytic combinatorics
• Central and local limit theorems applied to asymptotic enumeration
• Developments in Language Theory
• Distribution of additive functions with respect to numeration systems on regular languages
• Finite counting automata
• Frequency of symbol occurrences in bicomponent stochastic models
• Hidden word statistics
• Large deviation properties for patterns
• Local limit properties for pattern statistics and rational models
• Markov Chains
• Motif statistics.
• Non-negative matrices and Markov chains. 2nd ed
• On computing the coefficients of bivariate holonomic formal series
• On convergence rates in the central limit theorems for combinatorial structures
• On pattern frequency occurrences in a Markovian sequence
• On the diversity of pattern distributions in rational language.
• On the number of occurrences of a symbol in words of regular languages.

This page was built for publication: Local limit laws for symbol statistics in bicomponent rational models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168079)