String Ontology

FLOW ALGEBRA
TITLE: String Ontology
DOMAIN: Discrete Mathematics / Formal Languages
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/string-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Represent finite strings as ordered sequences of symbols from an alphabet, together with their operations, structural relationships, and formally checkable laws.

2. TYPED ENTITIES
Alphabet := finite nonempty set of distinct symbols Sigma (some conventions permit an empty alphabet).
Symbol := atomic member a in Sigma.
String(Sigma) := finite sequence of symbols from Sigma.
EmptyString := epsilon, the unique sequence of length zero.
Length := nonnegative integer |w|.
Language(Sigma) := subset of Sigma*.
Position(w) := integer index i with 0 <= i < |w|.
Substring := contiguous segment of a string.
Prefix := initial segment; Suffix := terminal segment.

3. CORE CONSTRUCTORS AND OPERATIONS
singleton(a: Symbol) -> String: sequence containing a.
concat(u: String, v: String) -> String: uv.
length(w: String) -> Nat: number of symbols.
reverse(w: String) -> String: symbols in reverse order.
slice(w: String, i: Nat, j: Nat) -> String: positions i through j-1, where 0 <= i <= j <= |w|.
power(w: String, n: Nat) -> String: n-fold concatenation, w^0 = epsilon.
Sigma* := union over n >= 0 of Sigma^n.
Sigma+ := Sigma* excluding epsilon.

4. FORMAL LAWS
Associativity: (uv)w = u(vw).
Identity: epsilon w = w epsilon = w.
Length: |uv| = |u| + |v|; |epsilon| = 0.
Reverse: reverse(uv) = reverse(v) reverse(u).
Involution: reverse(reverse(w)) = w.
Power: w^(m+n) = w^m w^n for m,n >= 0.
Free monoid: (Sigma*, concat, epsilon) is a free monoid on Sigma.
Noncommutativity: uv need not equal vu.
Cancellation: ux = uy implies x = y; xu = yu implies x = y.
Prefix: u is a prefix of w iff exists v: w = uv.
Suffix: v is a suffix of w iff exists u: w = uv.
Substring: x is a substring of w iff exists u,v: w = uxv.

5. SEMANTIC RELATIONSHIPS
Symbol --MEMBER_OF--> Alphabet.
String --SEQUENCE_OVER--> Alphabet.
String --CONTAINS_SYMBOL--> Symbol (when present).
String --HAS_LENGTH--> NaturalNumber.
String --PREFIX_OF--> String.
String --SUFFIX_OF--> String.
String --SUBSTRING_OF--> String.
String --MEMBER_OF--> Language.
Concatenation --COMPOSES--> String.
EmptyString --IDENTITY_FOR--> Concatenation.
String --REPRESENTED_BY--> Encoding (representation-dependent).

6. INFERENCE RULES
IF u in Sigma* AND v in Sigma* THEN uv in Sigma*.
IF w in Sigma* THEN |w| >= 0.
IF |w| = 0 THEN w = epsilon.
IF w = uv THEN |w| = |u| + |v|.
IF u is a prefix of v AND v is a prefix of w THEN u is a prefix of w.
IF x is a substring of y AND y is a substring of z THEN x is a substring of z.
IF a in Sigma THEN singleton(a) in Sigma*.

7. VALIDATION AND COUNTEREXAMPLES
Validate all string symbols against declared alphabet.
Validate integer indices and slice boundaries.
Preserve symbol identity independently of byte or character encoding.
Do not assume concatenation commutes: over {a,b}, 'ab' != 'ba'.
Do not confuse epsilon (empty string) with empty language (empty set).
Do not equate symbol count with byte length or Unicode code-point count without a specified representation.

8. SEMANTIC_EQUIVALENCE
'word' == 'finite string' when used in formal-language theory.
'epsilon' == 'empty string' == 'length-zero sequence'.
'concatenation' == 'string product' in the free-monoid context.
Disambiguation: an empty string is an element of Sigma*; an empty language has no elements.

9. CONFIDENCE
Definitions and algebraic laws: HIGH (standard formal-language theory).
Page-specific correspondence: UNVERIFIED.
Inference outputs: require validated premises and alphabet context.

10. FLOW_HASH
MODEL: SHA-256 over canonical UTF-8 serialisation of ontology fields and rules.
STATUS: COMPUTE_AT_INGEST (no fabricated digest).
CANONICALISATION: stable key ordering, Unicode NFC, LF line endings.

11. UPDATE_MODEL
On update: check mathematical definitions, version change, recompute FLOW_HASH, retain provenance and previous revision, revalidate all inference rules and examples.

12. AI_CONSUMPTION
INPUT: alphabet, strings, requested operation, optional language constraints.
PROCESS: type-check -> normalise -> apply operation/rule -> validate -> record provenance.
OUTPUT: result, type, supporting law, confidence, warnings and hash if computed.
FAILURE: reject invalid symbols/indices; distinguish unknown from false.

END FLOW ALGEBRA