Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914255469543424 |
|---|---|
| author | Kostolányi, Peter Ravinger, Andrej |
| author_facet | Kostolányi, Peter Ravinger, Andrej |
| contents | Reversible weighted automata are introduced and considered in a specific setting where the weights are taken from a nontrivial locally finite commutative ring such as a finite field. It is shown that the supports of series realised by such automata are precisely the rational languages such that the idempotents in their syntactic monoids commute. In particular, this is true for reversible weighted automata over the finite field $\mathbb{F}_2$, where the realised series can be directly identified with such languages. A new automata-theoretic characterisation is thus obtained for the variety of rational languages corresponding to the pseudovariety of finite monoids $\mathbf{ECom}$, which also forms the Boolean closure of the reversible languages in the sense of J.-É. Pin. The problem of determining whether a rational series over a locally finite commutative ring can be realised by a reversible weighted automaton is decidable as a consequence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09409 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents Kostolányi, Peter Ravinger, Andrej Formal Languages and Automata Theory Reversible weighted automata are introduced and considered in a specific setting where the weights are taken from a nontrivial locally finite commutative ring such as a finite field. It is shown that the supports of series realised by such automata are precisely the rational languages such that the idempotents in their syntactic monoids commute. In particular, this is true for reversible weighted automata over the finite field $\mathbb{F}_2$, where the realised series can be directly identified with such languages. A new automata-theoretic characterisation is thus obtained for the variety of rational languages corresponding to the pseudovariety of finite monoids $\mathbf{ECom}$, which also forms the Boolean closure of the reversible languages in the sense of J.-É. Pin. The problem of determining whether a rational series over a locally finite commutative ring can be realised by a reversible weighted automaton is decidable as a consequence. |
| title | Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2601.09409 |