Time filter

Source Type

Chatterjee K.,IST Institute of Science and Technology | Fijalkow N.,IST Institute of Science and Technology | Fijalkow N.,Ecole Normale Superieure de Cachan
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

The class of ω-regular languages provides a robust specification language in verification. Every ω-regular condition can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens "eventually". Finitary liveness was proposed by Alur and Henzinger as a stronger formulation of liveness [2]. It requires that there exists an unknown, fixed bound b such that something good happens within b transitions. In this work we consider automata with finitary acceptance conditions defined by finitary Büchi, parity and Streett languages. We give their topological complexity of acceptance conditions, and present a regular-expression characterization of the languages they express. We provide a classification of finitary and classical automata with respect to the expressive power, and give optimal algorithms for classical decisions questions on finitary automata. We (a) show that the finitary languages are ∑2 0-complete; (b) present a complete picture of the expressive power of various classes of automata with finitary and infinitary acceptance conditions; (c) show that the languages defined by finitary parity automata exactly characterize the star-free fragment of ωB-regular languages [4]; and (d) show that emptiness is NLOGSPACE-complete and universality as well as language inclusion are PSPACE-complete for finitary automata. © 2011 Springer-Verlag.


Chatterjee K.,IST Institute of Science and Technology | Chatterjee K.,Ecole Polytechnique Federale de Lausanne | Doyen L.,Ecole Normale Superieure de Cachan | Henzinger T.A.,Ecole Polytechnique Federale de Lausanne
Logical Methods in Computer Science | Year: 2010

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit-average, or discounted-sum of the transition weights. The value of a word w is the supremum of the values of the runs over w. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be non-ω-regular for deterministic limit-average and discounted-sum automata, while this set is always ω-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the ω-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights 0 or 1 and show that they are as expressive as general weighted automata in the limit-average case, but not in the discountedsum case. Third, for quantitative languages L1 and L2, we consider the operations max(L1, L2), min(L1, L2), and 1 -L1, which generalize the boolean operations on languages, as well as the sum L1+L2. We establish the closure properties of all classes of quantitative languages with respect to these four operations. © K. Chatterjee, L. Doyen, and T. A. Henzinger.


Chatterjee K.,IST Institute of Science and Technology | Henzinger T.A.,IST Institute of Science and Technology | Horn F.,IST Institute of Science and Technology | Horn F.,University Paris Diderot
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

We consider two-player graph games whose objectives are request-response condition, i.e conjunctions of conditions of the form "if a state with property Rq is visited, then later a state with property Rp is visited". The winner of such games can be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we close this gap by showing that this problem is, in fact, EXPTIME-complete. We show that the problem becomes PSPACE-complete if we only consider games played on DAGs, and NP-complete or PTIME-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition). We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case. © 2011 Springer-Verlag.

Loading IST Institute of Science and Technology collaborators
Loading IST Institute of Science and Technology collaborators