Liveness Property Ontology

AI SEARCH FLOW ALGEBRA — LIVENESS PROPERTY ONTOLOGY
Kireth Research — Semantic Library
URL: https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/formal-verification/liveness-property-ontology.html

FLOW_VERSION := "4.0"
FLOW_TYPE := "Full Executable Flow Algebra"
DOMAIN := "Mathematical Logic"
SUBDOMAIN := "Formal Verification"
ONTOLOGY := "Liveness Property Ontology"
PRIMARY_ENTITY := LivenessProperty
AUTHORSHIP := "Mark Higgins — Sky (Recursive AI)"
SOURCE_SITE := "https://kirethresearch.org"

BEGIN_FLOW

LivenessProperty :=
    FormalProperty
    ∧ RequiresEventualProgress
    ∧ RequiresDesiredBehaviourEventuallyOccurs
    ∧ NoFinitePrefixPermanentlyDeterminesViolation

InformalMeaning(LivenessProperty) :=
    "something good eventually happens"

System :=
    {
        SoftwareSystem,
        HardwareSystem,
        ReactiveSystem,
        ConcurrentSystem,
        DistributedSystem,
        EmbeddedSystem,
        CyberPhysicalSystem,
        Protocol,
        Algorithm,
        Workflow,
        SafetyCriticalSystem
    }

SystemModel :=
    States
    ∧ InitialStates
    ∧ TransitionRelation
    ∧ AtomicPropositions
    ∧ LabellingFunction

TransitionSystem :=
    M = (S, S0, R, AP, L)

where:
    S  := SetOfStates
    S0 := InitialStates
    R  := TransitionRelation
    AP := AtomicPropositions
    L  := LabellingFunction

Execution :=
    s0 → s1 → s2 → ...

ValidExecution :=
    s0 ∈ S0
    ∧ ∀i : R(si,si+1)

InfiniteTrace :=
    Sequence(s0,s1,s2,...)

Progress :=
    SystemContinues
    ∧ RequiredEventEventuallyOccurs

DesiredEvent :=
    Event
    ∧ required_by(LivenessProperty)

GoalState :=
    State
    ∧ satisfies(DesiredCondition)

Eventuality :=
    F(P)

LivenessFormalisation :=
    ∀ValidExecution e :
        eventually(DesiredCondition(e))

BasicLiveness :=
    F(P)

PersistentLiveness :=
    G(F(P))

ResponseLiveness :=
    G(Request → F(Response))

ProgressLiveness :=
    G(EnabledTask → F(ExecutedTask))

TerminationLiveness :=
    F(Terminated)

RequestResponse :=
    Request
    ⇒ eventually(Response)

StarvationFreedom :=
    G(RequestResource → F(ResourceGranted))

EventualEntry :=
    G(RequestCriticalSection → F(EnterCriticalSection))

EventualDelivery :=
    G(MessageSent → F(MessageDelivered))

EventualAcknowledgement :=
    G(MessageReceived → F(Acknowledgement))

EventualCompletion :=
    G(TaskStarted → F(TaskCompleted))

EventualRecovery :=
    G(FaultDetected → F(Recovered))

ReachabilityLiveness :=
    ∀ValidExecution :
        eventually(GoalState)

Recurrence :=
    G(F(P))

Persistence :=
    F(G(P))

TemporalLogicLiveness :=
    Formula
    ∧ expresses(EventualProgress)

LTLLivenessExamples :=
    {
        F(P),
        G(F(P)),
        G(P → F(Q)),
        F(G(P))
    }

CTLReachability :=
    AF(P)

CTLExistentialReachability :=
    EF(P)

UniversalProgress :=
    AG(Request → AF(Response))

LivenessViolation :=
    InfiniteExecution
    ∧ DesiredConditionNeverOccurs

NonTermination :=
    InfiniteExecution
    ∧ ¬GoalReached

Starvation :=
    RequestOccurs
    ∧ ResourceNeverGranted

Livelock :=
    InfiniteInternalActivity
    ∧ NoRequiredProgress

