Algorithmic Mathematics Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Algorithmic Mathematics Ontology within the Kireth Research Semantic Library. Algorithmic mathematics studies the mathematical structure, correctness, efficiency and computational behaviour of algorithms used to solve mathematical problems. This ontology supports algorithm design, recursion, iteration, invariants, correctness proofs, termination, complexity, exact and approximate algorithms, deterministic and randomised methods, divide-and-conquer, dynamic programming, greedy methods, graph algorithms, numerical algorithms, symbolic algorithms, optimisation procedures and relationships with computational mathematics, discrete mathematics, logic and complexity theory.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Algorithmic Mathematics Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Foundations of Computational Mathematics / Algorithmic Mathematics"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/foundations-of-computational-mathematics/algorithmic-mathematics-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = AlgorithmicMathematics
 ENTITY_CLASS = MathematicalAlgorithmFramework
 PRIMARY_CONTEXT = FoundationsOfComputationalMathematics
 DEFINITION = "Algorithmic mathematics is the mathematical study of finite procedures for solving problems, including their structure, correctness, termination, complexity and approximation behaviour."
 SYMBOLIC_FORMS = [
  "A:Input->Output",
  "T(n)=aT(n/b)+f(n)",
  "I(k+1)=F(I(k))",
  "correctness=partial_correctness+termination"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for algorithm structure, correctness, invariants, termination, recursion, complexity, exactness, approximation, randomness and computational problem solving."
}

SCOPE {
 INCLUDE = [
  AlgorithmicMathematics,
  Algorithm,
  MathematicalAlgorithm,
  ComputationalProcedure,
  Input,
  Output,
  State,
  Step,
  Instruction,
  Iteration,
  Loop,
  Recursion,
  RecursiveAlgorithm,
  IterativeAlgorithm,
  BaseCase,
  RecurrenceRelation,
  LoopInvariant,
  Invariant,
  Precondition,
  Postcondition,
  Correctness,
  PartialCorrectness,
  TotalCorrectness,
  Termination,
  TerminationProof,
  RankingFunction,
  VariantFunction,
  DeterministicAlgorithm,
  RandomisedAlgorithm,
  ProbabilisticAlgorithm,
  ExactAlgorithm,
  ApproximationAlgorithm,
  HeuristicAlgorithm,
  OnlineAlgorithm,
  OfflineAlgorithm,
  SequentialAlgorithm,
  ParallelAlgorithm,
  DistributedAlgorithm,
  DivideAndConquer,
  DynamicProgramming,
  GreedyAlgorithm,
  Backtracking,
  BranchAndBound,
  SearchAlgorithm,
  SortingAlgorithm,
  SelectionAlgorithm,
  EnumerationAlgorithm,
  GraphAlgorithm,
  ShortestPathAlgorithm,
  MinimumSpanningTreeAlgorithm,
  MatchingAlgorithm,
  FlowAlgorithm,
  StringAlgorithm,
  NumberTheoreticAlgorithm,
  AlgebraicAlgorithm,
  MatrixAlgorithm,
  NumericalAlgorithm,
  SymbolicAlgorithm,
  OptimisationAlgorithm,
  RootFindingAlgorithm,
  IntegrationAlgorithm,
  DifferentiationAlgorithm,
  IterativeSolver,
  DirectSolver,
  FixedPointAlgorithm,
  NewtonAlgorithm,
  Complexity,
  TimeComplexity,
  SpaceComplexity,
  WorstCaseComplexity,
  AverageCaseComplexity,
  BestCaseComplexity,
  AmortisedComplexity,
  AsymptoticAnalysis,
  BigONotation,
  BigOmegaNotation,
  BigThetaNotation,
  RecurrenceSolving,
  MasterTheorem,
  PolynomialTime,
  ExponentialTime,
  PseudoPolynomialTime,
  FixedParameterTractable,
  NPProblem,
  NPCompleteProblem,
  NPHardProblem,
  Reduction,
  PolynomialReduction,
  ApproximationRatio,
  RandomVariable,
  ExpectedRunningTime,
  FailureProbability,
  MonteCarloAlgorithm,
  LasVegasAlgorithm,
  AlgorithmicStability,
  NumericalStability,
  ErrorBound,
  Residual,
  Convergence,
  ConvergenceRate,
  DataStructure,
  Array,
  Matrix,
  Graph,
  Tree,
  Heap,
  Queue,
  Stack,
  PriorityQueue,
  HashStructure,
  SparseRepresentation,
  Parallelism,
  Work,
  Span,
  Speedup,
  Scalability,
  Verification,
  FormalVerification,
  ProofOfCorrectness,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  SoftwareEngineeringWithoutMathematicalAlgorithmAnalysis,
  PureComputabilityWithoutConcreteAlgorithmStructure,
  NumericalComputationWithoutAlgorithmicReasoning,
  HeuristicProcedureWithoutDefinedInputOutputSemantics
 ]
 DISAMBIGUATION_RULE = "When a finite mathematical procedure is analysed in terms of correctness, termination, complexity, structure or approximation, interpret the context as algorithmic mathematics."
}

