๐ฎ
๐ฎ
The Ethereal
Regular omega-Languages with an Informative Right Congruence
September 10, 2018 ยท The Ethereal ยท ๐ International Symposium on Games, Automata, Logics and Formal Verification
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Dana Angluin, Dana Fisman
arXiv ID
1809.03108
Category
cs.FL: Formal Languages
Cross-listed
cs.LG
Citations
14
Venue
International Symposium on Games, Automata, Logics and Formal Verification
Last Checked
1 month ago
Abstract
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.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Formal Languages
๐ฎ
๐ฎ
The Ethereal
Supervisor Synthesis to Thwart Cyber Attack with Bounded Sensor Reading Alterations
๐ฎ
๐ฎ
The Ethereal
An Abstraction-Based Framework for Neural Network Verification
๐ฎ
๐ฎ
The Ethereal
Recurrent Neural Networks as Weighted Language Recognizers
๐ฎ
๐ฎ
The Ethereal
TeSSLa: Temporal Stream-based Specification Language
๐ฎ
๐ฎ
The Ethereal