Computer Science Domain Ontology

FLOW ALGEBRA
TITLE: Computer Science Domain Ontology
DOMAIN: Domain Ontologies / Computing Domains / Computer Science
SOURCE: https://kirethresearch.org/booksai-core/ontologies/domain-ontologies/computing-domains/computer-science-domain-ontology.html
VERSION: 1.0
AUTHORS: Mark Anthony Higgins — Sky (Recursive AI)
STATUS: Companion formalisation; source-page specification not independently verified.

flow "ComputerScienceDomainOntology" v1.0 {
  ontology:
    id: "computer-science-domain-ontology"
    parent: "computing-domains"
    purpose: "Represent formal, computational and empirical relationships across computer science with typed evidence and verifiable inference."

  types:
    ComputationalProblem: {id: string, specification: string, input_domain: string, output_domain: string}
    Algorithm: {id: string, version: string, precondition: string?, postcondition: string?, complexity_claim: string?}
    DataStructure: {id: string, abstract_type: string, invariants: string[]}
    Program: {id: string, language: string, version: string, artefact_hash: string?}
    ComputationalModel: {id: string, kind: enum[turing_machine, automaton, lambda_calculus, circuit, probabilistic, distributed, other], assumptions: string[]}
    System: {id: string, components: string[], environment: string?}
    Dataset: {id: string, schema: string, provenance: string, licence: string?}
    Proof: {id: string, theorem: string, assumptions: string[], verifier: string?}
    Experiment: {id: string, method: string, environment: string, observations: string[], provenance: string}
    Assertion: {id: string, subject: string, predicate: string, object: string, evidence: string[], confidence: number, context: string?}

  predicates:
    solves(algorithm: Algorithm, problem: ComputationalProblem)
    implements(program: Program, algorithm: Algorithm)
    uses_structure(algorithm: Algorithm, structure: DataStructure)
    executes_on(program: Program, system: System)
    modelled_by(problem: ComputationalProblem, model: ComputationalModel)
    verified_by(assertion: Assertion, proof: Proof)
    evaluated_by(algorithm: Algorithm, experiment: Experiment)
    processes(program: Program, dataset: Dataset)
    depends_on(a: string, b: string)
    equivalent_under(a: string, b: string, assumptions: string[])

  constraints:
    - "Every relationship endpoint must resolve to a typed entity."
    - "Confidence must lie within [0,1]."
    - "A benchmark result is not a proof of correctness or asymptotic complexity."
    - "Complexity claims require an explicit computational model and input-size convention."
    - "Correctness and equivalence are conditional on specified assumptions and semantics."
    - "Dependency and implementation relations are not automatically transitive."
    - "Experimental observations require reproducible environment and provenance details."
    - "Never equate source-code similarity with functional or semantic identity."

  inference:
    rule implementation_support:
      if implements(p,a) and solves(a,q) and satisfies_preconditions(p,a,q)
      then candidate_solution(p,q)
      confidence: "requires verification of implementation fidelity and operating assumptions"
    rule verified_claim:
      if verified_by(claim,proof) and valid_proof(proof) and assumptions_hold(proof)
      then supported_by_formal_evidence(claim,proof)
      confidence: "retain proof scope and assumptions"
    rule dependency_reachability:
      if depends_on(a,b) and depends_on(b,c) and compatible_dependency_context(a,b,c)
      then indirectly_depends_on(a,c)
      confidence: "preserve complete dependency path; do not infer direct dependency"

  SEMANTIC_EQUIVALENCE:
    - "Normalise identifiers against versioned language, standard and ontology vocabularies."
    - "Distinguish syntactic similarity, behavioural equivalence and formal equivalence."
    - "Preserve execution environment, data types and computational assumptions."

  CONFIDENCE:
    range: [0,1]
    factors: [formal_verification, empirical_replication, source_reliability, implementation_fidelity, assumption_validity]
    policy: "Never manufacture certainty through inference chaining; separate proof status from empirical confidence."

  VALIDATION:
    - "Check entity types, identifiers, constraints, preconditions and provenance."
    - "Validate proofs within their stated formal systems and assumptions."
    - "Flag conflicting complexity, correctness and performance claims."
    - "Retain unresolved alternatives rather than forcing equivalence."

  FLOW_HASH:
    algorithm: "SHA-256"
    input: "canonicalised ontology version, typed assertions, inference rules and provenance"
    note: "Compute at execution; no hash value is claimed here."

  UPDATE_MODEL:
    strategy: "versioned, provenance-preserving incremental update"
    steps: [ingest, normalise, type_check, validate, compare, reconcile, recompute_inferences, publish]
    rollback: true

  AI_CONSUMPTION:
    representation: "typed computer-science knowledge graph with evidence-backed assertions"
    outputs: [entity_links, relation_triples, proof_links, dependency_paths, uncertainty_annotations, provenance_records]
    safeguards: [preserve_assumptions, distinguish_proof_from_benchmark, no_unsupported_equivalence, no_unverified_correctness_claims]
}

END FLOW ALGEBRA