Substring¶
A string value occurring as a contiguous factor of a host, including the empty value by convention.
Core Idea¶
A substring is a contiguous factor of an ordered string. Formally, u occurs in host t when the host can be decomposed as p followed immediately by u followed immediately by s, with p and s possibly empty. This includes prefixes, suffixes, the entire host, and—under the usual stated convention—the empty string. It excludes a subsequence that keeps symbol order but skips positions.
A substring value and its occurrence are not the same object: ana is one string value that appears twice in banana. Pattern-searching algorithms use this relation when locating all contiguous occurrences of a query pattern in text. The formal statement assumes an alphabet and segmentation of symbols; code units, Unicode characters, and grapheme clusters can differ in real text systems, so a computational implementation must state which sequence it searches.
Scope of Application¶
Substring reasoning applies after a host string and its symbol units are fixed.
- Formal languages. Reason about factors, prefixes, suffixes, and word equations.
- Pattern matching. Locate all contiguous query-string occurrences in a host.
- Text processing. Extract spans while documenting character or grapheme indexing conventions.
- Comparative string problems. Distinguish longest common substring from longest common subsequence.
Clarity¶
Show t=p u s with p and s possibly empty. Ana is one substring value of banana at two offsets; a subsequence that skips a symbol is the closest exclusion. Prefixes and suffixes are included positional cases, and the empty string qualifies by the stated convention. In software, byte, code-point, and grapheme indexing may differ, so specify the symbol unit before reporting spans.
Manages Complexity¶
The factor relation compresses ordered adjacency and host-relative position into one term. It supports concise pattern-search and combinatorics claims, but can hide whether an analysis counts values, occurrences, or implementation-specific text units. Restating the host, factor, and span makes the relation computable without conflating those choices.
Abstract Reasoning¶
- Fix the host string and the alphabet or text-segmentation unit.
- Choose candidate u and search for an uninterrupted matching span.
- Exhibit p and s such that t=p u s, including empty boundary pieces if needed.
- Separate the factor's symbol value from every occurrence offset.
- Reject ordered-but-gapped subsequences and state the empty-string convention.
Knowledge Transfer¶
The contiguous-factor test transfers across formal strings, program tokens, and encoded text only after the symbol unit is specified. The ana-in-banana offsets do not carry to a differently normalized text representation, and a KMP occurrence claim does not include gapped subsequences. The general part-whole intuition is broader but lacks the exact t=p u s condition.
Neighborhood in Abstraction Space¶
Substring sits in a crowded region of the domain-specific corpus (37th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Language Structure & Grammar Formalisms (23 abstractions)
Nearest neighbors
- Literal movement grammar — 0.88
- Superpermutation — 0.88
- Sierpiński Graph — 0.88
- Regular Expression — 0.88
- Formal Syntax — 0.88
Computed from structural-signature embeddings · 2026-10-08