Locally catenative sequence¶

A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words.

Version: v1 · 2026-09-28 · History
Domain-specific #: 10462
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Combinatorics on Words → Mathematics

Core Idea¶

A locally catenative sequence is an infinite sequence of finite words in which every sufficiently late word is obtained by concatenating a fixed finite pattern of earlier words. Formally, there are positive offsets \(i_1,\ldots,i_k\) such that \(w(n)=w(n-i_1)w(n-i_2)\cdots w(n-i_k)\) for all \(n\) beyond the largest offset. “Local” means that the construction of the next word consults only specified relative positions in the sequence; “catenative” means that the construction joins whole earlier words without interleaving their symbols. The offsets and order remain stable across the recurrence.

Fibonacci words provide the canonical example: \(w(n)=w(n-1)w(n-2)\). Their lengths obey the corresponding numerical Fibonacci recurrence, but the word recurrence carries more information because concatenation is generally noncommutative. Changing the order of the two factors can change every later word even when lengths are unchanged. This makes locally catenative sequences useful in combinatorics on words, where one studies factor complexity, morphic structure, repetitions, and infinite limits generated by finite recursion.

Definitions differ over whether transformed copies count. Under the strict definition, only previous words themselves may be concatenated. Under an extended definition, a fixed encoding or morphism may be applied first; the Thue–Morse word sequence can then be described through a word and its bitwise complement, although it is not locally catenative in the strict sense. The abstraction is not any recursively generated sequence, a recurrence on word lengths, or arbitrary reuse of earlier substrings. It requires a uniform finite concatenation rule over earlier sequence elements, with the permitted transformations stated explicitly.

Structural Signature¶

Sig role-phrases:

the word-valued sequence — an infinite ordered family of finite words over a declared alphabet
the finite offset set — fixed positive indices identifying which earlier sequence elements may be consulted
the recurrence threshold — a point beyond which the same rule applies to every new word
the whole-word factors — earlier words reused intact rather than arbitrary substrings or interleaved symbols
the fixed concatenation order — noncommutative arrangement of factors preserved at every step
the generated next word — exact concatenation of the designated previous elements
the induced length recurrence — numerical relation among word lengths that records size but not symbol order
the optional-transform convention — explicit declaration when a fixed morphism or encoding may precede concatenation
the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths

What It Is Not¶

Not any recursively generated word sequence. The recurrence must concatenate a fixed finite pattern of earlier sequence elements after a bounded starting segment.
Not a recurrence on lengths alone. Equal numerical lengths can conceal different word orders because concatenation is generally noncommutative.
Not arbitrary reuse of earlier substrings. Strict catenation joins whole prior words at specified offsets rather than selecting fragments.
Not a changing rule at every index. Offsets and factor order remain uniform once the recurrence begins.
Not automatically inclusive of transformed copies. Complements, encodings, or morphisms count only under an explicitly extended definition.
Not interleaving. Symbols of the source words retain their within-word order and appear in concatenated blocks.
Not merely an infinite word. The object is a sequence of finite words whose recurrence may generate or converge toward an infinite limiting structure.

Scope of Application¶

Locally catenative sequence applies to infinite sequences of finite words generated after an initial segment by one fixed ordered concatenation pattern over earlier whole sequence elements.

Combinatorics on words. Repeated concatenation supports proofs about factors, prefixes, recurrence, and subword complexity.
Fibonacci-word constructions. Fixed offsets and factor order produce canonical symbolic analogues of numerical recurrences.
Morphic limits. Compatible prefix growth can connect the recurrence to an infinite fixed or morphic word.
Length recurrences. Word lengths inherit numerical relations, but the symbolic sequence retains additional noncommutative information.
Algorithmic generation. Initial words, offsets, threshold index, and factor order define efficient production and recognition tasks.
Extended conventions. Fixed encodings or complements may be admitted only when the chosen definition expressly permits them.
Comparative sequence theory. Strict locally catenative sequences can be separated from substitution, automatic, and arbitrary recursive sequences.
Applicability boundary. Reusing substrings, matching only length recurrences, or exchanging concatenation order does not preserve the strict concept, and existence of a limit requires a prefix or convergence argument.

