CISPA
Browse
cispa_all_3081.pdf (294.75 kB)

Approximate Automata for Omega-Regular Languages

Download (294.75 kB)
conference contribution
posted on 2023-11-29, 18:12 authored by Rayna DimitrovaRayna Dimitrova, Bernd FinkbeinerBernd Finkbeiner, Hazem Torfah
Automata over infinite words, also known as omega-automata, play a key role in the verification and synthesis of reactive systems. The spectrum of omega-automata is defined by two characteristics: the acceptance condition (e.g. Büchi or parity) and the determinism (e.g., deterministic or nondeterministic) of an automaton. These characteristics play a crucial role in applications of automata theory. For example, certain acceptance conditions can be handled more efficiently than others by dedicated tools and algorithms. Furthermore, some applications, such as synthesis and probabilistic model checking, require that properties are represented as some type of deterministic omega-automata. However, properties cannot always be represented by automata with the desired acceptance condition and determinism. In this paper we study the problem of approximating linear-time properties by automata in a given class. Our approximation is based on preserving the language up to a user-defined precision given in terms of the size of the finite lasso representation of infinite executions that are preserved. We study the state complexity of different types of approximating automata, and provide constructions for the approximation within different automata classes, for example, for approximating a given automaton by one with a simpler acceptance condition.

History

Preferred Citation

Rayna Dimitrova, Bernd Finkbeiner and Hazem Torfah. Approximate Automata for Omega-Regular Languages. In: International Symposium on Automated Technology for Verification and Analysis (ATVA). 2019.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Symposium on Automated Technology for Verification and Analysis (ATVA)

Legacy Posted Date

2020-05-25

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3081, title = "Approximate Automata for Omega-Regular Languages", author = "Dimitrova, Rayna and Finkbeiner, Bernd and Torfah, Hazem", booktitle="{International Symposium on Automated Technology for Verification and Analysis (ATVA)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC