Specification Ontology

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

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

BEGIN_FLOW

Specification :=
    FormalDescription
    ∧ IntendedBehaviour
    ∧ Constraints
    ∧ Properties
    ∧ InterfaceRequirements
    ∧ EnvironmentalAssumptions
    ∧ VerificationCriteria

FormalSpecification :=
    Specification
    ∧ FormalLanguage
    ∧ MathematicalSemantics
    ∧ UnambiguousInterpretation

SpecificationPurpose :=
    DefineExpectedBehaviour
    ∧ ConstrainImplementation
    ∧ SupportReasoning
    ∧ EnableVerification
    ∧ EstablishCorrectnessCriteria

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

SpecificationLanguage :=
    {
        NaturalLanguage,
        StructuredNaturalLanguage,
        Logic,
        TemporalLogic,
        PredicateLogic,
        SetTheory,
        AlgebraicSpecification,
        StateBasedSpecification,
        ProcessAlgebra,
        ContractLanguage,
        DomainSpecificLanguage
    }

SpecificationComponent :=
    {
        State,
        Variable,
        Constant,
        Type,
        Operation,
        Event,
        Transition,
        Input,
        Output,
        Precondition,
        Postcondition,
        Invariant,
        Assumption,
        Guarantee,
        Constraint,
        Requirement,
        Property
    }

SystemModel :=
    States
    ∧ InitialStates
    ∧ Transitions
    ∧ Inputs
    ∧ Outputs
    ∧ Observations

StateSpace :=
    {s | s satisfies TypeConstraints ∧ StructuralConstraints}

InitialCondition :=
    Predicate(State)
    ∧ identifies(AllowedInitialStates)

TransitionRelation :=
    R ⊆ State × State

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

ValidExecution :=
    InitialCondition(s0)
    ∧ ∀i TransitionRelation(si, si+1)

Behaviour :=
    FiniteTrace
    ∨ InfiniteTrace
    ∨ StateTransitionSequence
    ∨ InputOutputRelation

RequiredBehaviour :=
    Behaviour ∩ SpecificationConstraints

ForbiddenBehaviour :=
    Behaviour \ RequiredBehaviour

Implementation :=
    ConcreteSystem
    ∧ OperationalSemantics

Satisfaction :=
    Implementation ⊨ Specification

CorrectImplementation :=
    Implementation
    ∧ satisfies(Implementation, Specification)

Refinement :=
    SpecDetailed ⊑ SpecAbstract

ValidRefinement :=
    Behaviours(SpecDetailed) ⊆ Behaviours(SpecAbstract)

Abstraction :=
    ConcreteModel → AbstractModel

Concretisation :=
    AbstractModel → Set(ConcreteModels)

Requirement :=
    DesiredProperty
    ∧ Scope
    ∧ Condition
    ∧ ExpectedOutcome

FunctionalRequirement :=
    Condition → RequiredAction

NonFunctionalRequirement :=
    Constraint(
        Performance
        ∨ Reliability
        ∨ Security
        ∨ Safety
        ∨ Availability
        ∨ Timing
        ∨ ResourceUsage
    )

SafetyProperty :=
    "something bad never happens"

SafetyFormalisation :=
    ∀ExecutionPrefix p : ¬BadState(p)

LivenessProperty :=
    "something good eventually happens"

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

Invariant :=
    P(State)

