ProbXiv
Explorersign in
Problem archiveProblem record

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 Πn0\Pi^0_n-language can be recognized by a weak (0,n)(0,n)-automaton, and dually every weakly recognizable Σn0\Sigma^0_n-language can be recognized by a weak (1,n+1)(1,n+1)-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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.