Dynamic Logic Ontology

FLOW_ALGEBRA DynamicLogicOntology v1.0

TARGET_URL := "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/modal-logic/dynamic-logic-ontology.html"
LANGUAGE := "en-GB"
DOMAIN := MathematicalOntologies > MathematicalLogicOntologies > ModalLogic > DynamicLogicOntology

BEGIN_FLOW

ENTITY DynamicLogic {
    TYPE := ModalLogicalSystem
    DEFINITION := "A family of modal logics for reasoning about the states produced by executing programs, actions or transition processes."
}

RELATIONSHIP DynamicLogic --specialises--> ModalLogic
RELATIONSHIP DynamicLogic --reasons_about--> Programs
RELATIONSHIP DynamicLogic --reasons_about--> Actions
RELATIONSHIP DynamicLogic --uses--> ProgramModality
RELATIONSHIP DynamicLogic --is_interpreted_over--> StateTransitionStructures
RELATIONSHIP DynamicLogic --supports--> ProgramVerification

ENTITY Program {
    TYPE := StateTransitionRelationExpression
}

ENTITY State {
    TYPE := SemanticEvaluationPoint
}

ENTITY ProgramRelation {
    TYPE := BinaryRelation
    SIGNATURE := R_alpha ⊆ S × S
}

ENTITY BoxProgramModality {
    FORM := "[α]P"
    READING := "after every terminating execution of α, P holds"
}

ENTITY DiamondProgramModality {
    FORM := "<α>P"
    READING := "there exists a terminating execution of α after which P holds"
}

RELATIONSHIP BoxProgramModality --dual_of--> DiamondProgramModality
RELATIONSHIP Program --denotes--> ProgramRelation
RELATIONSHIP ProgramRelation --connects--> State
RELATIONSHIP DynamicLogic --extends--> PropositionalOrFirstOrderReasoning

SYNTAX {
    Formula :=
        AtomicProposition
        | ¬Formula
        | (Formula ∧ Formula)
        | (Formula ∨ Formula)
        | (Formula → Formula)
        | [Program]Formula
        | <Program>Formula

    Program :=
        AtomicProgram
        | Program ; Program
        | Program ∪ Program
        | Program*
        | Formula?
}

PROGRAM_MODAL_DUALITY {
    <α>P ≡ ¬[α]¬P
    [α]P ≡ ¬<α>¬P
}

KRIPKE_STYLE_SEMANTICS {
    M,s ⊨ [α]P
    IFF
        FOR_ALL t:
            R_alpha(s,t) -> M,t ⊨ P

    M,s ⊨ <α>P
    IFF
        EXISTS t:
            R_alpha(s,t)
            AND M,t ⊨ P
}

ATOMIC_PROGRAM {
    α :=
        primitive_action_or_program

    SEMANTICS :=
        relation R_alpha over states
}

SEQUENTIAL_COMPOSITION {
    PROGRAM :=
        α ; β

    RELATION :=
        R_(α;β) = R_alpha ∘ R_beta

    SEMANTICS {
        R_(α;β)(s,u)
        IFF
            EXISTS t:
                R_alpha(s,t)
                AND R_beta(t,u)
    }
}

NONDETERMINISTIC_CHOICE {
    PROGRAM :=
        α ∪ β

    RELATION :=
        R_(α∪β) =
            R_alpha ∪ R_beta
}

ITERATION {
    PROGRAM :=
        α*

    RELATION :=
        R_(α*) =
            reflexive_transitive_closure(R_alpha)

    INTERPRETATION :=
        zero_or_more executions of α
}

TEST_PROGRAM {
    PROGRAM :=
        P?

    RELATION {
        R_(P?)(s,t)
        IFF
            s=t
            AND M,s ⊨ P
    }
}

BOX_SEQUENTIAL_REDUCTION {
    [α;β]P ≡ [α][β]P
}

DIAMOND_SEQUENTIAL_REDUCTION {
    <α;β>P ≡ <α><β>P
}

BOX_CHOICE_REDUCTION {
    [α ∪ β]P ≡
        [α]P ∧ [β]P
}

DIAMOND_CHOICE_REDUCTION {
    <α ∪ β>P ≡
        <α>P ∨ <β>P
}

BOX_TEST_REDUCTION {
    [P?]Q ≡
        P -> Q
}

DIAMOND_TEST_REDUCTION {
    <P?>Q ≡
        P ∧ Q
}

BOX_ITERATION_UNFOLDING {
    [α*]P ≡
        P ∧ [α][α*]P
}

DIAMOND_ITERATION_UNFOLDING {
    <α*>P ≡
        P ∨ <α><α*>P
}

