Semidirect Product Decompositions for Periodic Regular Languages
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911791573893120 |
|---|---|
| author | Inoue, Yusuke Hashimoto, Kenji Seki, Hiroyuki |
| author_facet | Inoue, Yusuke Hashimoto, Kenji Seki, Hiroyuki |
| contents | The definition of period in finite-state Markov chains can be extended to regular languages by considering the transitions of DFAs accepting them. For example, the language $(ΣΣ)^*$ has period two because the length of a recursion (cycle) in its DFA must be even. This paper shows that the period of a regular language appears as a cyclic group within its syntactic monoid. Specifically, we show that a regular language has period $P$ if and only if its syntactic monoid is isomorphic to a submonoid of a semidirect product between a specific finite monoid and the cyclic group of order $P$. Moreover, we explore the relation between the structure of Markov chains and our result, and apply this relation to the theory of probabilities of languages. We also discuss the Krohn-Rhodes decomposition of finite semigroups, which is strongly linked to our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Semidirect Product Decompositions for Periodic Regular Languages Inoue, Yusuke Hashimoto, Kenji Seki, Hiroyuki Formal Languages and Automata Theory 68Q45, 68Q70 The definition of period in finite-state Markov chains can be extended to regular languages by considering the transitions of DFAs accepting them. For example, the language $(ΣΣ)^*$ has period two because the length of a recursion (cycle) in its DFA must be even. This paper shows that the period of a regular language appears as a cyclic group within its syntactic monoid. Specifically, we show that a regular language has period $P$ if and only if its syntactic monoid is isomorphic to a submonoid of a semidirect product between a specific finite monoid and the cyclic group of order $P$. Moreover, we explore the relation between the structure of Markov chains and our result, and apply this relation to the theory of probabilities of languages. We also discuss the Krohn-Rhodes decomposition of finite semigroups, which is strongly linked to our methods. |
| title | Semidirect Product Decompositions for Periodic Regular Languages |
| topic | Formal Languages and Automata Theory 68Q45, 68Q70 |
| url | https://arxiv.org/abs/2403.05088 |