Complexity Analysis Ontology

AI SEARCH

FLOW ALGEBRA — COMPLEXITY ANALYSIS ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms/complexity-analysis-ontology.html

FLOW COMPLEXITY_ANALYSIS_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Complexity Analysis Ontology"
    PURPOSE = "Formalise algorithmic complexity, input-size models, resource functions, asymptotic bounds, cases, recurrences, amortised analysis, complexity classes and empirical evidence."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    COMPLEXITY_ANALYSIS
    ALGORITHM
    ALGORITHM_VARIANT
    IMPLEMENTATION
    INPUT
    INPUT_SIZE
    INPUT_SIZE_PARAMETER
    INPUT_DISTRIBUTION
    RESOURCE
    TIME_RESOURCE
    SPACE_RESOURCE
    COMMUNICATION_RESOURCE
    IO_RESOURCE
    BASIC_OPERATION
    COST_MODEL
    UNIT_COST_MODEL
    RAM_MODEL
    COMPARISON_MODEL
    RESOURCE_FUNCTION
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    AUXILIARY_SPACE
    BEST_CASE
    AVERAGE_CASE
    EXPECTED_CASE
    WORST_CASE
    AMORTISED_COMPLEXITY
    ASYMPTOTIC_ANALYSIS
    ASYMPTOTIC_BOUND
    UPPER_BOUND
    LOWER_BOUND
    TIGHT_BOUND
    BIG_O
    BIG_OMEGA
    BIG_THETA
    LITTLE_O
    LITTLE_OMEGA
    CONSTANT_TIME
    LOGARITHMIC_TIME
    LINEAR_TIME
    LINEARITHMIC_TIME
    POLYNOMIAL_TIME
    EXPONENTIAL_TIME
    FACTORIAL_TIME
    RECURRENCE_RELATION
    RECURSION_TREE
    MASTER_THEOREM
    SUBSTITUTION_METHOD
    ITERATION_METHOD
    AGGREGATE_METHOD
    ACCOUNTING_METHOD
    POTENTIAL_METHOD
    POTENTIAL_FUNCTION
    ACTUAL_COST
    AMORTISED_COST
    COMPLEXITY_CLASS
    P
    NP
    CO_NP
    NP_HARD
    NP_COMPLETE
    PSPACE
    EXPTIME
    PARAMETERISED_COMPLEXITY
    FIXED_PARAMETER_TRACTABLE
    RANDOMISED_COMPLEXITY
    EXPECTED_RUNNING_TIME
    PROBABILISTIC_BOUND
    REDUCTION
    LOWER_BOUND_PROOF
    UPPER_BOUND_PROOF
    BENCHMARK
    EMPIRICAL_RUNTIME
    EMPIRICAL_MEMORY
    HARDWARE
    RUNTIME
    COMPILER
    CONFIGURATION
    DATASET
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    ANALYSES
    HAS_INPUT
    HAS_INPUT_SIZE
    HAS_PARAMETER
    HAS_DISTRIBUTION
    MEASURES
    COUNTS
    HAS_RESOURCE
    HAS_COST_MODEL
    HAS_RESOURCE_FUNCTION
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_AUXILIARY_SPACE
    HAS_BEST_CASE
    HAS_AVERAGE_CASE
    HAS_EXPECTED_CASE
    HAS_WORST_CASE
    HAS_AMORTISED_COMPLEXITY
    BOUNDED_ABOVE_BY
    BOUNDED_BELOW_BY
    TIGHTLY_BOUNDED_BY
    HAS_BIG_O
    HAS_BIG_OMEGA
    HAS_BIG_THETA
    DOMINATES
    GROWS_AS
    HAS_RECURRENCE
    SOLVED_BY
    HAS_RECURSION_TREE
    USES_POTENTIAL_FUNCTION
    HAS_ACTUAL_COST
    HAS_AMORTISED_COST
    BELONGS_TO_COMPLEXITY_CLASS
    REDUCES_TO
    PROVEN_BY
    BENCHMARKED_BY
    EXECUTED_ON
    HAS_CONFIGURATION
    USES_DATASET
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    ALGORITHM_SPECIFICATIONS
    ALGORITHM_VARIANTS
    PSEUDOCODE
    SOURCE_CODE
    INPUT_SIZE_DEFINITIONS
    INPUT_DISTRIBUTION_DATA
    COST_MODEL_DEFINITIONS
    OPERATION_COUNTS
    RESOURCE_USAGE_FUNCTIONS
    RECURRENCE_RELATIONS
    RECURSION_TREE_DATA
    AMORTISED_ANALYSIS_DATA
    COMPLEXITY_CLASS_DATA
    REDUCTION_PROOFS
    LOWER_BOUND_PROOFS
    UPPER_BOUND_PROOFS
    BENCHMARK_DATA
    HARDWARE_DATA
    RUNTIME_DATA
    COMPILER_DATA
    CONFIGURATION_DATA
    DATASET_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_COMPLEXITY_ANALYSIS_IDENTIFIERS
    NORMALISE_ALGORITHM_AND_VARIANT_IDENTIFIERS
    NORMALISE_INPUT_SIZE_PARAMETERS
    NORMALISE_INPUT_DISTRIBUTIONS
    NORMALISE_RESOURCE_TYPES
    NORMALISE_COST_MODELS
    NORMALISE_OPERATION_COUNTS
    NORMALISE_RESOURCE_FUNCTIONS
    NORMALISE_ASYMPTOTIC_NOTATION
    NORMALISE_COMPLEXITY_CLASS_NAMES
    NORMALISE_RECURRENCE_RELATIONS
    NORMALISE_BENCHMARK_UNITS
    NORMALISE_HARDWARE_RUNTIME_AND_COMPILER_CONTEXT
    RESOLVE_ANALYSIS_ALGORITHM_AND_EVIDENCE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS COMPLEXITY_ANALYSIS_PIPELINE {
    ALGORITHM_REFERENCE
      -> ALGORITHM_VARIANT_RESOLUTION
      -> INPUT_SIZE_MODEL
      -> COST_MODEL
      -> RESOURCE_FUNCTION
      -> CASE_ANALYSIS
      -> ASYMPTOTIC_ANALYSIS
      -> BOUND_DERIVATION
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS INPUT_SIZE_REASONING {
    INPUT
      -> STRUCTURAL_PARAMETERS
      -> INPUT_SIZE_PARAMETER_SET
      -> RELEVANT_SIZE_PARAMETERS
      -> COMPLEXITY_DOMAIN
  }

  PROCESS COST_MODEL_REASONING {
    ALGORITHM
      -> BASIC_OPERATIONS

    BASIC_OPERATIONS
      -> COST_ASSIGNMENT
      -> COST_MODEL

    EXECUTION_PATH
      -> OPERATION_COUNTS

    OPERATION_COUNTS + COST_MODEL
      -> RESOURCE_FUNCTION
  }

  PROCESS CASE_REASONING {
    INPUTS_OF_SIZE_N
      -> RESOURCE_COSTS

    MINIMUM_COST
      -> BEST_CASE

    MAXIMUM_COST
      -> WORST_CASE

    DISTRIBUTION_OVER_INPUTS
      -> EXPECTED_COST

    EXPECTED_COST
      -> AVERAGE_OR_EXPECTED_CASE_ACCORDING_TO_DEFINED_MODEL
  }

  PROCESS ASYMPTOTIC_REASONING {
    RESOURCE_FUNCTION_F_N
      -> DOMINANT_GROWTH
      -> CANDIDATE_BOUND_G_N

    UPPER_BOUND_PROOF
      -> BIG_O

    LOWER_BOUND_PROOF
      -> BIG_OMEGA

    MATCHING_UPPER_AND_LOWER_BOUND
      -> BIG_THETA
  }

  PROCESS RECURRENCE_REASONING {
    RECURSIVE_ALGORITHM
      -> SUBPROBLEM_COSTS

    SUBPROBLEM_COSTS + NONRECURSIVE_WORK
      -> RECURRENCE_RELATION

    RECURRENCE_RELATION
      -> SUBSTITUTION_OR_ITERATION_OR_RECURSION_TREE_OR_MASTER_THEOREM

    SOLUTION
      -> ASYMPTOTIC_BOUND
  }

  PROCESS AMORTISED_REASONING {
    OPERATION_SEQUENCE
      -> ACTUAL_COST_SEQUENCE

    AGGREGATE_METHOD
      -> TOTAL_SEQUENCE_COST / OPERATION_COUNT

    ACCOUNTING_METHOD
      -> ASSIGNED_AMORTISED_CHARGES

    POTENTIAL_METHOD
      -> ACTUAL_COST + POTENTIAL_CHANGE

    RESULT
      -> AMORTISED_COST_BOUND
  }

  PROCESS SPACE_REASONING {
    EXECUTION
      -> INPUT_STORAGE
      -> OUTPUT_STORAGE
      -> AUXILIARY_STORAGE

    MAXIMUM_SIMULTANEOUS_AUXILIARY_STORAGE
      -> AUXILIARY_SPACE_COMPLEXITY

    DEFINED_SPACE_MODEL
      -> TOTAL_OR_AUXILIARY_SPACE_BOUND
  }

  PROCESS COMPLEXITY_CLASS_REASONING {
    COMPUTATIONAL_PROBLEM
      -> RESOURCE_BOUND_MODEL

    RESOURCE_BOUND
      -> COMPLEXITY_CLASS_MEMBERSHIP_CANDIDATE

    REDUCTIONS_AND_PROOFS
      -> HARDNESS_OR_COMPLETENESS_EVIDENCE

    VERIFIED_EVIDENCE
      -> COMPLEXITY_CLASS_RELATION
  }

  PROCESS EMPIRICAL_REASONING {
    IMPLEMENTATION + DATASET + HARDWARE + RUNTIME + CONFIGURATION
      -> BENCHMARK

    BENCHMARK
      -> EMPIRICAL_RUNTIME
      -> EMPIRICAL_MEMORY

    REPEATED_RUNS
      -> EMPIRICAL_DISTRIBUTION
      -> OBSERVED_SCALING_PROFILE
  }

  RULES {
    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE ALGORITHM_VARIANT_INPUT_SIZE_COST_MODEL_AND_CASE_CONTEXT

    IF AVERAGE_CASE_IS_ASSERTED
    THEN REQUIRE DEFINED_INPUT_DISTRIBUTION_OR_AVERAGING_MODEL

    IF BIG_O_IS_ASSERTED
    THEN DO_NOT AUTOMATICALLY_ASSERT TIGHT_BOUND

    IF BIG_THETA_IS_ASSERTED
    THEN REQUIRE MATCHING_ASYMPTOTIC_UPPER_AND_LOWER_BOUNDS

    IF AMORTISED_BOUND_IS_ASSERTED
    THEN PRESERVE OPERATION_SEQUENCE_MODEL

    IF MASTER_THEOREM_IS_USED
    THEN REQUIRE ITS_APPLICABILITY_CONDITIONS

    IF EMPIRICAL_RUNTIME_IS_REPORTED
    THEN DO_NOT TREAT_IT_AS_FORMAL_ASYMPTOTIC_PROOF

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND COMPLEXITY_ANALYSIS_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_VARIANT_CERTAINTY,
        INPUT_SIZE_MODEL_CERTAINTY,
        COST_MODEL_CERTAINTY,
        RESOURCE_FUNCTION_CERTAINTY,
        CASE_MODEL_CERTAINTY,
        ASYMPTOTIC_PROOF_QUALITY,
        COMPLEXITY_CLASS_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF INPUT_SIZE_OR_COST_MODEL_IS_UNKNOWN
    THEN REDUCE_COMPLEXITY_CONFIDENCE

    IF AVERAGE_CASE_DISTRIBUTION_IS_UNKNOWN
    THEN REDUCE_AVERAGE_CASE_CONFIDENCE

    IF FORMAL_BOUND_PROOFS_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ALGORITHM_IDENTIFIER,
        ALGORITHM_VARIANT,
        INPUT_SIZE_MODEL,
        COST_MODEL,
        RESOURCE_TYPE,
        CASE_CONTEXT
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    COMPLEXITY_ANALYSIS != BENCHMARKING
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    SPACE_COMPLEXITY != RAW_MEMORY_MEASUREMENT
    BIG_O != BIG_THETA
    BIG_OMEGA != BIG_THETA
    ASYMPTOTIC_BOUND != EXACT_RESOURCE_FUNCTION
    BEST_CASE != WORST_CASE
    AVERAGE_CASE != EXPECTED_CASE_WITHOUT_DEFINED_MODEL
    AMORTISED_COMPLEXITY != AVERAGE_CASE_COMPLEXITY
    INPUT_SIZE != INPUT_VALUE
    COST_MODEL != HARDWARE_RUNTIME
    MASTER_THEOREM != UNIVERSAL_RECURRENCE_SOLVER
    COMPLEXITY_CLASS != ALGORITHM_RUNNING_TIME_AS_IDENTICAL_CONCEPT
    NP_HARD != NP_COMPLETE
    EMPIRICAL_SCALING != FORMAL_ASYMPTOTIC_BOUND
    CONSTANT_FACTORS_MAY_MATTER_EMPIRICALLY_WHILE_BEING_IGNORED_ASYMPTOTICALLY
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_ALGORITHM_IDENTIFIER
    CHECK_ALGORITHM_VARIANT
    CHECK_INPUT_SIZE_MODEL
    CHECK_INPUT_DISTRIBUTION_IF_REQUIRED
    CHECK_RESOURCE_TYPE
    CHECK_COST_MODEL
    CHECK_OPERATION_COUNTS
    CHECK_RESOURCE_FUNCTION
    CHECK_CASE_CONTEXT
    CHECK_UPPER_BOUND_PROOF
    CHECK_LOWER_BOUND_PROOF
    CHECK_TIGHT_BOUND_IF_ASSERTED
    CHECK_RECURRENCE_IF_APPLICABLE
    CHECK_MASTER_THEOREM_APPLICABILITY_IF_USED
    CHECK_AMORTISED_ANALYSIS_IF_APPLICABLE
    CHECK_SPACE_MODEL
    CHECK_COMPLEXITY_CLASS_EVIDENCE_IF_APPLICABLE
    CHECK_BENCHMARK_CONTEXT_IF_USED
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_COMPLEXITY_ANALYSIS_ENTITIES
    INPUT_SIZE_RELATIONS
    COST_MODEL_RELATIONS
    OPERATION_COUNT_RELATIONS
    RESOURCE_FUNCTION_RELATIONS
    BEST_AVERAGE_EXPECTED_AND_WORST_CASE_RELATIONS
    BIG_O_RELATIONS
    BIG_OMEGA_RELATIONS
    BIG_THETA_RELATIONS
    RECURRENCE_RELATIONS
    MASTER_THEOREM_RELATIONS
    AMORTISED_ANALYSIS_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    COMPLEXITY_CLASS_RELATIONS
    REDUCTION_AND_PROOF_RELATIONS
    EMPIRICAL_PERFORMANCE_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON ALGORITHM_INPUT_OR_COST_MODEL_CHANGE {
      NORMALISE
      RESOLVE_ANALYSIS_ALGORITHM_AND_EVIDENCE_IDENTITIES
      UPDATE_INPUT_SIZE_MODEL
      UPDATE_COST_MODEL
      RECOMPUTE_RESOURCE_FUNCTION
      REASSESS_CASES_AND_ASYMPTOTIC_BOUNDS
      REASSESS_COMPLEXITY_CLASS_RELATIONS_IF_APPLICABLE
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_PROOF_OR_BENCHMARK_EVIDENCE {
      LINK_EVIDENCE
      UPDATE_BOUND_PROOFS
      UPDATE_RECURRENCE_OR_AMORTISED_ANALYSIS
      UPDATE_EMPIRICAL_PROFILE
      COMPARE_EMPIRICAL_AND_FORMAL_MODELS
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_ALGORITHM
      BY_ALGORITHM_VARIANT
      BY_INPUT_SIZE
      BY_COST_MODEL
      BY_RESOURCE_FUNCTION
      BY_CASE
      BY_ASYMPTOTIC_BOUND
      BY_RECURRENCE
      BY_AMORTISED_COST
      BY_COMPLEXITY_CLASS
      BY_BENCHMARK
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_INPUT_SIZE
      ANALYSE_COST_MODELS
      DERIVE_RESOURCE_FUNCTIONS
      ANALYSE_BEST_AVERAGE_EXPECTED_AND_WORST_CASES
      ANALYSE_ASYMPTOTIC_BOUNDS
      SOLVE_RECURRENCES
      CHECK_MASTER_THEOREM_APPLICABILITY
      ANALYSE_AMORTISED_COMPLEXITY
      ANALYSE_SPACE_COMPLEXITY
      ANALYSE_COMPLEXITY_CLASSES
      ANALYSE_EMPIRICAL_EVIDENCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_FORMAL_COMPLEXITY_FROM_EMPIRICAL_PERFORMANCE
      DISTINGUISH_BIG_O_BIG_OMEGA_AND_BIG_THETA
      DISTINGUISH_AVERAGE_EXPECTED_AND_AMORTISED_COMPLEXITY
      PRESERVE_ALGORITHM_VARIANT_INPUT_SIZE_COST_MODEL_CASE_RESOURCE_AND_CONFIGURATION_CONTEXT
      APPLY_RECURRENCE_THEOREMS_ONLY_WHEN_PRECONDITIONS_ARE_MET
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_COMPLEXITY_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              COMPLEXITY_ANALYSIS_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW