Control of ω-automata under state fairness assumptions

✍ Scribed by J.G. Thistle; R.P. Malhamé

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 113 KB
• Volume: 33
• Category: Article
• ISSN: 0167-6911
• DOI: 10.1016/s0167-6911(97)00106-0

✦ Synopsis

This article studies the deadlock-free control of ÿnite automata subject to speciÿcations in the form of Rabin acceptance conditions. Automata are assumed to satisfy a state fairness condition, whereby any transition that is inÿnitely often enabled (by both the underlying dynamics and the control mechanism) must eventually occur. The problem of computing the automaton's controllability subset -the set of states from which it can be controlled to satisfy its acceptance condition -is solved through a ÿxpoint characterization of this state subset. The state fairness condition simpliÿes the ÿxpoint characterization and allows the controllability subset to be computed in polynomial time. The problem represents a modiÿed version of Church's problem and the emptiness problem for automata on inÿnite trees, and has potential applications to the veriÿcation and synthesis of reactive systems and to supervisory control.