Context-Sensitive Language Ontology

FLOW ALGEBRA
Context-Sensitive Language Ontology
Version: 1.0 | Date: 2026-10-11
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/context-sensitive-language-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)

1. DOMAIN AND PURPOSE
flow "ContextSensitiveLanguageOntology" v1.0
  domain: discrete_mathematics.formal_languages
  subject: context_sensitive_language
  objective: represent, classify, derive, and validate context-sensitive languages using formal grammars and bounded computation.

2. TYPED ENTITIES
  Alphabet = finite_set<Symbol>
  String = sequence<Symbol>
  Language = set<String>
  Nonterminal = Symbol
  Terminal = Symbol
  SententialForm = sequence<Terminal | Nonterminal>
  Production = pair<SententialForm, SententialForm>
  Grammar = record<N:finite_set<Nonterminal>, T:Alphabet, P:finite_set<Production>, S:Nonterminal>
  LinearBoundedAutomaton = record<states, input_alphabet, tape_alphabet, transition, initial_state, accepting_states, bounded_tape>
  Derivation = sequence<SententialForm>
  ParseResult = record<accepted:bool, witness:Derivation?, confidence:real>

3. CORE DEFINITIONS
  context_sensitive(L:Language) := exists G:Grammar . generates(G,L) and type1_grammar(G)
  type1_grammar(G) := every production p in G.P is context_sensitive_valid(p,G)
  context_sensitive_valid((lhs,rhs),G) :=
      (length(rhs) >= length(lhs) and lhs contains a nonterminal)
      or (lhs = [G.S] and rhs = [] and G.S never appears on any production RHS)
  note: Noncontracting grammar productions characterise context-sensitive languages, with the stated restricted empty-string exception.
  generates(G,L) := L = {w in G.T* | derives_star(G,[G.S],w)}
  lba_recognisable(L) := exists M:LinearBoundedAutomaton . L = language_accepted(M)
  theorem: context_sensitive(L) iff lba_recognisable(L)

4. RELATIONSHIPS
  ContextSensitiveLanguage IS_A FormalLanguage
  ContextSensitiveGrammar IS_A FormalGrammar
  ContextSensitiveGrammar GENERATES ContextSensitiveLanguage
  LinearBoundedAutomaton RECOGNISES ContextSensitiveLanguage
  ContextFreeLanguage SUBCLASS_OF ContextSensitiveLanguage
  ContextSensitiveLanguage SUBCLASS_OF RecursiveLanguage
  ContextSensitiveLanguage SUBCLASS_OF RecursivelyEnumerableLanguage
  ProductionRule TRANSFORMS SententialForm
  Derivation ESTABLISHES MembershipWitness

5. INFERENCE RULES
  R1: type1_grammar(G) AND generates(G,L) => context_sensitive(L)
  R2: lba_recognisable(L) => context_sensitive(L)
  R3: context_free(L) => context_sensitive(L)
  R4: context_sensitive(L) => decidable_membership(L)
  R5: context_sensitive(L1) AND context_sensitive(L2) => context_sensitive(union(L1,L2))
  R6: context_sensitive(L1) AND context_sensitive(L2) => context_sensitive(intersection(L1,L2))
  R7: context_sensitive(L) => context_sensitive(complement(L))
  R8: context_sensitive(L1) AND context_sensitive(L2) => context_sensitive(concatenation(L1,L2))
  R9: context_sensitive(L) => context_sensitive(kleene_star(L))
  R10: context_sensitive(L) => context_sensitive(reversal(L))
  caution: Arbitrary homomorphic images need not preserve context sensitivity; non-erasing homomorphisms do.

6. CANONICAL EXAMPLE
  L_abc = {a^n b^n c^n | n >= 1}
  classification: context_sensitive = true; context_free = false
  example_grammar:
    S -> aSBC | aBC
    CB -> BC
    aB -> ab
    bB -> bb
    bC -> bc
    cC -> cc
  example_derivation:
    S => aSBC => aaBCBC => aaBBCC => aabBCC => aabbCC => aabbcC => aabbcc
  validation: all listed productions are noncontracting; generated strings have equal positive counts of a, b, c in that order.

7. COMPUTATION FLOW
  input: candidate grammar G, candidate string w
  stage_1: validate finite symbol sets and start symbol
  stage_2: check production well-formedness and noncontracting constraints
  stage_3: identify restricted epsilon exception, if present
  stage_4: construct or simulate a suitable bounded-space recogniser
  stage_5: decide membership of w using bounded configurations
  stage_6: return acceptance, derivation witness when available, and validation diagnostics
  output: ParseResult
  termination: finite bounded-tape configuration space for each fixed input

8. FORMAL CONSTRAINTS
  C1: G.N intersection G.T = empty_set
  C2: G.S belongs_to G.N
  C3: every production LHS contains at least one nonterminal
  C4: no production decreases sentential-form length except permitted S -> epsilon
  C5: if S -> epsilon is used, S does not occur on any production RHS
  C6: LBA working tape is bounded by O(input_length) cells, under the standard model
  C7: language membership is defined by terminal-only derivations or equivalent LBA acceptance

9. SEMANTIC EQUIVALENCE AND CONFIDENCE
  SEMANTIC_EQUIVALENCE:
    type1_language <=> context_sensitive_language
    context_sensitive_language <=> linear_bounded_automaton_recognisable_language
  CONFIDENCE:
    formal_definitions: 1.0
    equivalence_theorem: 1.0
    example_classification: 1.0
    unverified_external_grammar: requires_proof

10. FLOW HASH AND UPDATE MODEL
  FLOW_HASH:
    method: SHA-256
    input: canonical_utf8(serialised_ontology_without_hash_field)
    value: compute_at_ingestion
  UPDATE_MODEL:
    version_policy: semantic_versioning
    preserve: canonical definitions, proofs, provenance
    on_change: revalidate rules, examples, and dependency links
    audit: record timestamp, editor, change summary, hash

11. AI CONSUMPTION
  AI_CONSUMPTION:
    retrieval_keys: [context-sensitive language, type-1 grammar, noncontracting grammar, linear bounded automaton, Chomsky hierarchy]
    reasoning_tasks: [grammar classification, membership checking, closure reasoning, automata equivalence, derivation verification]
    output_contract: distinguish proven theorem from candidate inference; attach witnesses or proof obligations
    safety: never infer grammar equivalence solely from similar terminology
    provenance: source URL and version recorded above

12. VALIDATION TESTS
  T1: classify {a^n b^n c^n | n >= 1} as context-sensitive and not context-free
  T2: verify each example production is noncontracting
  T3: verify aabbcc is derivable from the example grammar
  T4: reject a grammar with unrestricted length-decreasing production as Type-1 under the noncontracting definition
  T5: accept a context-free language as a context-sensitive language
  T6: check complement closure of context-sensitive languages
  T7: flag arbitrary erasing homomorphism closure as unsupported

END FLOW ALGEBRA