Computer Science Department
School of Computer Science, Carnegie Mellon University


Extending Automated Compositional Verification to
the Full Class of Omega-Regular Languages

Azadeh Farzan, Yu-Fang Chen, Edmund M. Clarke
Yih-Kuen Tsay, Bow-Yaw Wang

March 2008


Keywords: Model checking, compositional verification, learning algorithm, assume-guarantee reasoning, Büchi Automata, regular languages, omega-regular languages

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 Σ *.

19 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by