AFTD Auto-Formalizing Theoretical Domains

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

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}
See it in the graphDiscuss this resultChallenge it