InvariantCondition :=
    InitialCondition ⇒ P
    ∧
    (P(s) ∧ TransitionRelation(s,s')) ⇒ P(s')

Precondition :=
    Predicate(Input, State)

Postcondition :=
    Predicate(Input, OldState, NewState, Output)

OperationContract :=
    Precondition
    ⇒
    Operation
    ⇒
    Postcondition

HoareTriple :=
    {P} C {Q}

HoareMeaning :=
    P holds before C
    ∧ C terminates
    ⇒ Q holds after C

PartialCorrectness :=
    P ∧ terminates(C) ⇒ Q

TotalCorrectness :=
    PartialCorrectness
    ∧ Termination

AssumeGuaranteeSpecification :=
    Assumption(Environment)
    ⇒ Guarantee(System)

InterfaceSpecification :=
    Inputs
    ∧ Outputs
    ∧ Operations
    ∧ ProtocolRules
    ∧ TimingConstraints
    ∧ ErrorConditions

DataSpecification :=
    Types
    ∧ Domains
    ∧ Relations
    ∧ IntegrityConstraints

ControlSpecification :=
    States
    ∧ Events
    ∧ Guards
    ∧ Transitions
    ∧ Actions

TemporalSpecification :=
    TimeDependentProperty
    ∧ TemporalLogicFormula

LTLSpecification :=
    Formula(
        AtomicProposition,
        ¬,
        ∧,
        ∨,
        X,
        F,
        G,
        U
    )

CTLSpecification :=
    Formula(
        AtomicProposition,
        PathQuantifier{A,E},
        TemporalOperator{X,F,G,U}
    )

CommonTemporalPatterns :=
    {
        Invariance: G(P),
        Eventuality: F(P),
        Response: G(P → F(Q)),
        Precedence: ¬Q U P,
        Persistence: F(G(P))
    }

AlgebraicSpecification :=
    Sorts
    ∧ Operations
    ∧ Equations
    ∧ Axioms

StateBasedSpecification :=
    StateSchema
    ∧ Initialisation
    ∧ Operations
    ∧ Invariants

TransitionSystemSpecification :=
    (S, S0, R, AP, L)

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

LabelledTransitionSystem :=
    (S, Act, →)

ProcessSpecification :=
    Processes
    ∧ Actions
    ∧ CompositionOperators
    ∧ SynchronisationRules

Contract :=
    Preconditions
    ∧ Postconditions
    ∧ Invariants

DesignByContract :=
    CallerObligation(Precondition)
    ∧ SupplierObligation(Postcondition)
    ∧ PersistentInvariant

SpecificationConsistency :=
    ¬∃P : Specification ⊢ P ∧ Specification ⊢ ¬P

SpecificationCompleteness :=
    RelevantBehaviour
    ⊆
    DefinedOrConstrainedBehaviour

SpecificationAmbiguity :=
    MultiplePlausibleInterpretations

FormalisationGoal :=
    minimise(Ambiguity)
    ∧ maximise(Precision)
    ∧ preserve(Intent)

SpecificationValidation :=
    "Are we specifying the intended system?"

SpecificationVerification :=
    "Does the formal artefact satisfy required formal properties?"

ValidationMethods :=
    {
        Review,
        Simulation,
        Animation,
        ScenarioAnalysis,
        StakeholderInspection,
        TraceAnalysis
    }

VerificationMethods :=
    {
        ModelChecking,
        TheoremProving,
        DeductiveVerification,
        StaticAnalysis,
        SymbolicExecution,
        RefinementChecking,
        EquivalenceChecking
    }

ModelCheckingRelation :=
    Model M
    ∧ Property φ
    →
    evaluate(M ⊨ φ)

ModelCheckingResult :=
    Satisfied
    ∨ Counterexample

TheoremProvingRelation :=
    Axioms
    ∧ Specification
    ⊢ Property

Counterexample :=
    ExecutionTrace
    ∧ violates(Property)

Witness :=
    ExecutionTrace
    ∧ satisfies(ExistentialProperty)

Traceability :=
    Requirement
    ↔ SpecificationElement
    ↔ DesignElement
    ↔ ImplementationElement
    ↔ VerificationEvidence

RequirementTrace :=
    R_i → S_j → V_k

ChangeImpact :=
    ChangedSpecificationElement
    →
    DependentRequirements
    ∪ DependentModels
    ∪ DependentProofs
    ∪ DependentTests

SpecificationHierarchy :=
    InformalRequirement
    → StructuredRequirement
    → FormalSpecification
    → RefinedSpecification
    → Implementation
    → VerificationEvidence

RefinementChain :=
    S0 ⊒ S1 ⊒ S2 ⊒ ... ⊒ Implementation

RefinementObligation :=
    ∀Behaviour b :
        b ∈ Behaviours(S_n)
        ⇒
        b ∈ Behaviours(S_n-1)

Equivalence :=
    SpecA ≡ SpecB
    iff
    Behaviours(SpecA) = Behaviours(SpecB)

ObservationalEquivalence :=
    Observations(SpecA) = Observations(SpecB)

ConsistencyCheck :=
    satisfiable(Specification)

Satisfiability :=
    ∃Model M : M ⊨ Specification

UnsatisfiableSpecification :=
    ¬∃Model M : M ⊨ Specification

UnderSpecification :=
    ∃Behaviour b :
        b is unintended
        ∧ b satisfies Specification

OverSpecification :=
    ∃IntendedImplementation i :
        i fails Specification
        because Specification contains unnecessary constraints

SpecificationError :=
    Ambiguity
    ∨ Contradiction
    ∨ Omission
    ∨ IncorrectConstraint
    ∨ UnverifiableRequirement
    ∨ InconsistentAssumption

QualityAttributes :=
    {
        Correctness,
        Completeness,
        Consistency,
        Clarity,
        Precision,
        Traceability,
        Verifiability,
        Modularity,
        Maintainability
    }

SpecificationComposition :=
    Spec1 ⊗ Spec2

CompatibleSpecifications :=
    constraints(Spec1) ∩ constraints(Spec2) is satisfiable

CompositionResult :=
    CombinedBehaviour
    ∧ CombinedConstraints
    ∧ ResolvedInterfaces

Decomposition :=
    SystemSpecification
    →
    {ComponentSpec1, ComponentSpec2, ..., ComponentSpecN}

DecompositionCorrectness :=
    compose(ComponentSpecifications)
    ⊨
    SystemSpecification

EnvironmentModel :=
    ExternalStates
    ∧ ExternalEvents
    ∧ Assumptions
    ∧ InteractionConstraints

ClosedSystemVerification :=
    SystemModel
    ∧ EnvironmentModel
    ⊨ Property

OpenSystemSpecification :=
    Assumptions(Environment)
    ∧ Guarantees(System)

Nondeterminism :=
    ∃s : |Successors(s)| > 1

DeterministicSpecification :=
    ∀s,input :
        |AllowedNextStates(s,input)| ≤ 1

ExecutableSpecification :=
    FormalSpecification
    ∧ OperationalSemantics
    ∧ MachineEvaluable

DeclarativeSpecification :=
    states(WhatMustHold)
    rather_than
    states(HowToCompute)

SpecificationSemantics :=
    Syntax
    → Interpretation
    → MathematicalModel
    → Meaning

Syntax :=
    WellFormedExpressions

Semantics :=
    Mapping(Syntax, Meaning)

DenotationalSemantics :=
    Expression → MathematicalObject

OperationalSemantics :=
    Configuration → TransitionRules

AxiomaticSemantics :=
    ProgramConstruct → LogicalAssertions

SemanticPreservation :=
    transform(SpecA, SpecB)
    ⇒
    Meaning(SpecA) = Meaning(SpecB)

VerificationCondition :=
    LogicalFormula
    ∧ must_be_proved_for(Correctness)

VerificationConditionGeneration :=
    Program
    ∧ Specification
    →
    {VC1, VC2, ..., VCn}

ProofObligation :=
    FormalClaim
    ∧ required_for(Refinement ∨ Correctness ∨ Consistency)

DischargeProofObligation :=
    AutomatedProver
    ∨ InteractiveTheoremProver
    ∨ DecisionProcedure
    ∨ ManualProof

SpecificationRepository :=
    Ontology
    ∧ Version
    ∧ Dependencies
    ∧ Provenance
    ∧ VerificationStatus

SpecificationVersion :=
    Identifier
    ∧ Timestamp
    ∧ ChangeSet
    ∧ ParentVersion

Provenance :=
    Source
    ∧ Author
    ∧ TransformationHistory
    ∧ Evidence

MachineReadableSpecification :=
    StructuredRepresentation
    ∧ ExplicitSemantics
    ∧ TypedEntities
    ∧ TypedRelationships

SpecificationOntology :=
    Classes
    ∧ Relations
    ∧ Constraints
    ∧ Axioms
    ∧ Instances
    ∧ VerificationRules

CoreClasses :=
    {
        Specification,
        Requirement,
        Property,
        Constraint,
        Assumption,
        Guarantee,
        State,
        Transition,
        Operation,
        Interface,
        Model,
        Implementation,
        ProofObligation,
        VerificationResult,
        Counterexample
    }

CoreRelations :=
    {
        specifies,
        constrains,
        assumes,
        guarantees,
        refines,
        implements,
        satisfies,
        violates,
        verifies,
        dependsOn,
        composedWith,
        abstracts,
        concretises,
        tracesTo
    }

TypedRelationExamples :=
    Specification --specifies--> System
    Requirement --constrains--> Behaviour
    Implementation --implements--> Specification
    Implementation --satisfies--> Property
    RefinedSpecification --refines--> AbstractSpecification
    ProofObligation --verifies--> Refinement
    Counterexample --violates--> Property
    Requirement --tracesTo--> VerificationEvidence

InferenceRules := {
    (Implementation satisfies Spec)
        ∧ (Spec entails Property)
        ⇒ (Implementation satisfies Property),

    (SpecB refines SpecA)
        ∧ (Implementation satisfies SpecB)
        ⇒ candidate(Implementation satisfies SpecA),

    (Property is Invariant)
        ∧ InitialState satisfies Property
        ∧ every Transition preserves Property
        ⇒ all ReachableStates satisfy Property,

    (Specification is Unsatisfiable)
        ⇒ no Implementation can satisfy Specification,

    (Counterexample violates Property)
        ⇒ Property not universally satisfied by Model
}

Reachability :=
    Reachable(s)
    iff
    s ∈ InitialStates
    ∨ ∃p : Reachable(p) ∧ TransitionRelation(p,s)

InvariantVerification :=
    ∀s :
        Reachable(s)
        ⇒ P(s)

Deadlock :=
    Reachable(s)
    ∧ noEnabledTransition(s)

DeadlockFreedom :=
    ∀s :
        Reachable(s)
        ⇒ existsEnabledTransition(s)

MutualExclusion :=
    G ¬(Critical1 ∧ Critical2)

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

TerminationProperty :=
    ∀Execution : eventually(FinalState)

FairnessConstraint :=
    continuouslyEnabled(Action)
    ⇒ eventuallyExecuted(Action)

SecuritySpecification :=
    Confidentiality
    ∧ Integrity
    ∧ Availability
    ∧ Authorisation
    ∧ InformationFlowConstraints

SafetyCriticalSpecification :=
    Hazard
    → SafetyConstraint
    → VerificationObligation
    → Evidence

SpecificationEvidence :=
    Proof
    ∨ ModelCheckResult
    ∨ TestResult
    ∨ AnalysisResult
    ∨ ReviewRecord

Confidence :=
    f(
        Formality,
        Consistency,
        VerificationCoverage,
        EvidenceStrength,
        Traceability,
        SemanticClarity
    )

CONFIDENCE(Specification) :=
    weighted_mean(
        FormalityScore,
        ConsistencyScore,
        CompletenessScore,
        VerificationScore,
        TraceabilityScore
    )

SemanticEquivalence :=
    SEMANTIC_EQUIVALENCE(SpecA, SpecB)
    iff
    Meaning(SpecA) ≡ Meaning(SpecB)

SemanticCompatibility :=
    compatible(
        Constraints(SpecA),
        Constraints(SpecB),
        Assumptions(SpecA),
        Assumptions(SpecB)
    )

Canonicalisation :=
    Specification
    → NormalisedEntities
    → NormalisedRelations
    → NormalisedConstraints
    → CanonicalSpecificationGraph

SpecificationGraph :=
    G = (V,E)

V :=
    {
        Requirements,
        States,
        Operations,
        Properties,
        Assumptions,
        Guarantees,
        Components,
        Evidence
    }

E :=
    {
        constrains,
        dependsOn,
        refines,
        satisfies,
        violates,
        tracesTo,
        verifies
    }

AI_REASONING_FLOW :=
    Query
    → IdentifySpecificationEntity
    → ResolveSpecificationType
    → ExtractRequirements
    → ExtractAssumptions
    → ExtractConstraints
    → BuildFormalModel
    → IdentifyProperties
    → GenerateProofObligations
    → SelectVerificationMethod
    → EvaluateSatisfaction
    → ProduceEvidence
    → ReturnExplanation

AI_QUERY_INTERPRETATION :=
    lexical_match(Query)
    ∪ semantic_match(Query)
    ∪ ontology_relation_match(Query)
    ∪ formal_property_match(Query)

AI_CONSUMPTION :=
    {
        ParseEntities,
        ParseRelations,
        ResolveDefinitions,
        FollowRefinementLinks,
        EvaluateConstraints,
        CompareSpecifications,
        IdentifyVerificationObligations,
        GenerateExplanations
    }

UPDATE_MODEL :=
    NewEvidence
    → Validate
    → CompareWithExistingSpecification
    → DetectConflict
    → UpdateAffectedEntities
    → RecomputeRelations
    → RecomputeConfidence
    → VersionSpecificationGraph

ConflictResolution :=
    Conflict
    → IdentifySources
    → CompareAuthority
    → CompareFormalConsistency
    → PreserveProvenance
    → MarkUnresolvedIfNecessary

FLOW_HASH_INPUT :=
    canonical(
        ONTOLOGY,
        CoreClasses,
        CoreRelations,
        InferenceRules,
        SpecificationSemantics,
        VerificationRelations
    )

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT)

OUTPUT_MODEL :=
    {
        EntityResolution,
        FormalMeaning,
        RelationshipGraph,
        ConstraintSet,
        VerificationStatus,
        Confidence,
        Provenance,
        Explanation
    }

END_FLOW

END OF AI SEARCH FLOW ALGEBRA