2.1k citations · 3.9k across the 42 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.LO2014
Deciding the Borel complexity of regular tree languages
Alessandro Facchini, Henryk Michalewski
We show that it is decidable whether a given a regular tree language belongs to the class of the Borel hierarchy, or equivalently whether the Wadge degree of a regula…
cs.FL2014★ 1 cited
Unambiguous Buchi is weak
Henryk Michalewski, Michał Skrzypczak
A non-deterministic automaton running on infinite trees is unambiguous if it has at most one accepting run on every tree. The class of languages recognisable by unambiguous tree au…