Temporal Logic Ontology

FLOW_ALGEBRA TemporalLogicOntology v1.0

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

BEGIN_FLOW

ENTITY TemporalLogic {
    TYPE := ModalLogicalSystem
    DEFINITION := "A family of formal logics for expressing and reasoning about propositions whose truth may vary across time or ordered states."
}

RELATIONSHIP TemporalLogic --specialises--> ModalLogic
RELATIONSHIP TemporalLogic --reasons_about--> Time
RELATIONSHIP TemporalLogic --uses--> TemporalOperator
RELATIONSHIP TemporalLogic --is_interpreted_over--> TemporalStructure
RELATIONSHIP TemporalLogic --supports--> TemporalVerification

ENTITY TemporalStructure {
    TYPE := OrderedOrTransitionStructure
    COMPONENTS := {StatesOrTimes, TemporalRelation}
}

ENTITY TemporalState {
    TYPE := EvaluationPoint
}

ENTITY TemporalRelation {
    TYPE := BinaryRelation
    INTERPRETATION := temporal_successor_or_reachability
}

TEMPORAL_LANGUAGE_FAMILIES {
    LTL := LinearTemporalLogic
    CTL := ComputationTreeLogic
    CTL_STAR := ComputationTreeLogicStar
    PAST_TEMPORAL_LOGIC := TemporalLogicWithPastOperators
}

ENTITY NextOperator {
    SYMBOL := "X"
    READING := "next"
}

ENTITY EventuallyOperator {
    SYMBOL := "F"
    READING := "eventually"
}

ENTITY GloballyOperator {
    SYMBOL := "G"
    READING := "always/globally"
}

ENTITY UntilOperator {
    SYMBOL := "U"
    READING := "until"
}

ENTITY ReleaseOperator {
    SYMBOL := "R"
    READING := "release"
}

LTL_SYNTAX {
    Formula :=
        AtomicProposition
        | ¬Formula
        | (Formula ∧ Formula)
        | (Formula ∨ Formula)
        | (Formula → Formula)
        | X Formula
        | F Formula
        | G Formula
        | (Formula U Formula)
        | (Formula R Formula)
}

ENTITY InfiniteTrace {
    FORM := s0,s1,s2,...
    REQUIRE :=
        each adjacent state follows the transition semantics
}

TRACE_POSITION {
    π,i := trace π evaluated at position i
}

LTL_ATOMIC_SEMANTICS {
    π,i ⊨ p
    IFF
        p is true at state π[i]
}

NEXT_SEMANTICS {
    π,i ⊨ X P
    IFF
        π,i+1 ⊨ P
}

EVENTUALLY_SEMANTICS {
    π,i ⊨ F P
    IFF
        EXISTS j >= i:
            π,j ⊨ P
}

GLOBALLY_SEMANTICS {
    π,i ⊨ G P
    IFF
        FOR_ALL j >= i:
            π,j ⊨ P
}

UNTIL_SEMANTICS {
    π,i ⊨ P U Q
    IFF
        EXISTS j >= i:
            π,j ⊨ Q
            AND
            FOR_ALL k:
                i <= k < j
                -> π,k ⊨ P
}

RELEASE_SEMANTICS {
    P R Q
    := dual_of_until

    EQUIVALENCE :=
        P R Q ≡ ¬(¬P U ¬Q)
}

TEMPORAL_DUALITIES {
    F P ≡ ¬G¬P
    G P ≡ ¬F¬P
    P R Q ≡ ¬(¬P U ¬Q)
}

DERIVED_LTL_FORMS {
    F P ≡ TRUE U P
    G P ≡ FALSE R P
}

EVENTUALITY_WITNESS {
    IF π,i ⊨ F P
    THEN
        EXISTS j >= i:
            π,j ⊨ P

    j := temporal_witness_position
}

GLOBAL_COUNTEREXAMPLE {
    IF π,i ⊭ G P
    THEN
        EXISTS j >= i:
            π,j ⊭ P

    j := temporal_counterexample_position
}

UNTIL_WITNESS {
    IF π,i ⊨ P U Q
    THEN
        EXISTS j >= i:
            Q holds_at j
            AND P holds_at every position i..j-1
}

