---
_id: '3347'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Nathanaël
  full_name: Fijalkow, Nathanaël
  id: A1B5DD72-E997-11E9-8398-E808B6C6ADC0
  last_name: Fijalkow
citation:
  ama: '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>'
  apa: '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>'
  chicago: 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>.
  ieee: '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.'
  ista: 'Chatterjee K, Fijalkow N. 2011. Finitary languages. LATA: Language and Automata
    Theory and Applications, LNCS, vol. 6638, 216–226.'
  mla: 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>.
  short: K. Chatterjee, N. Fijalkow, in:, Springer, 2011, pp. 216–226.
conference:
  end_date: 2011-05-31
  location: Tarragona, Spain
  name: 'LATA: Language and Automata Theory and Applications'
  start_date: 2011-05-26
corr_author: '1'
date_created: 2018-12-11T12:02:48Z
date_published: 2011-06-16T00:00:00Z
date_updated: 2024-10-09T20:54:28Z
day: '16'
department:
- _id: KrCh
doi: 10.1007/978-3-642-21254-3_16
external_id:
  arxiv:
  - '1101.1727'
fulldoi: https://doi.org/10.1007/978-3-642-21254-3_16
intvolume: '      6638'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1101.1727
month: '06'
oa: 1
oa_version: Preprint
page: 216 - 226
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3274'
quality_controlled: '1'
scopus_import: 1
status: public
title: Finitary languages
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6638
year: '2011'
...