Localising Stochasticity in Weighted Automata
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914356480966656 |
|---|---|
| author | Agarwal, Smayan Thakkar, Aalok |
| author_facet | Agarwal, Smayan Thakkar, Aalok |
| contents | Weighted automata over the nonnegative reals form a fundamental model for quantitative languages. We show that, up to scaling, this model collapses to probabilistic automata.
Concretely, we prove that every weighted automaton whose transition matrix has spectral radius strictly less than one can be normalised, by a semantics-preserving rescaling of transition weights, into an equivalent locally stochastic probabilistic automaton. Thus, finite-mass weighted automata and probabilistic automata coincide up to normalisation. The construction is effective and relies on Perron-Frobenius theory. We further characterise probabilistic automata by stochastic regular expressions equipped with a geometrically weighted star.
Beyond the finite-mass setting, we show that the behaviour of an arbitrary weighted automaton admits a decomposition into an exponential growth rate and a normalised probabilistic component, separating quantitative growth from stochastic structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23805 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Localising Stochasticity in Weighted Automata Agarwal, Smayan Thakkar, Aalok Formal Languages and Automata Theory Weighted automata over the nonnegative reals form a fundamental model for quantitative languages. We show that, up to scaling, this model collapses to probabilistic automata. Concretely, we prove that every weighted automaton whose transition matrix has spectral radius strictly less than one can be normalised, by a semantics-preserving rescaling of transition weights, into an equivalent locally stochastic probabilistic automaton. Thus, finite-mass weighted automata and probabilistic automata coincide up to normalisation. The construction is effective and relies on Perron-Frobenius theory. We further characterise probabilistic automata by stochastic regular expressions equipped with a geometrically weighted star. Beyond the finite-mass setting, we show that the behaviour of an arbitrary weighted automaton admits a decomposition into an exponential growth rate and a normalised probabilistic component, separating quantitative growth from stochastic structure. |
| title | Localising Stochasticity in Weighted Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.23805 |