AFTD Auto-Formalizing Theoretical Domains

rev_comp

def

The reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).

Statement

def rev_comp {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : List Γ
Defined in
arXiv:2611.16573, Section 2
Verified
14 Nov 2026
Axioms
none listed
Used by 8
  • rc_substring_freeFor 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…
  • tgreedy_rc_output_sanityWith cm = id, TGREEDY-RC on {12} can output 12.
  • greedy_rc_step_sanityWith cm = id, one GREEDY-RC step on {12, 23} gives {123}.
  • scs_rc_optThe optimum of the Shortest Common Superstring with Reverse Complements problem: the least length of a string that contains s or rc(s) as…
  • greedy_rc_stepFor cm : Γ → Γ and S, S' : Finset (List Γ), greedy_rc_step cm S S' holds when S has more than one element and, with V = S ∪ rev_comp cm ''…
  • mgreedy_rc_stepFor cm : Γ → Γ and states st = (S, T), st' : Finset (List Γ) × Finset (List Γ), mgreedy_rc_step cm st st' holds when, with V = S ∪…
  • rev_comp_sanityThe reverse complement of 011 under n ↦ 3 − n is 223.
  • scs_rc_opt_singleton_leThe SCS-RC optimum of a single string is at most its length.

Read back from the Lean

For any type Γ, given a function cm : Γ → Γ and a list s : List Γ, rev_comp cm s is defined as the reverse of the list obtained by applying cm elementwise to s (that is, (s.map cm).reverse).

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

/-- The reverse complement rc(s) of a string: reverse it and complement each letter. -/
def rev_comp {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : List Γ := (s.map cm).reverse
See it in the graphDiscuss this resultChallenge it