Research proof index

The ω-regular language accepted by a finite-state NA M is the union of ω-languages of the form (M.PairLang s0 sa) * (M.PairLang sa sa)^ω, where s0 and sa range over initial and accepting states respectively.

If accepting states appear infinitely often in a run and φ : Stream' ℕ is StrictMono, then there exist infinitely many m such that the segment of the run from φ(m) to φ(m + 1) contains at least one accepting state.

The following result is technical and used to prove the saturation property of the Buchi congruence. Its main purpose is to "fill in" the states between the successive ss' m to produce a well-formed run in which the accepting states appear infinitely often. Note that ss needs to agree with ss' only at positions φ m: ∀ m, ss (φ m) = ss' m.

If M is finite-state, then M.PairAccLang acc s s' is regular for any pair of states s and s'. Note that we need to use the history NA construction to prove this result, because the NA needs to remember whether an accepting state has been visited.

If M is finite-state, then M.PairLang s s' is regular for any pair of states s and s'.

The ω-language accepted by a finite-state Büchi automaton is the finite union of ω-languages of the form L * M^ω, where all Ls and Ms are regular languages.