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...

Full description

Bibliographic Details
Main Authors: Colcombet, Thomas, Löding, Christof
Other Authors: 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
Language:English
Published: HAL CCSD 2008
Subjects:
Automata
Infinite trees
Fix-points
Mostowski
Rabin
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Iceland
Online Access:https://hal.science/hal-00347194
https://doi.org/10.1007/978-3-540-70583-3
Description
Summary: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.

Similar Items