CORE_CONCEPTS {
 AlgorithmicMathematics = "Mathematical study of algorithms as problem-solving procedures."
 Algorithm = "Finite or well-defined procedure mapping admissible inputs to outputs."
 Correctness = "Property that an algorithm satisfies its specified input-output behaviour."
 Termination = "Property that an algorithm halts after finitely many steps for admissible inputs."
 LoopInvariant = "Property preserved across iterations and used in correctness reasoning."
 RecurrenceRelation = "Equation describing recursively defined algorithmic cost or state."
 Complexity = "Resource consumption of an algorithm as a function of input size."
 ApproximationAlgorithm = "Algorithm returning provably near-optimal or bounded-error solutions."
 RandomisedAlgorithm = "Algorithm using randomness as part of its computational process."
 Reduction = "Transformation showing that solving one problem enables solving another."
}

RELATIONS {
 AlgorithmicMathematics --is_child_of--> FoundationsOfComputationalMathematics
 Algorithm --maps--> InputToOutput
 Algorithm --contains--> Step
 IterativeAlgorithm --uses--> Loop
 RecursiveAlgorithm --uses--> Recursion
 RecursiveAlgorithm --has--> BaseCase
 LoopInvariant --supports--> CorrectnessProof
 Precondition --constrains--> ValidInput
 Postcondition --specifies--> ValidOutput
 PartialCorrectness --plus--> Termination
 TotalCorrectness --requires--> PartialCorrectness
 TotalCorrectness --requires--> Termination
 RecurrenceRelation --models--> RecursiveCost
 DivideAndConquer --induces--> RecurrenceRelation
 DynamicProgramming --reuses--> OverlappingSubproblems
 GreedyAlgorithm --uses--> LocalChoice
 Backtracking --explores--> SearchTree
 BranchAndBound --prunes--> SearchTree
 Complexity --measures--> ResourceUse
 PolynomialReduction --relates--> ComputationalProblems
 ApproximationRatio --measures--> ApproximationQuality
 MonteCarloAlgorithm --allows--> BoundedFailureProbability
 LasVegasAlgorithm --guarantees--> CorrectOutput
 ParallelAlgorithm --has--> Work
 ParallelAlgorithm --has--> Span
 Verification --checks--> AlgorithmImplementation
 FormalVerification --proves--> AlgorithmProperties
}

OPERATORS {
 ALGORITHM(A,x) := y=A(x)
 LOOP_INVARIANT(I,k) := I(k)->I(k+1)
 TOTAL_CORRECTNESS(P,A,Q) := {P}A{Q} and termination(A)
 RECURRENCE(T,n,a,b,f) := T(n)=a*T(n/b)+f(n)
 BIG_O(f,g) := exists_c,n0 forall_n>=n0: f(n)<=c*g(n)
 BIG_OMEGA(f,g) := exists_c,n0 forall_n>=n0: f(n)>=c*g(n)
 BIG_THETA(f,g) := BIG_O(f,g) and BIG_OMEGA(f,g)
 EXPECTED_TIME(T) := E[T]
 APPROXIMATION_RATIO(sol,opt) := value(sol)/value(opt) in_declared_direction
 PARALLEL_SPEEDUP(T1,Tp) := S_p=T1/Tp
 PARALLEL_EFFICIENCY(T1,Tp,p) := E_p=T1/(p*Tp)
}