MODEL_CHECK_LTL_TRACE(Trace π, Position i, Formula Fml) {
    IF atomic(Fml):
        RETURN truth_at(π[i],Fml)

    IF Fml = ¬P:
        RETURN NOT MODEL_CHECK_LTL_TRACE(π,i,P)

    IF Fml = P ∧ Q:
        RETURN MODEL_CHECK_LTL_TRACE(π,i,P)
               AND MODEL_CHECK_LTL_TRACE(π,i,Q)

    IF Fml = X P:
        RETURN MODEL_CHECK_LTL_TRACE(π,i+1,P)

    IF Fml = F P:
        SEARCH j >= i
        RETURN TRUE IF P holds_at_some_j

    IF Fml = G P:
        CHECK all j >= i
        RETURN FALSE IF any_counterexample_found
        RETURN TRUE otherwise

    IF Fml = P U Q:
        SEARCH witness j >= i WHERE Q
        REQUIRE P at all preceding positions from i to j-1

    IF Fml = P R Q:
        EVALUATE dual_or_direct_release_semantics
}

SAFETY_PROPERTY {
    INTUITION :=
        "Something bad never happens."

    COMMON_FORM :=
        G ¬Bad

    VIOLATION :=
        finite_counterexample_prefix_may_demonstrate_failure
}

LIVENESS_PROPERTY {
    INTUITION :=
        "Something good eventually happens."

    COMMON_FORM :=
        F Good
}

RESPONSE_PROPERTY {
    FORM :=
        G(Request -> F Response)

    INTERPRETATION :=
        every request is eventually followed by a response
}

INVARIANT_PROPERTY {
    FORM :=
        G P

    INTERPRETATION :=
        P holds at every future trace position
}

RECURRENCE_PROPERTY {
    FORM :=
        G F P

    INTERPRETATION :=
        P occurs infinitely often along an infinite trace
}

PERSISTENCE_PROPERTY {
    FORM :=
        F G P

    INTERPRETATION :=
        eventually P becomes permanently true
}

ORDER_SENSITIVITY {
    P THEN Q
        is not generally equivalent to
    Q THEN P

    TEMPORAL_POSITION :=
        semantically significant
}

LINEAR_TIME_ASSUMPTION {
    LTL :=
        evaluates formulae along individual linear traces
}

ENTITY BranchingTimeStructure {
    TYPE := TransitionSystemOrKripkeStructure
    PATHS := multiple_future_computations
}

CTL_PATH_QUANTIFIERS {
    A := "for all paths"
    E := "there exists a path"
}

CTL_TEMPORAL_OPERATORS {
    X := next
    F := eventually
    G := globally
    U := until
}

CTL_EXAMPLES {
    AX P :=
        P holds in every immediate successor state

    EX P :=
        P holds in at least one immediate successor state

    AF P :=
        along every path, P eventually holds

    EF P :=
        along at least one path, P eventually holds

    AG P :=
        along every path, P always holds

    EG P :=
        along at least one path, P always holds
}

CTL_SEMANTIC_PATTERN {
    PATH_QUANTIFIER + TEMPORAL_OPERATOR

    REQUIRE :=
        CTL state formula syntax rules
}

CTL_STAR {
    DEFINITION :=
        branching-time temporal logic allowing more flexible nesting of path quantifiers and temporal operators than CTL
}

LTL_VS_CTL {
    LTL :=
        trace-oriented linear-time semantics

    CTL :=
        branching-time state semantics with explicit path quantifiers

    CONSTRAINT :=
        formulas MUST be interpreted according to their own language semantics
}

FINITE_TRACE_NOTE {
    STANDARD_LTL :=
        commonly defined over infinite traces

    FINITE_TRACE_VARIANTS :=
        require explicit finite-trace semantics

    CONSTRAINT :=
        end-of-trace behaviour for X and other operators MUST be defined when finite traces are used
}

PAST_TEMPORAL_OPERATORS {
    Y := Previous
    O := Once
    H := Historically
    S := Since
}

PREVIOUS_SEMANTICS {
    π,i ⊨ Y P
    IFF
        i > 0
        AND π,i-1 ⊨ P
}

ONCE_SEMANTICS {
    π,i ⊨ O P
    IFF
        EXISTS j <= i:
            π,j ⊨ P
}

HISTORICALLY_SEMANTICS {
    π,i ⊨ H P
    IFF
        FOR_ALL j <= i:
            π,j ⊨ P
}

SINCE_SEMANTICS {
    π,i ⊨ P S Q
    IFF
        EXISTS j <= i:
            π,j ⊨ Q
            AND P holds_between j+1 and i
}

