Theorem 2 (proof), p. 5 — the pipe automaton of a Set Cover instance is strongly acyclic with p² + 1 states, and its shortest synchronizing word has the minimum cover size as length
ProvedSyncPrefix.Huffman.theorem_2_reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reductionsset-coversynchronizing-automata
Let and let be a family of subsets of that covers . Let be the pipe automaton of the instance: one letter per set, the states for every point and a state , where for the letter maps to if and to otherwise, and every letter maps and to .
Then has states and letters, is strongly acyclic and synchronizing, and
the length of a shortest synchronizing word of equals the minimum size of a subfamily of covering .
This is the gap-preserving reduction from Set Cover behind Theorem 2 and, through Lemma 5, behind Corollary 8.
Differences from the source:
- reading: the Set Cover input is a family covering X (the proof: "such subfamily trivially exists if C covers X") → hypothesis
I.Coverable; reason: without a cover the minimum is undefined. - encoding: states q^{(j)}i and f →
Fin (p·p + 1), with q^{(j+1)}{i+1} ↦ j·p + i and f ↦ p²; reason: Lean convention, the same automaton.
Preamble
import Mathlib import Definitions.Def_SyncPrefix_Huffman_Constructions
Formal statement
namespace SyncPrefix.Huffman
open SetCoverThreshold.SetCover
/-- Theorem 2's reduction (p. 5): for a Set Cover instance in which every point lies in some set,
the pipe automaton has `p² + 1` states and one letter per set, is strongly acyclic and
synchronizing, and the length of its shortest synchronizing word is the minimum size of a set
cover. -/
theorem theorem_2_reduction (I : SCInstance) (hI : I.Coverable) :
(scAutomaton I).n = I.n ^ 2 + 1 ∧ (scAutomaton I).k = I.sets.length ∧
StronglyAcyclic (scAutomaton I).δ ∧ IsSynchronizing (scAutomaton I).δ ∧
syncLength (scAutomaton I).δ = minCover I := by sorry
end SyncPrefix.Huffman
Source
Ryzhikov & Szykuła, Finding Short Synchronizing Words for Prefix Codes, arXiv:1806.06299v1, p. 5, proof of Theorem 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.