AXIOMS {
 A1 = "An algorithm requires explicit input and output semantics."
 A2 = "Correctness and efficiency are distinct properties."
 A3 = "Partial correctness does not imply termination."
 A4 = "Asymptotic complexity describes growth rather than exact runtime."
 A5 = "Randomised algorithms require probabilistic correctness or runtime semantics."
 A6 = "Approximation algorithms require explicit quality guarantees or error bounds."
 A7 = "Data representation can materially affect algorithmic complexity."
 A8 = "Algorithmic conclusions require correctness, complexity and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(problem,input_domain,output_requirement,constraints)
 R2_STRUCTURE = classify(iterative,recursive,divide_and_conquer,dynamic_programming,greedy,search_or_other)
 R3_CORRECTNESS = define(preconditions,postconditions,invariants)
 R4_TERMINATION = identify(base_cases,ranking_or_variant_function)
 R5_COMPLEXITY = derive(time,space,worst_case,average_case,amortised_cost)
 R6_APPROXIMATION = if_required derive(error_or_approximation_ratio)
 R7_RANDOMNESS = if_randomised analyse(expected_runtime,success_probability,variance)
 R8_DATA_STRUCTURE = choose(representation_supporting_required_operations)
 R9_PARALLEL = if_parallel analyse(work,span,communication,speedup)
 R10_VALIDATION = verify_correctness,benchmarks,edge_cases,complexity_claims,reproducibility)
}

CONSTRAINTS {
 C1 = "A mathematically correct algorithm can still be impractical because of complexity."
 C2 = "Asymptotic bounds do not capture constant factors or hardware effects."
 C3 = "Average-case analysis depends on an input distribution."
 C4 = "Randomised algorithms require explicit probability models."
 C5 = "Greedy methods are not globally optimal without supporting structure."
 C6 = "Dynamic programming can trade increased memory for reduced repeated computation."
 C7 = "Recursive algorithms can incur stack or depth limitations."
 C8 = "Approximation ratios depend on optimisation direction and problem definition."
 C9 = "Parallel speedup is limited by serial work and communication."
 C10 = "Benchmark performance does not establish formal correctness."
}

SEMANTIC_EQUIVALENCE {
 "AlgorithmicMathematics" <=> "MathematicsOfAlgorithms"
 "BigONotation" <=> "AsymptoticUpperBoundNotation"
 "BigOmegaNotation" <=> "AsymptoticLowerBoundNotation"
 "BigThetaNotation" <=> "AsymptoticTightBoundNotation"
 "MonteCarloAlgorithm" <=> "RandomisedBoundedErrorAlgorithm"
 "LasVegasAlgorithm" <=> "RandomisedAlwaysCorrectAlgorithm"
}

VALIDATION {
 V1 = "Input domain and output specification are explicit."
 V2 = "Correctness argument is documented."
 V3 = "Termination is justified where required."
 V4 = "Complexity model and input-size measure are explicit."
 V5 = "Worst-case versus average-case claims are distinguished."
 V6 = "Randomised failure probabilities or expected costs are reported."
 V7 = "Approximation guarantees are stated correctly."
 V8 = "Edge cases and degenerate inputs are tested."
 V9 = "Parallel complexity distinguishes work from span."
 V10 = "Benchmarking is distinguished from mathematical proof."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 ALGORITHMIC_MATHEMATICS_DEFINITION = 0.99
 CORRECTNESS_REASONING = 0.99
 TERMINATION_REASONING = 0.99
 COMPLEXITY_REASONING = 0.99
 RECURRENCE_REASONING = 0.99
 APPROXIMATION_REASONING = 0.98
 RANDOMISED_REASONING = 0.98
 PARALLEL_REASONING = 0.98
 POLICY = "Reduce confidence when problem specification, input-size measure, invariants, termination conditions, complexity model, randomness or approximation guarantees are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  AlgorithmicMathematicsReasoning,
  AlgorithmDesignReasoning,
  CorrectnessProofReasoning,
  LoopInvariantReasoning,
  TerminationReasoning,
  RecurrenceReasoning,
  ComplexityReasoning,
  DivideAndConquerReasoning,
  DynamicProgrammingReasoning,
  GreedyReasoning,
  SearchReasoning,
  ApproximationAlgorithmReasoning,
  RandomisedAlgorithmReasoning,
  ReductionReasoning,
  ParallelAlgorithmReasoning,
  FormalVerificationReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]
 NORMALISE {
  "algorithmic mathematics" -> AlgorithmicMathematics
  "mathematics of algorithms" -> AlgorithmicMathematics
  "Big O" -> BigONotation
  "Big Omega" -> BigOmegaNotation
  "Big Theta" -> BigThetaNotation
  "Monte Carlo algorithm" -> MonteCarloAlgorithm
  "Las Vegas algorithm" -> LasVegasAlgorithm
 }
}