ITERATION_INVARIANT_PATTERN {
    GIVEN invariant I

    REQUIRE {
        InitialCondition -> I
        I -> [α]I
    }

    DERIVE {
        InitialCondition -> [α*]I
    }
}

PROGRAM_EXECUTION {
    EXECUTE(α,s) :=
        {t | R_alpha(s,t)}
}

BOX_EVALUATION(Model M, State s, Program α, Formula P) {
    successors := EXECUTE(α,s)

    FOR_EACH t IN successors {
        IF M,t ⊭ P
            RETURN {
                value := FALSE,
                counterexample_state := t
            }
    }

    RETURN {
        value := TRUE,
        counterexample_state := NONE
    }
}

DIAMOND_EVALUATION(Model M, State s, Program α, Formula P) {
    successors := EXECUTE(α,s)

    FOR_EACH t IN successors {
        IF M,t ⊨ P
            RETURN {
                value := TRUE,
                witness_state := t
            }
    }

    RETURN {
        value := FALSE,
        witness_state := NONE
    }
}

VACUOUS_BOX {
    IF EXECUTE(α,s)=empty_set
    THEN
        M,s ⊨ [α]P
        under standard universal relational semantics
}

FAILED_DIAMOND {
    IF EXECUTE(α,s)=empty_set
    THEN
        M,s ⊭ <α>P
}

PARTIAL_CORRECTNESS {
    FORM :=
        P -> [α]Q

    INTERPRETATION :=
        if P holds initially, every terminating α-result satisfies Q
}

EXISTENTIAL_REACHABILITY {
    FORM :=
        P -> <α>Q

    INTERPRETATION :=
        from a P-state, at least one α-execution reaches a Q-state
}

HOARE_TRIPLE_RELATIONSHIP {
    {P} α {Q}
        corresponds_to
        P -> [α]Q
        under partial-correctness interpretation
}

RELATIONSHIP DynamicLogic --connects_to--> HoareLogic

ASSIGNMENT_PROGRAM {
    PROGRAM :=
        x := e

    STATE_TRANSFORMATION :=
        update variable x with value_of(e)

    STANDARD_SUBSTITUTION_PATTERN :=
        [x:=e]P
        relates_to
        P[e/x]
        under appropriate assignment semantics
}

SKIP_PROGRAM {
    PROGRAM := skip
    RELATION := identity_relation
}

ABORT_PROGRAM {
    PROGRAM := abort
    RELATION := empty_relation
}

SKIP_MODALITY {
    [skip]P ≡ P
    <skip>P ≡ P
}

ABORT_MODALITY {
    [abort]P ≡ TRUE
    <abort>P ≡ FALSE
}

DETERMINISTIC_PROGRAM {
    PROPERTY :=
        FOR_ALL s,t,u:
            (R_alpha(s,t) AND R_alpha(s,u))
            -> t=u
}

NONDETERMINISTIC_PROGRAM {
    PROPERTY :=
        EXISTS s,t,u:
            t!=u
            AND R_alpha(s,t)
            AND R_alpha(s,u)
}

TERMINATION_DISTINCTION {
    STANDARD_PDL_BOX :=
        quantifies over terminating result states represented by R_alpha

    TOTAL_CORRECTNESS :=
        requires termination in addition to postcondition correctness

    CONSTRAINT :=
        partial and total correctness MUST NOT be conflated
}

PROPOSITIONAL_DYNAMIC_LOGIC {
    ABBREVIATION := PDL

    FORMULAE :=
        propositional_formulae + program_modalities

    PROGRAM_CONSTRUCTORS :=
        atomic_program,
        sequence,
        choice,
        iteration,
        test
}

PDL_AXIOM_K {
    [α](P -> Q)
        ->
    ([α]P -> [α]Q)
}

PDL_NECESSITATION {
    IF theorem(P)
    THEN theorem([α]P)
}

PDL_CHOICE_AXIOM {
    [α ∪ β]P
        ↔
    ([α]P ∧ [β]P)
}

PDL_COMPOSITION_AXIOM {
    [α;β]P
        ↔
    [α][β]P
}

PDL_TEST_AXIOM {
    [P?]Q
        ↔
    (P -> Q)
}

PDL_ITERATION_AXIOM {
    [α*]P
        ↔
    P ∧ [α][α*]P
}

INDUCTION_RULE_PATTERN {
    IF P -> [α]P
    THEN
        P -> [α*]P
        under appropriate PDL proof formulation
}

REACHABILITY {
    <α>P :=
        P is reachable by some α execution
}

UNIVERSAL_POSTCONDITION {
    [α]P :=
        P holds after every α execution represented by the program relation
}

