tgreedy_rc_output
For cm : Γ → Γ, S : Finset (List Γ) and t : List Γ, tgreedy_rc_output cm S t holds when there is T : Finset (List Γ) such that the state (S, ∅) reaches (∅, T) by zero or more mgreedy_rc_step cm steps (Relation.ReflTransGen), and T reaches the singleton {t} by zero or more greedy_rc_step cm steps: t is an output of an execution of TGREEDY-RC.
Statement
def tgreedy_rc_output {Γ : Type*} [DecidableEq Γ] (cm : Γ → Γ) (S : Finset (List Γ)) (t : List Γ) : Prop
- Defined in
- arXiv:2611.16573, Algorithm 3
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Built on 2
- 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 ∪…
- 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 ''…
- Used by 2
- tgreedy_rc_output_sanityWith cm = id, TGREEDY-RC on {12} can output 12.
- 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 Γ with decidable equality, a function cm : Γ → Γ, a finite set of lists S : Finset (List Γ), and a list t : List Γ, the proposition tgreedy_rc_output cm S t asserts that:
There exists a finite set of lists T : Finset (List Γ) such that:
1. The pair (∅, T) is reachable from (S, ∅) via zero or more transitions of mgreedy_rc_step cm.
2. The singleton set {t} is reachable from T via zero or more transitions of greedy_rc_step cm.
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
/-- t is the output of some execution of TGREEDY-RC (Algorithm 3) on S: MGREEDY-RC run from (S, ∅) until S is empty gives T (without the final concatenation), and GREEDY-RC run on T leaves the single string t. -/ def tgreedy_rc_output {Γ : Type*} [DecidableEq Γ] (cm : Γ → Γ) (S : Finset (List Γ)) (t : List Γ) : Prop := ∃ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) ∧ Relation.ReflTransGen (greedy_rc_step cm) T {t}