Clarity¶

Locally catenative sequence names a word-valued recurrence in which each sufficiently late word is an ordered concatenation of words at fixed earlier offsets. ‘Local’ refers to those relative positions, while ‘catenative’ preserves whole-word order rather than combining symbols arithmetically. This prevents the induced recurrence for word lengths from being mistaken for the full construction, since concatenation is generally noncommutative. The sharper question is which offsets and order generate the sequence, from what initial words, and which structural properties follow beyond mere length growth.

Manages Complexity¶

A locally catenative sequence reduces an infinite family of words to finitely many initial words, fixed offsets, and one ordered concatenation rule. The analyst tracks the recurrence rather than constructing or storing every late word independently. Lengths obey an induced linear recurrence, while prefixes, suffixes, factor occurrences, and growth retain the noncommutative information of word order. Changing offsets or concatenation order creates explicit branches. This finite description makes proofs by induction and morphic structure possible and separates properties visible from length alone from those that require the actual symbolic arrangement.

Abstract Reasoning¶

Recurrence move. From the fixed offsets and ordered concatenation rule, generate all sufficiently late words and prove properties by induction. Length move. Map concatenation to addition to derive a numerical recurrence for word lengths, while withholding conclusions that depend on symbol order. Factor move. Use prefix, suffix, and recurrence structure to infer repeated factors or morphic behavior. Boundary move. Changing the order of earlier words can leave lengths unchanged while changing the sequence, so length evidence cannot identify the catenative word recurrence. Initialization move. Verify that initial words and offset threshold make every referenced predecessor defined.

Knowledge Transfer¶

Within the home domain. Locally catenative sequences transfer across combinatorics on words, morphic sequences, and symbolic dynamics when each term is formed by concatenating a fixed local pattern of earlier terms. Seed words, recurrence indices, concatenation order, lengths, and factor structure retain formal meanings. Beyond the home domain (C — formal sequence class). The definition applies literally to any word sequence satisfying the recurrence, independent of alphabet interpretation. Its boundary is strict: numerical recurrences using addition are not catenative unless symbols or words are concatenated, and visual self-similarity alone does not establish the required local generative rule.

Examples¶

Canonical¶

The Fibonacci-word sequence is locally catenative. Begin with finite words F0=0 and F1=01, then define Fn=F(n-1)F(n-2) for n≥2. Thus F2=010, F3=01001, and F4=01001010. Each new term is obtained by concatenating whole earlier words at the fixed offsets one and two and in a fixed order. The lengths therefore satisfy the ordinary Fibonacci recurrence even though the objects are words rather than numbers. Reversing the concatenation order produces a different sequence, and concatenating individual letters chosen from arbitrary earlier positions would break the stated local word-level recurrence.

Mapped back: The F_n form the word-valued sequence with finite offset set {1,2} after the recurrence threshold. Earlier F terms are the whole-word factors, arranged in the fixed concatenation order to produce the generated next word and induced length recurrence.

Applied / In Practice¶

A symbolic-dynamics program can generate a long Fibonacci word without storing every previous term. It retains the two needed words, concatenates them in the specified order, advances the window, and verifies the resulting length recurrence. Researchers then examine factors, repetition, balance, or substitution structure in the generated sequence. If memory requires a compressed representation, a rope or grammar can preserve concatenation structure without materializing the entire string. The implementation remains faithful only if operations combine complete predecessor words; chunking by convenience must not change the recurrence. A later binary-to-symbol transform may reinterpret 0 and 1 while leaving the catenative structure intact if the convention is recorded.

Mapped back: The rolling two-word state realizes the finite offset set and whole-word factors. Ordered concatenation enforces the fixed concatenation order and generated next word; compressed storage preserves the locality boundary, and recoding symbols uses the optional-transform convention without changing the induced length recurrence.

Structural Tensions¶

T1 — Identity versus admissible variation. Locally catenative sequence must remain recognizable across legitimate variants. Admissible variation is bounded by this condition: Repeated concatenation supports proofs about factors, prefixes, recurrence, and subword complexity. The stable element is expressed by this invariant: A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. Treating every surface change as a new abstraction fragments the identity, while allowing a change to the constitutive relation produces a false positive.