EXECUTION_RULES {
 E1 = "If a mathematical procedure is analysed for correctness, termination or complexity, activate AlgorithmicMathematicsOntology."
 E2 = "If an algorithm is recursive, identify base cases and derive recurrence relations where relevant."
 E3 = "If an iterative algorithm is analysed, identify loop invariants and stopping conditions."
 E4 = "If exact solution is expensive, consider approximation or heuristic methods with explicit guarantees."
 E5 = "If randomness is used, quantify expected runtime and error probability."
 E6 = "If multiple subproblems overlap, consider dynamic programming."
 E7 = "If local choices are proposed, verify conditions supporting greedy optimality."
 E8 = "If parallel execution is relevant, analyse work, span and communication."
 E9 = "Any algorithmic claim should be validated for correctness, termination, complexity and reproducibility."
}

RECURSION {
 ENTRY = AlgorithmicMathematics
 EXPAND(AlgorithmicMathematics) -> [
  Algorithm, MathematicalAlgorithm, ComputationalProcedure, Input, Output,
  State, Step, Instruction, Iteration, Loop, Recursion,
  RecursiveAlgorithm, IterativeAlgorithm, BaseCase, RecurrenceRelation,
  LoopInvariant, Invariant, Precondition, Postcondition, Correctness,
  PartialCorrectness, TotalCorrectness, Termination, TerminationProof,
  RankingFunction, VariantFunction, DeterministicAlgorithm,
  RandomisedAlgorithm, ProbabilisticAlgorithm, ExactAlgorithm,
  ApproximationAlgorithm, HeuristicAlgorithm, OnlineAlgorithm,
  OfflineAlgorithm, SequentialAlgorithm, ParallelAlgorithm,
  DistributedAlgorithm, DivideAndConquer, DynamicProgramming,
  GreedyAlgorithm, Backtracking, BranchAndBound, SearchAlgorithm,
  SortingAlgorithm, SelectionAlgorithm, EnumerationAlgorithm,
  GraphAlgorithm, ShortestPathAlgorithm, MinimumSpanningTreeAlgorithm,
  MatchingAlgorithm, FlowAlgorithm, StringAlgorithm,
  NumberTheoreticAlgorithm, AlgebraicAlgorithm, MatrixAlgorithm,
  NumericalAlgorithm, SymbolicAlgorithm, OptimisationAlgorithm,
  RootFindingAlgorithm, IntegrationAlgorithm, DifferentiationAlgorithm,
  IterativeSolver, DirectSolver, FixedPointAlgorithm, NewtonAlgorithm,
  Complexity, TimeComplexity, SpaceComplexity, WorstCaseComplexity,
  AverageCaseComplexity, BestCaseComplexity, AmortisedComplexity,
  AsymptoticAnalysis, BigONotation, BigOmegaNotation, BigThetaNotation,
  RecurrenceSolving, MasterTheorem, PolynomialTime, ExponentialTime,
  PseudoPolynomialTime, FixedParameterTractable, NPProblem,
  NPCompleteProblem, NPHardProblem, Reduction, PolynomialReduction,
  ApproximationRatio, ExpectedRunningTime, FailureProbability,
  MonteCarloAlgorithm, LasVegasAlgorithm, AlgorithmicStability,
  NumericalStability, ErrorBound, Residual, Convergence,
  ConvergenceRate, DataStructure, Array, Matrix, Graph, Tree, Heap,
  Queue, Stack, PriorityQueue, HashStructure, SparseRepresentation,
  Parallelism, Work, Span, Speedup, Scalability, Verification,
  FormalVerification, ProofOfCorrectness, Benchmarking, Reproducibility
 ]
 EXPAND(AlgorithmFamilies) -> [
  RecursiveAndIterativeAlgorithms,
  DivideAndConquerAlgorithms,
  DynamicProgrammingAlgorithms,
  GreedyAlgorithms,
  SearchAndEnumerationAlgorithms,
  NumericalAlgorithms,
  ApproximationAlgorithms,
  RandomisedAlgorithms,
  ParallelAlgorithms
 ]
 STOP_CONDITION = "Stop when problem specification, algorithm structure, correctness, termination, complexity, approximation or randomisation semantics and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Foundations of Computational Mathematics"
 RELATED_ONTOLOGIES = [
  "Foundations of Computational Mathematics",
  "Computational Mathematics Ontology 2",
  "Numerical Computation Ontology",
  "Discrete Mathematics Ontologies",
  "Mathematical Logic Ontologies",
  "Graph Theory Ontologies",
  "Optimisation Ontologies",
  "Complexity Theory Ontologies",
  "Numerical Analysis Ontologies",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Algorithmic Mathematics -> Foundations of Computational Mathematics for parent semantics",
  "Algorithmic Mathematics -> Computational Mathematics Ontology 2 for core computational semantics",
  "Algorithmic Mathematics -> Numerical Computation for numerical algorithms",
  "Algorithmic Mathematics -> Discrete Mathematics for finite structures",
  "Algorithmic Mathematics -> Mathematical Logic for correctness and computability",
  "Algorithmic Mathematics -> Graph Theory for graph algorithms",
  "Algorithmic Mathematics -> Optimisation for optimisation algorithms",
  "Algorithmic Mathematics -> Complexity Theory for resource bounds and reductions",
  "Algorithmic Mathematics -> Numerical Analysis for stable numerical algorithms",
  "Algorithmic Mathematics -> HPC for parallel algorithms"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible algorithm classes, proof structures or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve input-output semantics.",
  "Preserve correctness-versus-efficiency distinction.",
  "Preserve partial-versus-total correctness distinction.",
  "Preserve iterative-versus-recursive distinction.",
  "Preserve deterministic-versus-randomised distinction.",
  "Preserve exact-versus-approximation distinction.",
  "Preserve worst-case-versus-average-case distinction.",
  "Preserve machine-readable algorithmic-mathematics semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Algorithmic mathematics studies mathematical procedures in terms of structure, correctness, termination, complexity and approximation."
 CORRECTNESS_SUMMARY = "Preconditions, postconditions and invariants support formal reasoning about algorithm correctness."
 TERMINATION_SUMMARY = "Termination proofs show that admissible computations halt."
 COMPLEXITY_SUMMARY = "Time, space, worst-case, average-case and amortised analyses characterise resource growth."
 DESIGN_SUMMARY = "Divide-and-conquer, dynamic programming, greedy, backtracking and branch-and-bound provide major algorithm-design paradigms."
 RANDOMISED_SUMMARY = "Randomised algorithms require explicit expected-runtime or failure-probability semantics."
 APPROXIMATION_SUMMARY = "Approximation algorithms trade exactness for efficiency under declared quality guarantees."
 VALIDATION_SUMMARY = "Algorithmic claims should be checked for correctness, termination, complexity, edge cases and reproducibility."
}

FLOW {
 INPUT
 -> detect_algorithmic_mathematics_context
 -> identify_problem_input_domain_output_requirement_and_constraints
 -> classify_iterative_recursive_divide_and_conquer_dynamic_programming_greedy_search_randomised_approximation_or_parallel_algorithm
 -> define_preconditions_postconditions_invariants_and_state_transitions
 -> prove_or_assess_partial_correctness
 -> prove_or_assess_termination
 -> derive_time_space_worst_case_average_case_or_amortised_complexity
 -> if_recursive_solve_recurrence
 -> if_randomised_compute_expected_cost_and_failure_probability
 -> if_approximate_compute_error_or_approximation_ratio
 -> if_parallel_compute_work_span_speedup_and_scalability
 -> validate_edge_cases_benchmarks_correctness_claims_and_reproducibility
 -> route_to_foundations_computational_mathematics_core_computational_mathematics_numerical_computation_discrete_mathematics_logic_graph_theory_optimisation_complexity_numerical_analysis_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Algorithmic Mathematics Ontology defines the mathematical study of algorithms. It supports inputs, outputs, states, steps, loops and recursion, recursive and iterative algorithms, base cases and recurrence relations, preconditions, postconditions, loop invariants, partial and total correctness, termination proofs and ranking functions, deterministic, randomised, exact, approximate, heuristic, online, sequential, parallel and distributed algorithms, divide-and-conquer, dynamic programming, greedy, backtracking and branch-and-bound methods, search, sorting, selection, graph, string, number-theoretic, algebraic, matrix, numerical and optimisation algorithms, time and space complexity, worst, average and amortised complexity, asymptotic notation, recurrence solving and the Master theorem, polynomial and exponential time, reductions, NP-related classes, approximation ratios, Monte Carlo and Las Vegas algorithms, data structures, work and span, parallel speedup, formal verification, benchmarking and reproducibility."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-MATHEMATICS-ALGORITHMIC-MATHEMATICS-ONTOLOGY-V1"
}

}

END_FLOW