The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
International audience Given a Rabin tree-language and natural numbers $i,j$, the language is said to be $i,j$-feasible if it is accepted by a parity automaton using priorities $\{i,i+1,.,j\}$. The $i,j$-feasibility induces a hierarchy over the Rabin-tree languages called the Mostowski hierarchy. In...
Main Authors: | , |
---|---|
Other Authors: | , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2008
|
Subjects: | |
Online Access: | https://hal.science/hal-00347194 https://doi.org/10.1007/978-3-540-70583-3 |
id |
ftunivnantes:oai:HAL:hal-00347194v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivnantes:oai:HAL:hal-00347194v1 2023-05-15T16:49:50+02:00 The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata Colcombet, Thomas Löding, Christof Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH) Reykjavik, Iceland 2008-07-06 https://hal.science/hal-00347194 https://doi.org/10.1007/978-3-540-70583-3 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-70583-3 hal-00347194 https://hal.science/hal-00347194 doi:10.1007/978-3-540-70583-3 Automata, Languages and Programming ICALP'08 https://hal.science/hal-00347194 ICALP'08, Jul 2008, Reykjavik, Iceland. pp.398-409, ⟨10.1007/978-3-540-70583-3⟩ Automata Infinite trees Fix-points Mostowski Rabin [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] info:eu-repo/semantics/conferenceObject Conference papers 2008 ftunivnantes https://doi.org/10.1007/978-3-540-70583-3 2023-02-08T03:33:24Z International audience Given a Rabin tree-language and natural numbers $i,j$, the language is said to be $i,j$-feasible if it is accepted by a parity automaton using priorities $\{i,i+1,.,j\}$. The $i,j$-feasibility induces a hierarchy over the Rabin-tree languages called the Mostowski hierarchy. In this paper we prove that the problem of deciding if a language is $i,j$-feasible is reducible to the uniform universality problem for distance-parity automata. Distance-parity automata form a new model of automata extending both the nested distance desert automata introduced by Kirsten in his proof of decidability of the star-height problem, and parity automata over infinite trees. Distance-parity automata, instead of accepting a language, attach to each tree a cost in $\omega+1$. The uniform universality problem consists in determining if this cost function is bounded by a finite value. Conference Object Iceland Université de Nantes: HAL-UNIV-NANTES |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
Automata Infinite trees Fix-points Mostowski Rabin [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
spellingShingle |
Automata Infinite trees Fix-points Mostowski Rabin [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Colcombet, Thomas Löding, Christof The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
topic_facet |
Automata Infinite trees Fix-points Mostowski Rabin [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
description |
International audience Given a Rabin tree-language and natural numbers $i,j$, the language is said to be $i,j$-feasible if it is accepted by a parity automaton using priorities $\{i,i+1,.,j\}$. The $i,j$-feasibility induces a hierarchy over the Rabin-tree languages called the Mostowski hierarchy. In this paper we prove that the problem of deciding if a language is $i,j$-feasible is reducible to the uniform universality problem for distance-parity automata. Distance-parity automata form a new model of automata extending both the nested distance desert automata introduced by Kirsten in his proof of decidability of the star-height problem, and parity automata over infinite trees. Distance-parity automata, instead of accepting a language, attach to each tree a cost in $\omega+1$. The uniform universality problem consists in determining if this cost function is bounded by a finite value. |
author2 |
Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH) |
format |
Conference Object |
author |
Colcombet, Thomas Löding, Christof |
author_facet |
Colcombet, Thomas Löding, Christof |
author_sort |
Colcombet, Thomas |
title |
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
title_short |
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
title_full |
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
title_fullStr |
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
title_full_unstemmed |
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata |
title_sort |
non-deterministic mostowski hierarchy and distance-parity automata |
publisher |
HAL CCSD |
publishDate |
2008 |
url |
https://hal.science/hal-00347194 https://doi.org/10.1007/978-3-540-70583-3 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Automata, Languages and Programming ICALP'08 https://hal.science/hal-00347194 ICALP'08, Jul 2008, Reykjavik, Iceland. pp.398-409, ⟨10.1007/978-3-540-70583-3⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-70583-3 hal-00347194 https://hal.science/hal-00347194 doi:10.1007/978-3-540-70583-3 |
op_doi |
https://doi.org/10.1007/978-3-540-70583-3 |
_version_ |
1766040014882340864 |