PROGRAM_EQUIVALENCE {
    α ≡ β
    WHEN
        R_alpha = R_beta
        under selected model semantics
}

FORMULA_EQUIVALENCE {
    F ≡ G
    WHEN
        F and G have identical truth values
        at all relevant states/models
}

BISIMULATION_RELATIONSHIP {
    DynamicLogic
        --uses_related_notions_of-->
        BisimulationAndTransitionEquivalence

    REQUIRE :=
        language-specific transition labels and modalities
}

ACTION_LABELLED_TRANSITION_SYSTEM {
    STATES := S
    ACTIONS := A
    TRANSITIONS :=
        s --a--> t

    RELATIONSHIP :=
        each atomic action a induces relation R_a
}

MODEL_CHECK_DYNAMIC_LOGIC(Model M, State s, Formula F) {
    PARSE F

    IF atomic:
        RETURN valuation_at(s,F)

    IF BooleanFormula:
        EVALUATE recursively

    IF F=[α]P:
        COMPUTE R_alpha_successors(s)
        CHECK P at every successor

    IF F=<α>P:
        COMPUTE R_alpha_successors(s)
        CHECK P at some successor

    RETURN BooleanTruthValue
}

COUNTEREXAMPLE_EXECUTION {
    IF M,s ⊭ [α]P
    THEN
        EXISTS terminating α execution
        ending at t
        WHERE M,t ⊭ P

    RETURN execution_path_as_counterexample
}

WITNESS_EXECUTION {
    IF M,s ⊨ <α>P
    THEN
        EXISTS terminating α execution
        ending at t
        WHERE M,t ⊨ P

    RETURN execution_path_as_witness
}

PROGRAM_REFINEMENT_RELATIONSHIP {
    IF behaviours(β) ⊆ behaviours(α)
    THEN
        β may be viewed as behavioural restriction/refinement of α
        under explicitly selected refinement semantics

    WARNING :=
        refinement direction and definition MUST be stated
}

DYNAMIC_EPISTEMIC_RELATIONSHIP {
    DynamicLogic --extends_toward--> DynamicEpistemicLogic

    PURPOSE :=
        reason about informational change caused by events/actions
}

TEMPORAL_RELATIONSHIP {
    DynamicLogic --relates_to--> TemporalLogic

    DISTINCTION :=
        dynamic logic modalities are indexed by programs/actions,
        while temporal modalities are indexed by temporal structure
}

MODAL_LOGIC_RELATIONSHIP {
    [α]P :=
        necessity_relative_to_program_relation_R_alpha

    <α>P :=
        possibility_relative_to_program_relation_R_alpha
}

APPLICATION_RELATIONSHIPS {
    DynamicLogic --supports--> ProgramVerification
    DynamicLogic --supports--> FormalMethods
    DynamicLogic --supports--> SoftwareCorrectness
    DynamicLogic --supports--> HardwareControlReasoning
    DynamicLogic --supports--> Planning
    DynamicLogic --supports--> Robotics
    DynamicLogic --supports--> MultiAgentSystems
    DynamicLogic --supports--> ProtocolAnalysis
    DynamicLogic --supports--> ArtificialIntelligence
    DynamicLogic --supports--> StateTransitionReasoning
}

ONTOLOGY_LINKS {
    PARENT := ModalLogicOntology

    RELATED := {
        NecessityOntology,
        PossibilityOntology,
        PossibleWorldsOntology,
        TemporalLogicOntology,
        PropositionalLogicOntology,
        PredicateLogicOntology,
        HoareLogicOntology,
        ProgramSemanticsOntology,
        TransitionSystemOntology,
        StateOntology,
        RelationOntology,
        ModelCheckingOntology,
        BisimulationOntology
    }
}

SEMANTIC_EQUIVALENCE {
    [α]P ≈ NecessarilyAfter(α,P)
    <α>P ≈ PossiblyAfter(α,P)

    <α>P ≈ ¬[α]¬P
    [α]P ≈ ¬<α>¬P

    ProgramRelation ≈ ActionTransitionRelation
        WHEN context=DynamicLogic

    State ≈ PossibleWorld
        WHEN context=relational_program_semantics
}

