Published August 14, 2012
| Version v1
Conference paper
Acceptance Conditions for ω-Languages
Contributors
Others:
- Università degli Studi di Milano = University of Milan (UNIMI)
- Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- PRIN/MIUR project "Mathematical aspects and forthcoming applications of automata and formal languages"
- ANR-09-BLAN-0164,EMC,Emergence dans les modèles de calcul(2009)
Description
This paper investigates acceptance conditions for nite au-tomata recognizing ω-regular languages. Their expressive power and their position w.r.t. the Borel hierarchy is also studied. The full characterization for the conditions (ninf,), (ninf, ⊆) and (ninf, =) is given. The nal section provides a partial characterization of (f in, =).
Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.science/hal-01297584
- URN
- urn:oai:HAL:hal-01297584v1
Origin repository
- Origin repository
- UNICA