AFTD Auto-Formalizing Theoretical Domains

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

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