Diagnostic: After the proposed variation, can an analyst still establish this invariant: A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words?

T2 — Recognition versus proxy. The domain needs observable or inferential evidence for Locally catenative sequence, but the evidence is not automatically the identity. The working recognition rule is: the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths. A familiar indicator can occur without the defining relation, and the relation can persist when a customary detector is unavailable.

Diagnostic: Does the evidence establish the defining claim—A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words—or only a correlated sign?

T3 — Definition versus operational judgment. A compact definition aids reuse, whereas actual classification in combinatorics on words can require expert decisions about boundary conditions, measurements, conventions, or exceptions. Fibonacci words provide the canonical example: \(w(n)=w(n-1)w(n-2)\). The definition must constrain those judgments without pretending that every admissible case can be recognized from a label alone.

Diagnostic: Which observation would make a competent practitioner reject the classification under the stated definition?

T4 — Scope versus overextension. Locally catenative sequence has a genuine habitat in which repeated concatenation supports proofs about factors, prefixes, recurrence, and subword complexity. Yet Reusing substrings, matching only length recurrences, or exchanging concatenation order does not preserve the strict concept, and existence of a limit requires a prefix or convergence argument. A useful application map therefore has to be broad enough to cover recurring practice and narrow enough to exclude merely topical or metaphorical occurrences.

Diagnostic: Can the claimed application fill the same carrier and relation roles, or has only the name traveled?

T5 — Transfer versus domain accent. Knowledge about Locally catenative sequence can travel within its home domain, and some structural lessons may travel farther. Locally catenative sequences transfer across combinatorics on words, morphic sequences, and symbolic dynamics when each term is formed by concatenating a fixed local pattern of earlier terms. What transfers must be separated from the specialist vocabulary, warrant, and closure conditions that remain anchored in combinatorics on words.

Diagnostic: Is the receiving case a literal instance of Locally catenative sequence, a co-instance of Recursion, or only an analogy?

T6 — Autonomy versus reduction. Locally catenative sequence is a strict specialization of Recursion, but the edge does not erase the domain differentia. The broader node supplies only the necessary structural relation; combinatorics on words supplies the carrier, warrant, boundary, and exception conditions expressed by this identity: A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. The entry is over-split if those conditions add no discriminating work and under-specified if the parent alone is used for cases that require them.

Diagnostic: Can a domain expert use the added conditions to distinguish Locally catenative sequence from another case that equally instantiates Recursion?

Structural–Framed Character¶

Locally catenative sequence is mixed: structurally specifiable but materially dependent on its disciplinary frame. Its structural side consists of the carrier the word-valued sequence — an infinite ordered family of finite words over a declared alphabet and the constitutive relation A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. Its framed side comes from combinatorics on words, which fixes what the terms denote, what counts as evidence, and when a qualification or exception defeats the classification.

Across the principal tests, the entry is not merely a free-floating pattern. Evaluative weight: the identity can be stated descriptively even when its use has practical or normative consequences. Practice dependence: the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths. Institutional stabilization: disciplinary conventions may stabilize the name and test without necessarily creating every underlying event or relation. Vocabulary portability: the invariant is A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. Import versus recognition: an outside case qualifies literally only if the same typed roles and collapse condition are available; otherwise the comparison is analogical.

The reusable remainder is Recursion under a reviewed subsumption relation. That node preserves the necessary cross-domain organization after the combinatorics on words-specific carrier, evidence, and exceptions are removed. Locally catenative sequence remains autonomous because its recognition and collapse conditions distinguish cases that the parent alone leaves together.

Structural Core vs. Domain Accent¶

What is skeletal. The portable skeleton is a typed carrier organized by a constitutive relation, an invariant, a recognition test, and a collapse condition. Here the carrier is the word-valued sequence — an infinite ordered family of finite words over a declared alphabet. The decisive relation is A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words, which also states the controlling invariant at this level. Stripped of specialist nouns, this organization is represented by Recursion.

