Symbol Ontology

FLOW ALGEBRA
SYMBOL ONTOLOGY — FORMAL LANGUAGES
Version: 1.0
Date: 2026-10-11
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/symbol-ontology.html
Domain: Discrete Mathematics / Formal Languages
Authors: Mark Higgins — Sky (Recursive AI)
Site: https://kirethresearch.org
Source status: Domain-grounded formalisation; live source page not independently verified.

1. PURPOSE
Represent atomic symbols and their typed relationships to alphabets, strings, formal languages, grammars and automata. Distinguish abstract symbols from their textual encodings and from semantic interpretations.

2. TYPED ENTITIES
Symbol := atomic, distinguishable token within a formal alphabet.
Alphabet := finite nonempty set of symbols (conventional formal-language setting).
String := finite ordered sequence of symbols from one alphabet.
EmptyString := epsilon, sequence of length zero; not itself an alphabet symbol unless separately defined as a literal token.
Language := subset of Sigma*.
Terminal := symbol that appears in generated words of a grammar.
Nonterminal := syntactic variable used by grammar productions.
Grammar := (N, Sigma, P, S), with N and Sigma disjoint, S in N.
TransitionLabel := input symbol consumed by an automaton transition; epsilon-transition consumes no symbol.
Encoding := representation mapping abstract symbols to concrete bit or character sequences.
Interpretation := optional assignment of meaning to symbols, separate from syntax.

3. CORE SIGNATURES
member : Symbol × Alphabet -> Bool
singleton : Symbol -> Set[Symbol]
concat : String × String -> String
length : String -> Nat
encode : Symbol -> EncodedSequence
interpret : Symbol × Context -> Meaning? 

4. FORMAL AXIOMS AND INVARIANTS
A1. Sigma is a finite set of distinct atomic symbols.
A2. a in Sigma implies [a] in Sigma*, and length([a]) = 1.
A3. epsilon in Sigma*, length(epsilon) = 0.
A4. For x,y in Sigma*, length(xy) = length(x) + length(y).
A5. For all x in Sigma*, epsilon x = x epsilon = x.
A6. Sigma* = union_{n >= 0} Sigma^n, with Sigma^0 = {epsilon}.
A7. Sigma+ = union_{n >= 1} Sigma^n = Sigma* \ {epsilon}, for nonempty Sigma.
A8. Distinct symbols need not have distinct glyphs in every display encoding; an encoding intended for unambiguous decoding must enforce suitable distinguishability.
A9. A grammar's terminal and nonterminal sets are disjoint.
A10. A symbol's syntactic identity does not entail a unique semantic interpretation.

5. OPERATIONS
CREATE_SYMBOL(id, alphabet, representation?) -> Symbol
REGISTER_SYMBOL(symbol, Sigma) -> Sigma' where Sigma' = Sigma union {symbol}
TOKENISE(input, lexical_rules) -> sequence[Symbol] or error
APPEND_SYMBOL(w, a) -> wa, requiring w in Sigma* and a in Sigma
RENAME_SYMBOL(a, b, mapping) -> structure-preserving relabelling where mapping is bijective on relevant alphabet
ENCODE_SYMBOL(a, scheme) -> sequence[code_unit]
VALIDATE_MEMBERSHIP(a, Sigma) -> Bool

6. RELATIONSHIPS
Symbol --MEMBER_OF--> Alphabet
Symbol --OCCURS_IN--> String
String --FORMED_OVER--> Alphabet
Language --SUBSET_OF--> KleeneClosure(Alphabet)
Terminal --IS_A--> Symbol
Nonterminal --IS_A--> Symbol
Grammar --USES_TERMINAL--> Terminal
AutomatonTransition --CONSUMES--> Symbol
Symbol --ENCODED_AS--> EncodedSequence
Symbol --INTERPRETED_AS--> Meaning (context-dependent)

7. INFERENCE RULES
R1. a in Sigma => [a] in Sigma*.
R2. w in Sigma* and a in Sigma => wa in Sigma*.
R3. w in Sigma* => epsilon w = w.
R4. a in Sigma and b in Sigma => ab in Sigma^2.
R5. w in L and L subseteq Sigma* => w in Sigma*.
R6. a in Sigma and f:Sigma -> Delta bijective => f(a) in Delta.
R7. If lexical decoding is ambiguous, do not infer a unique symbol sequence from the raw representation.

8. SEMANTIC_EQUIVALENCE
SYNTACTIC_EQUAL(a,b) iff they are the same formal symbol under the chosen identity scheme.
ALPHA_RENAMING_EQUIVALENT(structure1,structure2) iff a consistent bijective relabelling preserves all required structure.
ENCODING_EQUIVALENT(a,b,scheme) iff decoding under the scheme identifies the same abstract symbol.
MEANING_EQUIVALENT(a,b,context) is context-dependent and does not imply syntactic equality.
Do not equate epsilon (empty string) with an epsilon-labelled input symbol or a literal epsilon character.

9. VALIDATION
V1. Reject strings containing symbols outside their declared alphabet.
V2. Reject terminal/nonterminal collisions within one grammar.
V3. Verify identity and uniqueness of registered symbols.
V4. Verify concatenation preserves alphabet membership and length addition.
V5. Verify encodings can be decoded unambiguously when that property is required.
V6. Distinguish an empty alphabet, empty string, and empty language.
V7. Check symbol-renaming bijection before claiming structural equivalence.

10. WORKED EXAMPLE
Sigma = {0,1}
a = 0; b = 1
w = 0101
length(w) = 4
w in Sigma*
epsilon in Sigma*
0 epsilon 1 = 01
L = {w in Sigma* : length(w) is even}
0101 in L; 010 not in L
The symbol '0' is distinct from the integer zero unless an interpretation explicitly connects them.

11. CONFIDENCE
Formal definitions and identities: HIGH (standard formal-language theory).
Interpretation of symbols: CONTEXT_DEPENDENT.
Correspondence to live page: UNVERIFIED.
Confidence is metadata about claims, not a substitute for formal proof.

12. FLOW_HASH
Algorithm: SHA-256 over canonical UTF-8 content, excluding the FLOW_HASH value itself.
Value: COMPUTE_ON_PUBLICATION
Canonicalisation: UTF-8; LF newlines; stable section order; no trailing spaces.

13. UPDATE_MODEL
On source revision: preserve ontology identifier, increment version, record changed axioms and mappings, revalidate examples, recompute hash and retain provenance.
On alphabet change: revalidate membership, grammar terminals, automaton transitions and language definitions.

14. AI_CONSUMPTION
input: {symbol_id, alphabet_id, encoding?, context?}
process: [type_check, membership_check, identity_resolution, optional_encoding_decode, optional_semantic_interpretation]
output: {symbol, alphabet, syntactic_validity, relationships, confidence, provenance}
constraints: Never infer semantics solely from a glyph; never conflate epsilon with an input token; distinguish formal validity from source-page verification.

END FLOW ALGEBRA