Backtracking Ontology

AI SEARCH

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

FLOW BACKTRACKING_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Backtracking Ontology"
    PURPOSE = "Formalise backtracking algorithms, search spaces, partial solutions, candidate choices, constraints, pruning, recursion, state restoration, solutions, correctness and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    BACKTRACKING
    BACKTRACKING_ALGORITHM
    SEARCH_PROBLEM
    SEARCH_SPACE
    STATE_SPACE
    SEARCH_TREE
    SEARCH_NODE
    ROOT_STATE
    STATE
    PARTIAL_SOLUTION
    COMPLETE_SOLUTION
    CANDIDATE
    CANDIDATE_SET
    CHOICE
    DECISION
    DECISION_POINT
    VARIABLE
    DOMAIN
    ASSIGNMENT
    CONSTRAINT
    CONSTRAINT_SET
    FEASIBLE_STATE
    INFEASIBLE_STATE
    VALID_PARTIAL_SOLUTION
    INVALID_PARTIAL_SOLUTION
    GOAL_STATE
    DEAD_END
    FAILURE_STATE
    SUCCESS_STATE
    RECURSIVE_CALL
    CALL_STACK
    STACK_FRAME
    DEPTH
    BRANCHING_FACTOR
    EXPANSION
    DESCENT
    BACKTRACK_STEP
    STATE_RESTORATION
    UNDO_OPERATION
    PRUNING
    CONSTRAINT_PRUNING
    FORWARD_CHECKING
    BOUND
    BRANCH_AND_BOUND
    HEURISTIC
    VARIABLE_ORDERING
    VALUE_ORDERING
    SYMMETRY_BREAKING
    N_QUEENS
    SUDOKU
    GRAPH_COLOURING
    HAMILTONIAN_PATH
    KNIGHT_TOUR
    SUBSET_SUM
    PERMUTATION_GENERATION
    COMBINATION_GENERATION
    MAZE_SEARCH
    CONSTRAINT_SATISFACTION_PROBLEM
    SATISFIABILITY_PROBLEM
    PRECONDITION
    POSTCONDITION
    INVARIANT
    CORRECTNESS
    COMPLETENESS
    TERMINATION
    INPUT_SIZE
    NODE_COUNT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    WORST_CASE
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    SOLVES
    SEARCHES
    SEARCHES_IN
    HAS_STATE
    HAS_ROOT
    HAS_CHILD
    HAS_PARENT
    HAS_PARTIAL_SOLUTION
    HAS_CANDIDATE
    HAS_CHOICE
    HAS_DECISION
    HAS_VARIABLE
    HAS_DOMAIN
    ASSIGNS
    HAS_CONSTRAINT
    SATISFIES
    VIOLATES
    EXTENDS
    EXPANDS
    DESCENDS_TO
    BACKTRACKS_TO
    RESTORES
    UNDOS
    PRUNES
    REJECTS
    ACCEPTS
    HAS_GOAL
    REACHES
    HAS_DEAD_END
    HAS_DEPTH
    HAS_BRANCHING_FACTOR
    USES_HEURISTIC
    ORDERS_VARIABLE
    ORDERS_VALUE
    BREAKS_SYMMETRY
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_COMPLETENESS
    HAS_TERMINATION
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    IMPLEMENTED_BY
    EXECUTED_BY
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    BACKTRACKING_ALGORITHM_SPECIFICATIONS
    PROBLEM_DEFINITIONS
    PSEUDOCODE
    SOURCE_CODE
    STATE_SPACE_DEFINITIONS
    VARIABLE_AND_DOMAIN_DATA
    CANDIDATE_GENERATION_RULES
    CONSTRAINT_DEFINITIONS
    GOAL_TESTS
    PRUNING_RULES
    HEURISTIC_DEFINITIONS
    SEARCH_TREE_DATA
    EXECUTION_TRACES
    STATE_RESTORATION_TRACES
    SOLUTION_DATA
    CORRECTNESS_PROOFS
    COMPLETENESS_PROOFS
    COMPLEXITY_ANALYSES
    IMPLEMENTATION_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_BACKTRACKING_IDENTIFIERS
    NORMALISE_PROBLEM_IDENTIFIERS
    NORMALISE_STATE_IDENTIFIERS
    NORMALISE_VARIABLE_AND_DOMAIN_IDENTIFIERS
    NORMALISE_CANDIDATE_AND_CHOICE_IDENTIFIERS
    NORMALISE_CONSTRAINTS
    NORMALISE_GOAL_TESTS
    NORMALISE_PRUNING_RULES
    NORMALISE_HEURISTIC_NAMES
    NORMALISE_SEARCH_TREE_NODES
    NORMALISE_DEPTH_AND_BRANCHING_FACTOR
    NORMALISE_COMPLEXITY_NOTATION
    RESOLVE_ALGORITHM_STATE_AND_SOLUTION_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS BACKTRACKING_PIPELINE {
    SEARCH_PROBLEM
      -> INITIAL_STATE
      -> CANDIDATE_GENERATION
      -> CHOICE_SELECTION
      -> STATE_EXTENSION
      -> CONSTRAINT_CHECK
      -> ACCEPT_OR_REJECT
      -> GOAL_TEST
      -> RECURSE_OR_BACKTRACK
      -> SOLUTION_OR_SEARCH_EXHAUSTION
      -> VALIDATION
  }

  PROCESS CANDIDATE_REASONING {
    CURRENT_STATE
      -> UNRESOLVED_VARIABLE_OR_DECISION

    DECISION
      -> CANDIDATE_SET

    CANDIDATE_SET
      -> ORDERING_HEURISTIC_IF_ANY

    ORDERED_CANDIDATES
      -> NEXT_CHOICE
  }

  PROCESS EXTENSION_REASONING {
    PARTIAL_SOLUTION
      + CHOICE
      -> EXTENDED_STATE

    EXTENDED_STATE
      -> CONSTRAINT_CHECK

    CONSTRAINTS_SATISFIED
      -> VALID_PARTIAL_SOLUTION

    CONSTRAINT_VIOLATED
      -> INVALID_PARTIAL_SOLUTION
  }

  PROCESS RECURSIVE_SEARCH_REASONING {
    VALID_PARTIAL_SOLUTION
      -> GOAL_TEST

    GOAL_TRUE
      -> COMPLETE_SOLUTION

    GOAL_FALSE
      -> NEXT_DECISION
      -> RECURSIVE_CALL

    RECURSIVE_FAILURE
      -> BACKTRACK_STEP
  }

  PROCESS BACKTRACK_REASONING {
    DEAD_END_OR_FAILED_DESCENDANT
      -> CURRENT_DECISION_POINT

    CURRENT_DECISION_POINT
      -> UNDO_LAST_CHOICE

    UNDO_LAST_CHOICE
      -> RESTORE_PREVIOUS_STATE

    RESTORED_STATE
      -> NEXT_UNTRIED_CANDIDATE

    NO_UNTRIED_CANDIDATE
      -> BACKTRACK_TO_PARENT_DECISION
  }

  PROCESS PRUNING_REASONING {
    PARTIAL_STATE
      -> FEASIBILITY_ANALYSIS

    DEFINITE_CONSTRAINT_VIOLATION
      -> PRUNE_SUBTREE

    FORWARD_CHECKING
      -> FUTURE_DOMAIN_ANALYSIS

    EMPTY_REQUIRED_DOMAIN
      -> PRUNE_SUBTREE

    SAFE_PRUNING_RULE
      -> PRESERVE_ALL_VALID_SOLUTIONS
  }

  PROCESS HEURISTIC_REASONING {
    SEARCH_STATE
      -> VARIABLE_ORDERING_HEURISTIC

    SELECTED_VARIABLE
      -> VALUE_ORDERING_HEURISTIC

    ORDERED_CHOICES
      -> SEARCH_ORDER

    SEARCH_ORDER
      -> PERFORMANCE_EFFECT_WITHOUT_CHANGING_SOLUTION_SET_IF_HEURISTIC_IS_COMPLETE
  }

  PROCESS SYMMETRY_REASONING {
    SEARCH_PROBLEM
      -> SYMMETRIC_STATES_OR_CHOICES

    SYMMETRY_BREAKING_CONSTRAINT
      -> CANONICAL_REPRESENTATIVE

    CANONICAL_REPRESENTATIVE
      -> REDUCED_SEARCH_SPACE

    REQUIRE
      -> PRESERVE_AT_LEAST_ONE_REPRESENTATIVE_OF_EACH_SOLUTION_CLASS
  }

  PROCESS SOLUTION_REASONING {
    COMPLETE_STATE
      -> GOAL_TEST

    GOAL_TRUE
      -> SOLUTION

    FIRST_SOLUTION_MODE
      -> TERMINATE_ON_FIRST_SOLUTION

    ALL_SOLUTIONS_MODE
      -> RECORD_SOLUTION
      -> BACKTRACK_FOR_ADDITIONAL_SOLUTIONS
  }

  PROCESS CORRECTNESS_REASONING {
    INITIAL_STATE
      -> VALID_START

    EACH_ACCEPTED_EXTENSION
      -> CONSTRAINTS_PRESERVED

    COMPLETE_GOAL_STATE
      -> VALID_SOLUTION

    STATE_RESTORATION
      -> PREVIOUS_STATE_SEMANTICS_PRESERVED

    RESULT
      -> SOUNDNESS_EVIDENCE
  }

  PROCESS COMPLETENESS_REASONING {
    FINITE_SEARCH_SPACE
      + COMPLETE_CANDIDATE_GENERATION
      + SAFE_PRUNING
      -> ALL_RELEVANT_BRANCHES_EXPLORED_OR_PRUNED_SAFELY

    SEARCH_EXHAUSTION
      -> NO_SOLUTION_IF_NO_GOAL_STATE_FOUND

    CONDITIONS
      -> COMPLETENESS_EVIDENCE
  }

  PROCESS COMPLEXITY_REASONING {
    SEARCH_TREE
      -> BRANCHING_FACTOR + DEPTH

    EXPLORED_NODES
      -> TIME_COST

    PRUNING_AND_HEURISTICS
      -> EFFECTIVE_SEARCH_TREE_SIZE

    ACTIVE_RECURSION_DEPTH + STATE_STORAGE
      -> SPACE_COMPLEXITY

    UNPRUNED_WORST_CASE
      -> EXPONENTIAL_OR_COMBINATORIAL_SEARCH_COST_WHERE_APPLICABLE
  }

  RULES {
    IF BACKTRACKING_IS_ASSERTED
    THEN REQUIRE CHOICE_EXTENSION_FAILURE_AND_STATE_RESTORATION_OR_EQUIVALENT_SEARCH_BEHAVIOUR

    IF PARTIAL_STATE_VIOLATES_HARD_CONSTRAINT
    THEN BRANCH_MAY_BE_PRUNED

    IF PRUNING_RULE_IS_USED
    THEN REQUIRE IT_DOES_NOT_REMOVE_REQUIRED_VALID_SOLUTIONS_FOR_COMPLETENESS_CLAIM

    IF STATE_IS_RESTORED
    THEN RESTORE_ALL_MUTATED_STATE_RELEVANT_TO_PARENT_SEARCH_CONTEXT

    IF FIRST_SOLUTION_MODE_IS_USED
    THEN DO_NOT ASSERT ALL_SOLUTIONS_ENUMERATED

    IF HEURISTIC_CHANGES_SEARCH_ORDER_ONLY
    THEN DO_NOT ASSERT IT_CHANGES_SOLUTION_VALIDITY

    IF BRANCH_AND_BOUND_IS_USED
    THEN DISTINGUISH FEASIBILITY_PRUNING_FROM_OBJECTIVE_BOUND_PRUNING

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND BACKTRACKING_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        STATE_SPACE_COMPLETENESS,
        CANDIDATE_GENERATION_COMPLETENESS,
        CONSTRAINT_CERTAINTY,
        STATE_RESTORATION_CERTAINTY,
        PRUNING_SAFETY_EVIDENCE,
        CORRECTNESS_AND_COMPLETENESS_EVIDENCE,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF CANDIDATE_GENERATION_IS_INCOMPLETE
    THEN REDUCE_COMPLETENESS_CONFIDENCE

    IF STATE_RESTORATION_IS_PARTIAL_OR_UNKNOWN
    THEN REDUCE_CORRECTNESS_CONFIDENCE

    IF PRUNING_SAFETY_IS_UNPROVEN
    THEN REDUCE_COMPLETENESS_CONFIDENCE

    IF EXECUTION_TRACE_AND_FORMAL_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        BACKTRACKING_ALGORITHM_IDENTIFIER,
        PROBLEM_DEFINITION,
        STATE_REPRESENTATION,
        CANDIDATE_GENERATION_RULE,
        CONSTRAINT_SET,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B
    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    BACKTRACKING != BRUTE_FORCE_AS_IDENTICAL_CONCEPT
    BACKTRACKING != BRANCH_AND_BOUND_AS_IDENTICAL_CONCEPT
    BACKTRACKING != DYNAMIC_PROGRAMMING
    PARTIAL_SOLUTION != COMPLETE_SOLUTION
    CANDIDATE != CHOICE_AS_IDENTICAL_CONTEXT
    INFEASIBLE_STATE != DEAD_END_IN_ALL_CONTEXTS
    PRUNING != BACKTRACKING
    HEURISTIC != CONSTRAINT
    VARIABLE_ORDERING != VALUE_ORDERING
    STATE_RESTORATION != NEW_STATE_CREATION
    SOUNDNESS != COMPLETENESS
    FIRST_SOLUTION != ALL_SOLUTIONS
    SAFE_PRUNING != ARBITRARY_BRANCH_REMOVAL
    SEARCH_TREE_SIZE != INPUT_SIZE
    WORST_CASE_COMPLEXITY_MAY_REMAIN_EXPONENTIAL_DESPITE_EFFECTIVE_HEURISTICS
    PERFORMANCE_DEPENDS_ON_SEARCH_ORDER_CONSTRAINT_PROPAGATION_AND_INSTANCE_STRUCTURE
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_BACKTRACKING_ALGORITHM_IDENTIFIER
    CHECK_PROBLEM_DEFINITION
    CHECK_INITIAL_STATE
    CHECK_STATE_REPRESENTATION
    CHECK_VARIABLES_AND_DOMAINS
    CHECK_CANDIDATE_GENERATION
    CHECK_CONSTRAINTS
    CHECK_GOAL_TEST
    CHECK_STATE_EXTENSION
    CHECK_STATE_RESTORATION
    CHECK_PRUNING_RULES
    CHECK_HEURISTICS_IF_APPLICABLE
    CHECK_SYMMETRY_BREAKING_IF_APPLICABLE
    CHECK_SOLUTION_MODE
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_COMPLETENESS_EVIDENCE
    CHECK_TERMINATION
    CHECK_COMPLEXITY_CONTEXT
    CHECK_IMPLEMENTATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_BACKTRACKING_ENTITIES
    SEARCH_SPACE_RELATIONS
    STATE_AND_DECISION_RELATIONS
    CANDIDATE_RELATIONS
    CONSTRAINT_RELATIONS
    PARTIAL_SOLUTION_RELATIONS
    STATE_EXTENSION_RELATIONS
    BACKTRACK_AND_RESTORATION_RELATIONS
    PRUNING_RELATIONS
    HEURISTIC_RELATIONS
    SYMMETRY_BREAKING_RELATIONS
    SOLUTION_RELATIONS
    CORRECTNESS_RELATIONS
    COMPLETENESS_RELATIONS
    TERMINATION_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    IMPLEMENTATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON PROBLEM_CONSTRAINT_OR_SEARCH_RULE_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_STATE_AND_SOLUTION_IDENTITIES
      UPDATE_STATE_SPACE
      UPDATE_CANDIDATE_GENERATION
      UPDATE_CONSTRAINTS_AND_GOAL_TESTS
      UPDATE_PRUNING_AND_HEURISTICS
      REASSESS_CORRECTNESS_COMPLETENESS_AND_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_OR_SOLUTION_DATA {
      LINK_EVIDENCE
      UPDATE_SEARCH_TREE
      UPDATE_STATE_TRANSITIONS
      UPDATE_BACKTRACK_AND_RESTORATION_RELATIONS
      UPDATE_SOLUTION_SET
      REASSESS_PRUNING_EFFECTS
      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_BACKTRACKING_ALGORITHM
      BY_SEARCH_PROBLEM
      BY_STATE
      BY_VARIABLE
      BY_CANDIDATE
      BY_CONSTRAINT
      BY_PARTIAL_SOLUTION
      BY_PRUNING_RULE
      BY_HEURISTIC
      BY_SOLUTION
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      GENERATE_CANDIDATES
      ANALYSE_STATE_EXTENSIONS
      CHECK_CONSTRAINTS
      TRACE_RECURSIVE_SEARCH
      TRACE_BACKTRACKING
      ANALYSE_PRUNING
      ANALYSE_HEURISTICS
      ANALYSE_SYMMETRY_BREAKING
      VALIDATE_SOLUTIONS
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLETENESS
      ANALYSE_COMPLEXITY
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_BACKTRACKING_FROM_BRUTE_FORCE_BRANCH_AND_BOUND_AND_DYNAMIC_PROGRAMMING
      DISTINGUISH_PARTIAL_FROM_COMPLETE_SOLUTIONS
      PRESERVE_STATE_CANDIDATE_CONSTRAINT_PRUNING_HEURISTIC_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_SOUNDNESS_FROM_COMPLETENESS
      PRESERVE_STATE_RESTORATION_AND_SEARCH_MODE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_BACKTRACKING_INFERENCE
    }
  }

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

END FLOW