Deciding the Borel complexity of regular tree languages
Alessandro FacchiniHenryk Michalewski
所有作者
Alessandro FacchiniHenryk Michalewski
文献摘要
We show that it is decidable whether a given a regular tree language belongs
to the class Δ20 of the Borel hierarchy, or equivalently whether
the Wadge degree of a regular tree language is countable.