Deciding the Borel complexity of regular tree languages
classification
💻 cs.LO
cs.FLmath.LO
keywords
regulartreeborellanguagewhetherbelongsclasscomplexity
read the original abstract
We show that it is decidable whether a given a regular tree language belongs to the class ${\bf \Delta^0_2}$ of the Borel hierarchy, or equivalently whether the Wadge degree of a regular tree language is countable.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.