The coincidence of the weak index and Borel hierarchies for weakly recognizable languages
Statement
A weakly recognizable language is a language recognized by a weak alternating automaton, and its weak index is the automaton index appearing in the corresponding weak index hierarchy. The Borel hierarchy is the hierarchy of classes of sets obtained from open sets by countable unions and complements.
Weak index–Borel hierarchy conjecture. For weakly recognizable languages, the weak index hierarchy and the Borel hierarchy coincide; equivalently, every weakly recognizable -language can be recognized by a weak -automaton, and dually every weakly recognizable -language can be recognized by a weak -automaton.
The preceding corollary establishes one implication, namely that weak automata of the indicated indices recognize languages in the corresponding Borel classes. The converse is asserted here but is not established in the supplied text.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.