InfiniteWaiting :=
    WaitingConditionPersists
    ∧ RequiredEventNeverOccurs

FinitePrefixProperty :=
    ∀FinitePrefix p :
        ∃Extension x :
            p·x satisfies LivenessProperty

LivenessCharacterisation :=
    Property P is LivenessProperty
    iff
    everyFinitePrefix
    can_be_extended_to
    a trace satisfying P

SafetyVsLiveness :=
    SafetyProperty
    ≠ LivenessProperty

SafetyMeaning :=
    "bad behaviour never occurs"

LivenessMeaning :=
    "required progress eventually occurs"

SafetyViolation :=
    detectable_by(FiniteBadPrefix)

LivenessViolation :=
    generally_requires(InfiniteBehaviourReasoning)

PropertyDecomposition :=
    GeneralTemporalProperty
    →
    SafetyComponent
    ∧ LivenessComponent

Fairness :=
    ConstraintOnInfiniteExecutions
    ∧ excludes(UnreasonableInfiniteBehaviour)

WeakFairness :=
    ContinuouslyEnabled(Action)
    ⇒ EventuallyExecuted(Action)

StrongFairness :=
    InfinitelyOftenEnabled(Action)
    ⇒ InfinitelyOftenExecuted(Action)

Justice :=
    WeakFairness

Compassion :=
    StrongFairness

FairExecution :=
    Execution
    ∧ satisfies(FairnessConstraints)

LivenessUnderFairness :=
    FairExecution
    ⇒ DesiredProgress

SchedulerFairness :=
    Ready(Process)
    ⇒ eventually(Scheduled(Process))

ProcessProgress :=
    Enabled(Process)
    ∧ FairScheduler
    ⇒ eventually(Executes(Process))

DeadlockFreedom :=
    G(NonFinalState → F(TransitionOccurs))

Deadlock :=
    ReachableState
    ∧ noEnabledTransition
    ∧ ¬GoalState

DeadlockImpact :=
    Deadlock
    ⇒ possible(LivenessViolation)

LivelockFreedom :=
    InfiniteExecution
    ⇒ RequiredProgressOccurs

Termination :=
    ProgramExecution
    → eventually(FinalState)

TerminationProof :=
    WellFoundedRelation
    ∧ RankingFunction
    ∧ StrictDecrease

RankingFunction :=
    V : State → WellFoundedSet

