arXiv Open Access 2018

Regular omega-Languages with an Informative Right Congruence

Dana Angluin Dana Fisman
Lihat Sumber

Abstrak

A regular language is almost fully characterized by its right congruence relation. Indeed, a regular language can always be recognized by a DFA isomorphic to the automaton corresponding to its right congruence, henceforth the Rightcon automaton. The same does not hold for regular omega-languages. The right congruence of a regular omega-language is not informative enough; many regular omega-languages have a trivial right congruence, and in general it is not always possible to define an omega-automaton recognizing a given language that is isomorphic to the rightcon automaton. The class of weak regular omega-languages does have an informative right congruence. That is, any weak regular omega-language can always be recognized by a deterministic Büchi automaton that is isomorphic to the rightcon automaton. Weak regular omega-languages reside in the lower levels of the expressiveness hierarchy of regular omega-languages. Are there more expressive sub-classes of regular omega languages that have an informative right congruence? Can we fully characterize the class of languages with a trivial right congruence? In this paper we try to place some additional pieces of this big puzzle.

Topik & Kata Kunci

Penulis (2)

D

Dana Angluin

D

Dana Fisman

Format Sitasi

Angluin, D., Fisman, D. (2018). Regular omega-Languages with an Informative Right Congruence. https://arxiv.org/abs/1809.03108

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2018
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