scs_rc_opt
def
The optimum of the Shortest Common Superstring with Reverse Complements problem: the least length of a string that contains s or rc(s) as a substring for every s in S.
Statement
noncomputable def scs_rc_opt {Γ : Type*} (cm : Γ → Γ) (S : Finset (List Γ)) : ℕ
- Defined in
- arXiv:2611.16573, Definition 5
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Built on 1
- rev_compThe reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).
- Used by 2
- tgreedy_rc_two_point_five_approx_of_partsIf t is an output of TGREEDY-RC on S, every MGREEDY-RC output T from S is RC-substring-free, GREEDY-RC from any RC-substring-free T to {t}…
- scs_rc_opt_singleton_leThe SCS-RC optimum of a single string is at most its length.
Read back from the Lean
Given a type Γ, a mapping cm : Γ → Γ, and a finite set of lists S : Finset (List Γ), scs_rc_opt cm S is defined as the infimum (in ℕ) of the set of all natural numbers n for which there exists a list u : List Γ of length n such that for every list s ∈ S, either s is an infix (contiguous sublist) of u, or rev_comp cm s is an infix of u.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- |OPT(S)| for SCS-RC: the least length of a string containing s or rc(s) as a substring for every s ∈ S. -/ noncomputable def scs_rc_opt {Γ : Type*} (cm : Γ → Γ) (S : Finset (List Γ)) : ℕ := sInf {n | ∃ u : List Γ, u.length = n ∧ ∀ s ∈ S, s <:+: u ∨ rev_comp cm s <:+: u}