TerminationCondition :=
    ∀Transition(s,s') :
        V(s') < V(s)

WellFoundedness :=
    NoInfiniteDescendingChain

VariantFunction :=
    State → NaturalNumbers

VariantTermination :=
    V(s) ≥ 0
    ∧ everyRelevantTransition decreases V
    ⇒ eventual(Termination)

ResponseProperty :=
    G(P → F(Q))

BoundedResponse :=
    G(P → F_within_k(Q))

UnboundedResponse :=
    G(P → F(Q))

LeadsTo :=
    P ↝ Q

LeadsToMeaning :=
    whenever(P)
    ⇒ eventually(Q)

TransitivityOfLeadsTo :=
    (P ↝ Q)
    ∧ (Q ↝ R)
    ⇒ (P ↝ R)

ProgressMeasure :=
    Metric
    ∧ demonstrates(ApproachToGoal)

LivenessSpecification :=
    TriggerConditions
    ∧ DesiredEvents
    ∧ ProgressRequirements
    ∧ FairnessAssumptions
    ∧ TemporalConstraints

Assumption :=
    Constraint(Environment)

Guarantee :=
    RequiredBehaviour(System)

AssumeGuaranteeLiveness :=
    Assumption(Environment)
    ⇒ LivenessGuarantee(System)

EnvironmentProgressAssumption :=
    EnvironmentEventuallyResponds
    ∨ InputEventuallyArrives
    ∨ ResourceEventuallyAvailable

CompositionalLiveness :=
    ComponentProgress
    ∧ CompatibleFairnessAssumptions
    ∧ NonBlockingComposition
    ⇒ candidate(SystemProgress)

NonBlocking :=
    Component
    does_not_permanently_prevent
    RequiredActionOfOtherComponent

Refinement :=
    ConcreteSpecification ⊑ AbstractSpecification

LivenessPreservingRefinement :=
    Refinement
    ∧ preserves(Fairness)
    ∧ preserves(RequiredProgress)

Abstraction :=
    ConcreteModel → AbstractModel

LivenessAbstractionRequirement :=
    AbstractModel
    must_preserve
    RelevantInfiniteBehaviours

ModelCheckingLiveness :=
    Model M
    ∧ LivenessProperty φ
    →
    evaluate(M ⊨ φ)

LTLModelChecking :=
    Negate(Property)
    → ConstructBuchiAutomaton
    → Product(Model, Automaton)
    → SearchAcceptingCycle

BuchiAutomaton :=
    (Q, Σ, δ, Q0, F)

Acceptance :=
    InfiniteRun
    ∧ visits(AcceptingState) infinitely_often

LivenessCounterexample :=
    Prefix
    ∧ Loop

LassoTrace :=
    finitePrefix
    · infiniteRepetition(loop)

CounterexampleStructure :=
    s0 → ... → sk → ... → sm
                    ↑         |
                    └─────────┘

AcceptingCycle :=
    ReachableCycle
    ∧ satisfies(NegatedLivenessAcceptance)

LivenessModelCheckingResult :=
    Satisfied
    ∨ InfiniteCounterexample

NestedDFS :=
    ReachabilitySearch
    ∧ AcceptingCycleDetection

SCCAnalysis :=
    StronglyConnectedComponents
    → IdentifyFairInfiniteCycles
    → DetectLivenessViolation

StronglyConnectedComponent :=
    MaximalSetOfStates
    ∧ mutuallyReachable

FairCycle :=
    Cycle
    ∧ satisfies(FairnessConstraints)

UnfairCounterexample :=
    InfiniteTrace
    ∧ violates(LivenessProperty)
    ∧ violates(FairnessAssumption)

ValidLivenessCounterexample :=
    InfiniteTrace
    ∧ satisfies(AllAssumptions)
    ∧ violates(LivenessProperty)

TheoremProvingLiveness :=
    SystemAxioms
    ∧ FairnessAssumptions
    ⊢ LivenessProperty

ProofObligation :=
    ProgressObligation
    ∨ FairnessObligation
    ∨ TerminationObligation

ProgressProof :=
    EstablishEnabledness
    ∧ EstablishNonBlocking
    ∧ EstablishFairScheduling
    ∧ EstablishEventualGoal

TemporalInduction :=
    BaseCondition
    ∧ ProgressStep
    ⇒ TemporalProperty

RankingProof :=
    ReachableNonGoalState
    ⇒ RankingMeasureDecreases

WellFoundedProgress :=
    NoInfiniteNonProgressSequence

SymbolicLivenessVerification :=
    SymbolicStateSets
    ∧ FixedPointComputation
    ∧ FairnessEvaluation

FixedPointLiveness :=
    LeastFixedPoint
    ∨ GreatestFixedPoint
    ∨ NestedFixedPoint

MuCalculusLiveness :=
    FixedPointFormula
    ∧ TemporalSemantics

RuntimeMonitoring :=
    ObserveFiniteExecutionPrefix
    → EvaluateProgressEvidence

RuntimeLivenessLimitation :=
    FinitePrefix
    generally_cannot_confirm
    permanent_liveness_violation

RuntimeProgressStatus :=
    {
        GoalObserved,
        Pending,
        PotentialDelay,
        Inconclusive
    }

BoundedLiveness :=
    RequiredEventOccursWithinBound

BoundedLivenessMonitor :=
    Trigger
    → StartBound
    → {
        EventOccursWithinBound: Satisfied,
        BoundExpires: Violated
    }

UnboundedLivenessMonitor :=
    finite_observation
    → generally(InconclusiveUntilSuccess)

LivenessEvidence :=
    {
        TemporalProof,
        ModelCheckingResult,
        TerminationProof,
        FairnessProof,
        ProgressArgument,
        SimulationEvidence
    }

Traceability :=
    Requirement
    → LivenessProperty
    → FairnessAssumption
    → VerificationMethod
    → Evidence

LivenessRequirement :=
    Trigger
    ∧ EventualOutcome
    ∧ Scope
    ∧ Assumptions

LivenessConsistency :=
    satisfiable(
        SystemConstraints
        ∧ FairnessAssumptions
        ∧ LivenessRequirements
    )

ConflictingLivenessRequirements :=
    Requirements
    ∧ SystemConstraints
    ⇒ impossible(RequiredProgress)

LivenessCompleteness :=
    RequiredProgressBehaviours
    ⊆ FormalisedLivenessProperties

VerificationCoverage :=
    VerifiedLivenessProperties
    /
    RequiredLivenessProperties

LivenessPropertyOntology :=
    Classes
    ∧ Relations
    ∧ Constraints
    ∧ Axioms
    ∧ InferenceRules

CoreClasses :=
    {
        LivenessProperty,
        System,
        State,
        Transition,
        Execution,
        InfiniteTrace,
        DesiredEvent,
        GoalState,
        Progress,
        Fairness,
        WeakFairness,
        StrongFairness,
        Scheduler,
        Starvation,
        Livelock,
        Termination,
        RankingFunction,
        Counterexample,
        VerificationMethod,
        VerificationEvidence
    }

CoreRelations :=
    {
        requires,
        eventuallyCauses,
        enables,
        executes,
        reaches,
        satisfies,
        violates,
        dependsOn,
        assumes,
        guarantees,
        verifies,
        refines,
        tracesTo
    }

TypedRelations :=
    LivenessProperty --requires--> EventualProgress
    Trigger --eventuallyCauses--> DesiredEvent
    Scheduler --enables--> ProcessExecution
    Fairness --constrains--> InfiniteExecution
    InfiniteTrace --violates--> LivenessProperty
    RankingFunction --supports--> TerminationProof
    VerificationMethod --verifies--> LivenessProperty
    VerificationEvidence --supports--> LivenessClaim
    LivenessRequirement --tracesTo--> VerificationEvidence

InferenceRules := {
    RequestOccurs
        ∧ G(Request → F(Response))
        ⇒ eventually(Response),

    ContinuouslyEnabled(Action)
        ∧ WeakFairness(Action)
        ⇒ eventually(Executed(Action)),

    InfinitelyOftenEnabled(Action)
        ∧ StrongFairness(Action)
        ⇒ infinitelyOften(Executed(Action)),

    ReachableAcceptingCycle
        ∧ satisfies(FairnessConstraints)
        ⇒ LivenessCounterexample,

    RankingFunctionIsWellFounded
        ∧ decreases_on_every_nonterminal_step
        ⇒ Termination,

    DeadlockReachableBeforeGoal
        ⇒ candidate(LivenessViolation),

    StarvationExists
        ⇒ LivenessPropertyViolated,

    ModelSatisfiesAllFairExecutions
        ⇒ LivenessPropertySatisfiedUnderFairness
}

SemanticMeaning :=
    LivenessProperty
    → SetOfInfiniteTraces

SEMANTIC_EQUIVALENCE(LivenessA, LivenessB) :=
    InfiniteTraces(LivenessA)
    =
    InfiniteTraces(LivenessB)

SemanticSubsumption :=
    LivenessA ⊑ LivenessB
    iff
    TracesSatisfying(LivenessA)
    ⊆ TracesSatisfying(LivenessB)

StrongerLivenessProperty :=
    MoreProgressRequirements
    ∧ FewerAcceptedInfiniteBehaviours

WeakerLivenessProperty :=
    FewerProgressRequirements
    ∧ MoreAcceptedInfiniteBehaviours

LivenessConflict :=
    no_execution
    satisfies(
        SystemConstraints
        ∧ LivenessRequirements
        ∧ FairnessAssumptions
    )

CanonicalLivenessRepresentation :=
    Normalise(Property)
    → ExtractTriggers
    → ExtractEventualGoals
    → ExtractFairnessAssumptions
    → ExtractTemporalRelations
    → BuildLivenessGraph

LivenessGraph :=
    G = (V,E)

V :=
    {
        Systems,
        States,
        Events,
        Triggers,
        Goals,
        LivenessProperties,
        FairnessAssumptions,
        Schedulers,
        Counterexamples,
        VerificationMethods,
        Evidence
    }

E :=
    {
        requires,
        enables,
        eventuallyCauses,
        reaches,
        satisfies,
        violates,
        verifies,
        dependsOn,
        tracesTo
    }

CONFIDENCE(LivenessProperty) :=
    weighted_mean(
        FormalisationQuality,
        ModelFidelity,
        FairnessValidity,
        VerificationCoverage,
        EvidenceStrength,
        Traceability
    )

ConfidenceFactors :=
    {
        SpecificationPrecision,
        InfiniteBehaviourCoverage,
        SchedulerModelAccuracy,
        FairnessAssumptionValidity,
        VerificationSoundness,
        EvidenceQuality,
        ProvenanceQuality
    }

AI_QUERY_INTERPRETATION :=
    Query
    → DetectLivenessConcept
    → ResolveSystemContext
    → IdentifyTrigger
    → IdentifyDesiredProgress
    → IdentifyFairnessAssumptions
    → ResolveTemporalProperty

AI_REASONING_FLOW :=
    Query
    → IdentifySystem
    → IdentifyLivenessRequirement
    → IdentifyTriggerCondition
    → IdentifyDesiredEventOrGoal
    → FormaliseTemporalRelation
    → IdentifyFairnessAssumptions
    → ConstructExecutionModel
    → SelectVerificationMethod
    → SearchForNonProgressCycle
    → EvaluateFairExecutions
    → DetermineVerificationStatus
    → GenerateEvidence
    → ExplainResult

AI_CONSUMPTION :=
    {
        ParseLivenessEntities,
        ParseTypedRelations,
        ResolveTemporalSemantics,
        IdentifyTriggers,
        IdentifyGoals,
        DetectProgressRequirements,
        ResolveFairness,
        DetectStarvation,
        DetectLivelock,
        FollowTraceability,
        EvaluateVerificationEvidence,
        GenerateFormalExplanation
    }

UPDATE_MODEL :=
    NewLivenessEvidence
    → ValidateEvidence
    → ResolveAffectedProperty
    → ReevaluateFairnessAssumptions
    → DetectContradiction
    → UpdateLivenessGraph
    → RecomputeVerificationStatus
    → RecomputeConfidence
    → PreserveProvenance
    → VersionModel

CounterexampleUpdate :=
    ValidFairInfiniteCounterexample
    ⇒ mark(Property, Violated)

ProofUpdate :=
    ValidLivenessProof
    ∧ AssumptionsSatisfied
    ⇒ mark(Property, VerifiedUnderAssumptions)

ModelChange :=
    ChangedTransitionSystem
    ∨ ChangedScheduler
    ∨ ChangedFairnessAssumption
    ⇒ invalidate_or_recheck(
        DependentLivenessResults
    )

FLOW_HASH_INPUT :=
    canonical(
        ONTOLOGY,
        CoreClasses,
        CoreRelations,
        InferenceRules,
        LivenessFormalisation,
        Fairness,
        LivenessVerification,
        AI_REASONING_FLOW
    )

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT)

OUTPUT_MODEL :=
    {
        LivenessEntityResolution,
        FormalLivenessMeaning,
        TriggerGoalRelations,
        FairnessAssumptions,
        ProgressStatus,
        VerificationStatus,
        CounterexampleStatus,
        Evidence,
        Confidence,
        Provenance,
        Explanation
    }

END_FLOW

END OF AI SEARCH FLOW ALGEBRA