AFTD Auto-Formalizing Theoretical Domains

is_complete_return_word

def

A word c is a complete return word to a factor q if q is both a prefix and a suffix of c, strictly shorter than c, and q does not occur at any intermediate position in c.

Statement

def is_complete_return_word {α : Type*} (c q : List α) : Prop
Defined in
arXiv:2611.13676 Section 2
Verified
12 Nov 2026
Axioms
none listed
Used by 2
  • is_rich_wordAn infinite word w is rich in palindromes if every complete return word to a palindromic factor of w is itself a palindrome.
  • is_complete_return_word_prefixIf c is a complete return word to q, then q is a prefix of c.

Read back from the Lean

Given a type α and two lists c, q : List α, is_complete_return_word c q asserts that all of the following hold: 1. q is a prefix of c (q <+: c), 2. q is a suffix of c (q <:+ c), 3. The length of q is strictly less than the length of c (q.length < c.length), and 4. For every natural number i, if 0 < i and i < c.length - q.length, then q is not a prefix of c.drop i (the list obtained by dropping the first i elements of c).

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 word c is a complete return word to factor q if q is a prefix and suffix of c, |c| > |q|, and q has no internal occurrences in c. -/
def is_complete_return_word {α : Type*} (c q : List α) : Prop := q <+: c ∧ q <:+ c ∧ q.length < c.length ∧
  ∀ i : ℕ, 0 < i → i < c.length - q.length → ¬ (q <+: c.drop i)
See it in the graphDiscuss this resultChallenge it