While this submission is a draft, it cannot be used by other submissions.

Proof of `Determinization of infinite-word automata`

groundedproofs/Lax369799Proofs/OmegaDeterminization.lean · lax-369799

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Safra's construction gives a deterministic Muller automaton. Latest appearance records convert its condition to parity; reversal around an even bound gives the least-priority convention used for branches. The Safra and appearance-record proofs are adapted from the ancillary Lean development of Bojańczyk, Casares, Manthe and Parys (2026).