conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Nathanaël Fijalkow author A1B5DD72-E997-11E9-8398-E808B6C6ADC0 KrCh department LATA: Language and Automata Theory and Applications Rigorous Systems Engineering project 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 &quot;eventually&quot;. 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. Springer2011Tarragona, Spain eng 1101.172710.1007/978-3-642-21254-3_16 6638216 - 226 Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Finitary Languages,” 6638:216–26. Springer, 2011. <a href="https://doi.org/10.1007/978-3-642-21254-3_16">https://doi.org/10.1007/978-3-642-21254-3_16</a>. Chatterjee K, Fijalkow N. 2011. Finitary languages. LATA: Language and Automata Theory and Applications, LNCS, vol. 6638, 216–226. K. Chatterjee, N. Fijalkow, in:, Springer, 2011, pp. 216–226. Chatterjee, K., &#38; Fijalkow, N. (2011). Finitary languages (Vol. 6638, pp. 216–226). Presented at the LATA: Language and Automata Theory and Applications, Tarragona, Spain: Springer. <a href="https://doi.org/10.1007/978-3-642-21254-3_16">https://doi.org/10.1007/978-3-642-21254-3_16</a> 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, Krishnendu, and Nathanaël Fijalkow. <i>Finitary Languages</i>. Vol. 6638, Springer, 2011, pp. 216–26, doi:<a href="https://doi.org/10.1007/978-3-642-21254-3_16">10.1007/978-3-642-21254-3_16</a>. Chatterjee K, Fijalkow N. Finitary languages. In: Vol 6638. Springer; 2011:216-226. doi:<a href="https://doi.org/10.1007/978-3-642-21254-3_16">10.1007/978-3-642-21254-3_16</a> 33472018-12-11T12:02:48Z2024-10-09T20:54:28Z