Lemma 33 — pinching
ProvedBuchiRabinIndex.LowerBound.lemma_33automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
Fix . Let be cycles in , and suppose one Rabin pair accepts both and . If
then accepts as well: and .
The containment is one-sided: the intermediate cycle must contain . All cycles and the pair are arbitrary, and no canonical-node or merged-pair restriction is imposed.
Differences from the source:
- encoding: states q_1,...,q_n and alphabet 2^(Q×Q) → Fin n with q_i represented by i−1 and Finset transition relations; reason: this is a bijective indexing of all states and letters
- encoding: labels are functions defined on the node set → labels extend by the empty set outside the node set, with a validity subtype; reason: the extension is unique and adds no histories or transitions
- encoding: deterministic transitions may fail to have a successor → Option history trees, with a dying trace rejected by every condition; reason: root deletion has no history-tree successor; no sink is added
- encoding: sets of actual history-tree transitions → sets in the ambient carrier of history/letter/history triples, with actual successors enforced in traces and cycles; reason: nonactual triples never occur in a trace or cycle; source transition sets embed unchanged
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Rabin set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound
/-- STOC 2027 submission #1731, lemma 33; statement only. -/
theorem lemma_33 (n : ℕ) (hn : 1 ≤ n)
(p : RabinPair (Edge (Fin n) (Letter n)))
(D1 D2 D : Set (Edge (Fin n) (Letter n)))
(h1 : Cycle (fullBuchi n hn) D1) (h2 : Cycle (fullBuchi n hn) D2)
(hD : Cycle (fullBuchi n hn) D) (hp1 : PairAccepts p D1) (hp2 : PairAccepts p D2)
(hsub : D2 ⊆ D) (hsup : D ⊆ D1 ∪ D2) : PairAccepts p D := by sorry
end BuchiRabinIndex.LowerBound
Source
Cong Tian, Runzhe Ma, Wensheng Wang, Zhenhua Duan, Büchi Determinization with Optimal States and Square Root Index Improvement, STOC 2027 submission #1731 (October 2026), Lemma 33, p. 26; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1731.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.