TIME_MODELS {
    DISCRETE_TIME :=
        positions indexed by integers_or_natural_numbers

    DENSE_TIME :=
        positions may range over dense ordered domains

    CONTINUOUS_TIME :=
        specialised semantics may use real-valued time

    REQUIRE :=
        temporal domain MUST be identified for metric or quantitative claims
}

METRIC_TEMPORAL_LOGIC_RELATIONSHIP {
    TemporalLogic --extends_to--> MetricTemporalLogic

    ADD :=
        time-bounded temporal operators

    EXAMPLES {
        F_[a,b] P
        G_[a,b] P
    }
}

REAL_TIME_LOGIC_RELATIONSHIP {
    TemporalLogic --extends_to--> RealTimeTemporalLogic
}

TRANSITION_SYSTEM {
    COMPONENTS := {
        States,
        InitialStates,
        TransitionRelation,
        LabellingFunction
    }
}

RELATIONSHIP TemporalLogic --can_be_checked_over--> TransitionSystem

LABELLING_FUNCTION {
    L(s) :=
        set_of_atomic_propositions_true_at_state_s
}

TRACE_GENERATION(TransitionSystem T) {
    START at initial_state
    FOLLOW transition_relation
    PRODUCE sequence_of_states
}

MODEL_CHECKING {
    INPUT := {
        TemporalFormula,
        TransitionSystem
    }

    OUTPUT :=
        formula_satisfied_or_counterexample_or_witness
}

LTL_MODEL_CHECKING_ABSTRACTION {
    CONVERT negation_of_property_to_automaton
    COMPOSE with system_behaviour
    SEARCH for accepting_counterexample_cycle
    RETURN validity_or_counterexample
}

CTL_MODEL_CHECKING_ABSTRACTION {
    COMPUTE satisfying_state_sets bottom_up
    USING fixed_point_style operations
    RETURN initial_state_satisfaction
}

FIXED_POINT_RELATIONSHIP {
    TemporalOperators --relate_to--> LeastAndGreatestFixedPoints

    EXAMPLES {
        EF := least_fixed_point_style_reachability
        EG := greatest_fixed_point_style_invariance_path
    }
}

FAIRNESS {
    TYPE := PathConstraint

    PURPOSE :=
        restrict attention to computations satisfying fairness assumptions

    WARNING :=
        fairness assumptions MUST be explicit because they change temporal validity
}

STUTTERING_RELATIONSHIP {
    LTL_without_next
        has important stuttering-invariance properties

    REQUIRE :=
        precise language and equivalence assumptions
}

TEMPORAL_ENTAILMENT {
    Γ ⊨_T F
    IFF
        every temporal model/trace satisfying Γ
        also satisfies F
}

TEMPORAL_SATISFIABILITY {
    SATISFIABLE(F)
    IFF
        EXISTS temporal_model_or_trace satisfying F
}

TEMPORAL_VALIDITY {
    VALID(F)
    IFF
        F holds in every model/trace of the specified temporal semantics
}

COUNTEREXAMPLE_TRACE {
    IF system violates temporal_property P
    THEN
        RETURN trace_or_path demonstrating violation
        WHEN supported by property/model-checking semantics
}

WITNESS_TRACE {
    IF existential_temporal_property holds
    THEN
        RETURN trace_or_path demonstrating satisfaction
        WHEN supported by semantics
}

APPLICATION_RELATIONSHIPS {
    TemporalLogic --supports--> FormalVerification
    TemporalLogic --supports--> ModelChecking
    TemporalLogic --supports--> ReactiveSystems
    TemporalLogic --supports--> ConcurrentSystems
    TemporalLogic --supports--> ProtocolVerification
    TemporalLogic --supports--> HardwareVerification
    TemporalLogic --supports--> SoftwareVerification
    TemporalLogic --supports--> Planning
    TemporalLogic --supports--> RuntimeVerification
    TemporalLogic --supports--> ArtificialIntelligence
}

ONTOLOGY_LINKS {
    PARENT := ModalLogicOntology

    RELATED := {
        NecessityOntology,
        PossibilityOntology,
        PossibleWorldsOntology,
        KripkeFrameOntology,
        TransitionSystemOntology,
        StateOntology,
        RelationOntology,
        LinearTemporalLogicOntology,
        ComputationTreeLogicOntology,
        ModelCheckingOntology,
        FixedPointOntology,
        AutomataTheoryOntology
    }
}

