2008 | OriginalPaper | Buchkapitel
Extending Automated Compositional Verification to the Full Class of Omega-Regular Languages
verfasst von : Azadeh Farzan, Yu-Fang Chen, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang
Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recent studies have suggested the applicability of learning to automated compositional verification. However, current learning algorithms fall short when it comes to learning
liveness
properties. We extend the automaton synthesis paradigm for the infinitary languages by presenting an algorithm to learn an
arbitrary
regular set of infinite sequences (an
ω
-regular language) over an alphabet
Σ
. Our main result is an algorithm to learn a nondeterministic Büchi automaton that recognizes an unknown
ω
-regular language. This is done by learning a unique projection of it on
Σ
*
using the framework suggested by Angluin for learning regular subsets of
Σ
*
.