Chatterjee, KrishnenduIST Austria ; Fijalkow, Nathanaël
Dediu, Adrian-Horia ; Inenaga, Shunsuke ; Martín-Vide, Carlos
The class of omega-regular languages provides a robust specification language in verification. Every omega-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. 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 Buchi, parity and Streett languages. We study languages expressible by such automata: we give their topological complexity and present a regular-expression characterization. We compare the expressive power of finitary automata and give optimal algorithms for classical decisions questions. We show that the finitary languages are Sigma 2-complete; we present a complete picture of the expressive power of various classes of automata with finitary and infinitary acceptance conditions; we show that the languages defined by finitary parity automata exactly characterize the star-free fragment of omega B-regular languages; and we show that emptiness is NLOGSPACE-complete and universality as well as language inclusion are PSPACE-complete for finitary parity and Streett automata.
216 - 226
LATA: Language and Automata Theory and Applications
2011-05-26 – 2011-05-31
Chatterjee K, Fijalkow N. Finitary languages. In: Dediu A-H, Inenaga S, Martín-Vide C, eds. Vol 6638. Springer; 2011:216-226. doi:10.1007/978-3-642-21254-3_16
Chatterjee, K., & Fijalkow, N. (2011). Finitary languages. In A.-H. Dediu, S. Inenaga, & C. Martín-Vide (Eds.) (Vol. 6638, pp. 216–226). Presented at the LATA: Language and Automata Theory and Applications, Tarragona, Spain: Springer. https://doi.org/10.1007/978-3-642-21254-3_16
Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Finitary Languages.” edited by Adrian-Horia Dediu, Shunsuke Inenaga, and Carlos Martín-Vide, 6638:216–26. Springer, 2011. https://doi.org/10.1007/978-3-642-21254-3_16.
K. Chatterjee and N. Fijalkow, “Finitary languages,” presented at the LATA: Language and Automata Theory and Applications, Tarragona, Spain, 2011, vol. 6638, pp. 216–226.
Chatterjee K, Fijalkow N. 2011. Finitary languages. LATA: Language and Automata Theory and Applications, LNCS, vol. 6638. 216–226.
Chatterjee, Krishnendu, and Nathanaël Fijalkow. Finitary Languages. Edited by Adrian-Horia Dediu et al., vol. 6638, Springer, 2011, pp. 216–26, doi:10.1007/978-3-642-21254-3_16.
Link(s) to Main File(s)