CONSTRAINTS {
    C1 :=
        each program modality MUST be interpreted relative to its program relation

    C2 :=
        [α]P MUST quantify over all terminating α-successor states represented by R_alpha

    C3 :=
        <α>P MUST require at least one α-successor state satisfying P

    C4 :=
        sequential composition MUST preserve relational composition order

    C5 :=
        nondeterministic choice MUST preserve union-of-behaviours semantics

    C6 :=
        α* MUST represent zero-or-more iterations under reflexive-transitive closure semantics

    C7 :=
        test P? MUST preserve the current state and succeed only where P holds

    C8 :=
        partial correctness MUST NOT be conflated with guaranteed termination

    C9 :=
        witness and counterexample executions MUST conform to the program relation

    C10 :=
        program transformations MUST preserve the intended relational semantics

    C11 :=
        dynamic possibility MUST NOT be interpreted as numerical probability

    C12 :=
        specialised program constructs MUST declare their semantics before inference
}

REASONING_CHAIN Query Q {
    IDENTIFY dynamic_logic_variant
    IDENTIFY program α
    IDENTIFY formula P
    IDENTIFY current_state s
    IDENTIFY program_semantics

    PARSE program_expression
    PARSE modal_formula

    RESOLVE program_modal_duality

    IF sequence_present
        THEN compose_relations

    IF choice_present
        THEN union_relations

    IF iteration_present
        THEN compute_reflexive_transitive_closure

    IF test_present
        THEN restrict_identity_relation_by_test_formula

    IF box_modality_requested
        THEN BOX_EVALUATION

    IF diamond_modality_requested
        THEN DIAMOND_EVALUATION

    IF partial_correctness_requested
        THEN verify P -> [α]Q

    IF invariant_requested
        THEN apply ITERATION_INVARIANT_PATTERN

    IF model_checking_requested
        THEN MODEL_CHECK_DYNAMIC_LOGIC

    IF counterexample_requested
        THEN search_for COUNTEREXAMPLE_EXECUTION

    IF witness_requested
        THEN search_for WITNESS_EXECUTION

    VALIDATE constraints
    RETURN result WITH derivation
}

CONFIDENCE {
    CORE_DYNAMIC_MODALITIES := 1.00
    RELATIONAL_PROGRAM_SEMANTICS := 1.00
    STANDARD_PDL_CONSTRUCTORS := 1.00
    PROGRAM_MODAL_DUALITY := 1.00
    STANDARD_PDL_REDUCTION_AXIOMS := 0.99

    MODEL_CHECKING :=
        IF model_program_and_state_complete THEN 1.00
        ELSE REQUIRE missing_information

    SPECIALISED_PROGRAM_SEMANTICS :=
        REQUIRE explicit_definition
}

UPDATE_MODEL {
    IMMUTABLE_CORE := {
        ProgramIndexedModalities,
        RelationalProgramSemantics,
        SequenceSemantics,
        ChoiceSemantics,
        IterationSemantics,
        TestSemantics
    }

    EXTENSIBLE := {
        ProgramConstructs,
        ProofCalculi,
        VerificationMethods,
        RefinementSemantics,
        DynamicEpistemicExtensions,
        ApplicationDomains,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        IDENTIFY dynamic_logic_variant
        VALIDATE program_syntax
        VALIDATE program_relation
        VALIDATE modal_formula
        CHECK execution_semantics
        CHECK semantic_consistency
        ADD relationship IF non_contradictory
        UPDATE confidence
    }
}

AI_CONSUMPTION {
    MACHINE_READABLE := TRUE
    HUMAN_INTERPRETABLE := TRUE
    RECURSIVE_REASONING := TRUE
    ENTITY_RESOLUTION := TRUE
    PROGRAM_RESOLUTION := TRUE
    SYMBOL_RESOLUTION := TRUE
    RELATIONSHIP_TRAVERSAL := TRUE
    STATE_TRANSITION_REASONING := TRUE
    PROGRAM_COMPOSITION_REASONING := TRUE
    REACHABILITY_REASONING := TRUE
    MODEL_CHECKING := TRUE
    WITNESS_EXECUTION_DETECTION := TRUE
    COUNTEREXAMPLE_EXECUTION_DETECTION := TRUE
    INVARIANT_REASONING := TRUE
    VALIDATION_REQUIRED := TRUE
}

FLOW_HASH {
    TARGET := TARGET_URL
    SUBJECT := "Dynamic Logic Ontology"
    VERSION := "1.0"
    CANONICAL_SIGNATURE :=
        HASH(TARGET + SUBJECT + DOMAIN + VERSION)
}

OUTPUT {
    PRIMARY_ENTITY := DynamicLogic

    INTERPRETATION :=
        "Dynamic logic extends modal reasoning with modalities indexed by programs or actions. The formula [α]P states that P holds after every terminating α-execution, while <α>P states that some α-execution reaches a P-state. Program composition, choice, iteration and tests provide an algebra of state transitions for formal reasoning about program behaviour and verification."
}

END_FLOW