rc_substring_free
def
For a complement map cm : Γ → Γ and a finite set S : Finset (List Γ), rc_substring_free cm S holds when for all x, y ∈ S with x ≠ y, x is not an infix (contiguous sublist) of y and x is not an infix of rev_comp cm y; nothing is required when x = y.
Statement
def rc_substring_free {Γ : Type*} (cm : Γ → Γ) (S : Finset (List Γ)) : Prop
- Defined in
- arXiv:2611.16573, Section 2
- 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 1
- 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}…
Read back from the Lean
Given a type Γ, a function cm : Γ → Γ, and a finite set of lists S : Finset (List Γ), rc_substring_free cm S asserts that for every list x ∈ S and every list y ∈ S, if x ≠ y, then x is not an infix (substring) of y and x is not an infix of rev_comp cm y.
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
/-- A set of strings is RC-substring-free: no string is a substring of another one or of its reverse complement. -/ def rc_substring_free {Γ : Type*} (cm : Γ → Γ) (S : Finset (List Γ)) : Prop := ∀ x ∈ S, ∀ y ∈ S, x ≠ y → ¬ x <:+: y ∧ ¬ x <:+: rev_comp cm y