Semidirect Product Decompositions for Periodic Regular Languages
<|reference_start|>Semidirect Product Decompositions for Periodic Regular Languages: 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 $(\Sigma\Sigma)^*$ 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.<|reference_end|>
@article{inoue2024semidirect,
    title={Semidirect Product Decompositions for Periodic Regular Languages},
    author={Yusuke Inoue, Kenji Hashimoto, Hiroyuki Seki},
    journal={arXiv preprint arXiv:2403.05088},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05088},
    primaryClass={cs.FL}
}