An alternative characterization of the Mostowksi index for omega-regular tree languages

The Mostowski index problem for tree languages is a long-standing problem: given a tree language, what is the minimal number of priorities required to recognize it with a non-deterministic parity automaton? In their 2008 paper, Colcombet and Löding reduced this problem to a boundedness question on distance-parity automata. This proof used complex machinery which makes it less accessible than ideal, and uses the less standard model of distance parity automata. In this joint work with Karoliina Lehtinen, we revisit this result, and propose a simplified proof. We combined tools developed by Lehtinen to solve parity games in quasi-polynomial time, and hierarchical counters as used by Colcombet and Löding. We hope to use this result to relate the Mostowski index problem with the theory of universal trees, as developed to solve parity games.

Authors

• Olivier Idir

Keywords

No keywords are indexed for this paper.