SEMANTIC_EQUIVALENCE {
    F P ≈ Eventually(P)
    G P ≈ Globally(P)
    X P ≈ Next(P)

    F P ≈ ¬G¬P
    G P ≈ ¬F¬P

    TemporalState ≈ PossibleWorld
        WHEN context=Kripke_style_temporal_semantics

    TemporalRelation ≈ TransitionRelation
        WHEN context=state_transition_semantics
}

CONSTRAINTS {
    C1 :=
        temporal logic family MUST be identified when syntax or semantics differ

    C2 :=
        LTL formulae MUST be evaluated according to linear-trace semantics

    C3 :=
        CTL formulae MUST preserve explicit path-quantifier semantics

    C4 :=
        F MUST mean eventual truth at some permitted future position

    C5 :=
        G MUST mean truth at all permitted future positions

    C6 :=
        P U Q MUST require a Q witness and P at every preceding required position

    C7 :=
        finite-trace semantics MUST be explicit when traces are finite

    C8 :=
        possibility-style temporal operators MUST NOT be interpreted as numerical probability

    C9 :=
        fairness assumptions MUST be explicit

    C10 :=
        metric temporal claims MUST identify the temporal domain and interval semantics

    C11 :=
        counterexample and witness paths MUST conform to the transition structure

    C12 :=
        transformations MUST preserve temporal semantics under the selected logic
}

REASONING_CHAIN Query Q {
    IDENTIFY temporal_logic_family
    IDENTIFY formula
    IDENTIFY temporal_model
    IDENTIFY time_or_state_domain

    PARSE temporal_formula
    IDENTIFY temporal_operators
    RESOLVE temporal_dualities

    IF LTL_context {
        IDENTIFY trace π
        IDENTIFY position i
        EVALUATE trace_semantics
    }

    IF CTL_context {
        IDENTIFY state s
        IDENTIFY path_quantifiers
        IDENTIFY transition_structure
        EVALUATE branching_time_semantics
    }

    IF eventually_requested
        THEN search_for temporal_witness

    IF globally_requested
        THEN search_for temporal_counterexample

    IF until_requested
        THEN search_for Q_witness
        AND verify P_on_required_prefix

    IF safety_property
        THEN search_for bad_state_counterexample

    IF liveness_property
        THEN search_for eventuality_witness_or_nonprogress_behaviour

    IF model_checking_requested
        THEN execute logic_appropriate_model_check

    IF metric_context
        THEN identify time_bounds_and_domain

    VALIDATE constraints
    RETURN result WITH derivation
}

CONFIDENCE {
    CORE_TEMPORAL_OPERATORS := 1.00
    STANDARD_LTL_SEMANTICS := 1.00
    STANDARD_CTL_OPERATOR_MEANINGS := 0.99
    TEMPORAL_DUALITIES := 1.00

    MODEL_CHECKING :=
        IF formula_and_transition_system_complete THEN 1.00
        ELSE REQUIRE missing_information

    FINITE_TRACE_OR_METRIC_SEMANTICS :=
        REQUIRE explicit_variant
}

UPDATE_MODEL {
    IMMUTABLE_CORE := {
        TemporalEvaluation,
        NextSemantics,
        EventuallySemantics,
        GloballySemantics,
        UntilSemantics
    }

    EXTENSIBLE := {
        TemporalLogicFamilies,
        PastOperators,
        MetricOperators,
        FairnessConstraints,
        ModelCheckingMethods,
        ApplicationDomains,
        RelatedOntologies
    }

    ON_NEW_KNOWLEDGE {
        IDENTIFY temporal_logic_variant
        VALIDATE syntax
        VALIDATE temporal_domain
        VALIDATE transition_structure
        CHECK operator_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
    SYMBOL_RESOLUTION := TRUE
    RELATIONSHIP_TRAVERSAL := TRUE
    TEMPORAL_REASONING := TRUE
    TRACE_REASONING := TRUE
    BRANCHING_TIME_REASONING := TRUE
    WITNESS_TRACE_DETECTION := TRUE
    COUNTEREXAMPLE_TRACE_DETECTION := TRUE
    MODEL_CHECKING := TRUE
    VALIDATION_REQUIRED := TRUE
}

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

OUTPUT {
    PRIMARY_ENTITY := TemporalLogic

    INTERPRETATION :=
        "Temporal logic extends modal reasoning to propositions whose truth changes across ordered times, traces or transition-system states. Operators such as next, eventually, globally and until express temporal relationships, while linear and branching-time systems provide distinct semantics for reasoning about future behaviour, verification, witnesses and counterexamples."
}

END_FLOW