Corollary 35 — adjacency through the decomposition
ProvedBuchiRabinIndex.LowerBound.corollary_35automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
Let and let be node names. For either decomposition part , if , then
For and ,
These are equivalences in both directions, identifying adjacency within and across the two parts.
Differences from the source:
- encoding: nodes are finite words of positive integers → List Nat with positivity in node and tree predicates; reason: children retain the source’s indices starting at 1
- encoding: the unique n-full ordered tree of Definition 12 → the explicitly enumerated positive words of weight at most n−1; reason: this is the same finite tree; no size is fixed
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Nodes set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound
/-- STOC 2027 submission #1731, corollary 35; statement only. -/
theorem corollary_35 (n : ℕ) (hn : 2 ≤ n) (x y : Node) (hne : x ≠ y) :
(x ∈ part1 n → y ∈ part1 n → (Adj n x y ↔ Adj (n - 1) (phi1 x) (phi1 y))) ∧
(x ∈ part2 n → y ∈ part2 n → (Adj n x y ↔ Adj (n - 1) (phi2 x) (phi2 y))) ∧
(x ∈ part1 n → y ∈ part2 n → (Adj n x y ↔ weight x + weight y ≤ n)) := 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), Corollary 35, 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.