AFTD Auto-Formalizing Theoretical Domains

tgreedy_rc_output

def

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

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