Kleene Theorems for Lasso Languages and $ω$-Languages
Abstrak
Automata operating on pairs of words were introduced as an alternative way of capturing acceptance of regular $ω$-languages. Families of DFAs and lasso automata operating on such pairs followed, giving rise to minimisation algorithms, a Myhill-Nerode theorem and language learning algorithms. Yet Kleene theorems for such a well-established class are still missing. We introduce rational lasso languages and expressions, show a Kleene theorem for lasso languages and explore the connection between rational lasso and $ω$-expressions, which yields a Kleene theorem for $ω$-languages with respect to saturated lasso automata. For one direction of the Kleene theorems, we also provide a Brzozowski construction for lasso automata from rational lasso expressions.
Topik & Kata Kunci
Penulis (1)
Mike Cruchten
Akses Cepat
- Tahun Terbit
- 2024
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