What is domain-bound. combinatorics on words supplies the actual objects or agents, admissible transformations, units or conventions, standards of warrant, and named exceptions. In this case, recognition requires evidence for the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths. Admissible variation is bounded by the condition that repeated concatenation supports proofs about factors, prefixes, recurrence, and subword complexity, and the classification collapses when the recurrence must concatenate a fixed finite pattern of earlier sequence elements after a bounded starting segment. These are constitutive differentia, not illustrative decoration.

Why it remains a domain-specific node. The reviewed DAG relation is subsumption to Recursion. Outside combinatorics on words, the parent captures only the reusable structural remainder. The specialist name remains literal only where the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths can be established under the domain's standards of warrant.

This entry is a kind of Recursion.

Immediate parent — Recursion (subsumption). Locally catenative sequence is a domain-specific kind of Recursion: A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. The parent supplies the necessary broader identity—Breaks processes into self-similar steps.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: A locally catenative sequence is an infinite sequence of finite words in which every sufficiently late word is obtained by concatenating a fixed finite pattern of earlier words.
Nearest catalog surface declined — Constant-recursive sequence. Its rematch score was 0.144451. Retrieval proximity did not establish synonymy or parentage; the carrier, invariant, and collapse condition remain different.
Related reasoning operations. Evidence, comparison, boundary testing, and representation can support a case without becoming additional DAG parents.

Relationships to Other Abstractions¶

Current abstraction Locally catenative sequence Domain-specific

Parents (1) — more general patterns this builds on

Locally catenative sequence is a kind of Recursion Prime

Locally catenative sequence is a domain-specific kind of Recursion: A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words.

Hierarchy path (1) — routes to 1 parentless root

Locally catenative sequence → Recursion

Neighborhood in Abstraction Space¶

Locally catenative sequence sits in a crowded region of the domain-specific corpus (39^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Formal Sequences & Language Structure (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Recursion. This is the reviewed immediate parent or structural prerequisite, not a synonym. Tell: retain Locally catenative sequence only when the domain-specific relation A locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words. and its source-domain warrant are established; otherwise route the case to Recursion.
Local Sequence Legality. This is the closest catalog retrieval surface, not an accepted synonym or parent. Tell: Ask which entry's carrier, invariant, and collapse test the case actually satisfies; shared vocabulary or a score of 0.710929 is insufficient.
Not any recursively generated word sequence. The recurrence must concatenate a fixed finite pattern of earlier sequence elements after a bounded starting segment. Tell: Require the positive recognition condition that the locality boundary — exclusion of arbitrary recursion, changing offsets, and recurrences operating only on lengths.
Not a recurrence on lengths alone. Equal numerical lengths can conceal different word orders because concatenation is generally noncommutative. Tell: Replace the familiar surface feature and test whether a locally catenative sequence is a word sequence governed by a fixed recurrence in which each sufficiently late word is the concatenation, in fixed order, of specified earlier words.
A detector, representation, or consequence. A method may reveal Locally catenative sequence, a notation may describe it, and an outcome may follow from it without any of those being identical to the abstraction. Tell: Would the defining relation remain if the present detector, notation, or downstream effect changed?
A metaphorical transfer. A case outside the home domain may resemble the structure while lacking its native role types and standards of warrant. Tell: If only the general organization survives, route the comparison to Recursion rather than treating it as another Locally catenative sequence instance.

References¶

Frozen Wikipedia revision: https://en.wikipedia.org/wiki/Locally_catenative_sequence (revision 1099536040).
A. Lepistö, ‘A generalization of automatic sequences’, Theoretical Computer Science 68(2): 195–214: https://doi.org/10.1016/0304-3975(89)90103-X
Grzegorz Rozenberg and Arto Salomaa (eds.), The Mathematical Theory of L Systems, Academic Press: https://doi.org/10.1016/C2013-0-11244-8
Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge University Press: https://doi.org/10.1017/CBO9780511546563 The frozen Wikipedia revision is discovery provenance. The added sources are reference-grade authorities for the definition, formal relation, or professional practice summarized above; downstream historical or application claims remain bounded by the wording and scope of the cited source.

The frozen Wikipedia revision is discovery provenance. The cited source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; URL transport failure alone was not treated as substantive contradiction.