How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Finite words, contiguous factors, avoidance and proper-prefix states
Definition
Let be a finite set, called an alphabet. A word of length over is a function from the natural number (The natural numbers (von Neumann)) to , written . The unique word of length zero is the empty word . Concatenation of words and is denoted by .
A word is a contiguous factor of if for some . It is a prefix if , a suffix if , and a proper prefix if it is a prefix other than the whole word.
For a set of words, a word avoids if none of its contiguous factors belongs to . Its set of proper-prefix states is
If is nonempty and every word in is nonempty, then . If is finite, then is finite.
Depends on
Used by
- Balanced bracket words, defined by the recursive grammar Definition
- Binary trees, defined recursively, and their size Definition
- Computation alphabets, words, the empty word, and Σ^* Definition
- Cyclic shifts of an integer word and its periodic partial-sum function Definition
- Lattice paths, step sets and step words Definition
- The longest-suffix prefix automaton for a finite set of forbidden factors Definition
- The computation-word convention agrees with the published finite-word definition Lemma
- The published prefix automata extend canonically to DFAs for factor-avoidance languages Proposition
Dependency tree · two levels
6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Example 4.7.7 and Proposition 4.7.8 (standard reference, not scraped)