Syntax Ontology

AI SEARCH FLOW ALGEBRA — SYNTAX ONTOLOGY
Kireth Research — Semantic Library
URL: https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/logical-semantics/syntax-ontology.html

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

BEGIN_FLOW

Syntax :=
    FormalStructureOfExpressions
    ∧ SymbolRules
    ∧ FormationRules
    ∧ Grammar
    ∧ WellFormedness

SyntaxPurpose :=
    define(ValidExpressions)
    ∧ separate(FormFromMeaning)
    ∧ enable(FormalParsing)
    ∧ support(Derivation)
    ∧ provide(InputToSemantics)

FormalLanguage :=
    Alphabet
    ∧ Vocabulary
    ∧ Grammar
    ∧ WellFormedExpressions

Alphabet :=
    SetOfPermittedSymbols

Vocabulary :=
    LogicalSymbols
    ∪ NonLogicalSymbols
    ∪ Variables
    ∪ Punctuation

LogicalSymbols := {
    ¬,
    ∧,
    ∨,
    →,
    ↔,
    ∀,
    ∃,
    =,
    ⊥,
    ⊤
}

NonLogicalSymbols := {
    Constants,
    FunctionSymbols,
    PredicateSymbols,
    RelationSymbols
}

Variable :=
    Symbol
    ∧ may_be_bound_or_free

ConstantSymbol :=
    Symbol
    ∧ arity = 0

FunctionSymbol :=
    Symbol
    ∧ arity ≥ 0

PredicateSymbol :=
    Symbol
    ∧ arity ≥ 0

Arity :=
    NumberOfArguments(Symbol)

Term :=
    Variable
    ∨ Constant
    ∨ FunctionApplication

TermFormation := {
    Variable(x) ⇒ Term(x),
    Constant(c) ⇒ Term(c),
    f arity n
        ∧ Term(t1)...Term(tn)
        ⇒ Term(f(t1,...,tn))
}

AtomicFormula :=
    PredicateApplication
    ∨ EqualityFormula

PredicateApplication :=
    P(t1,...,tn)

EqualityFormula :=
    t1 = t2

Formula :=
    AtomicFormula
    ∨ Negation
    ∨ BinaryCompoundFormula
    ∨ QuantifiedFormula

Negation :=
    ¬φ

Conjunction :=
    (φ ∧ ψ)

Disjunction :=
    (φ ∨ ψ)

Implication :=
    (φ → ψ)

Biconditional :=
    (φ ↔ ψ)

UniversalFormula :=
    ∀x φ

ExistentialFormula :=
    ∃x φ

FormulaFormation := {
    AtomicFormula(φ) ⇒ Formula(φ),
    Formula(φ) ⇒ Formula(¬φ),
    Formula(φ) ∧ Formula(ψ)
        ⇒ Formula((φ ∧ ψ)),
    Formula(φ) ∧ Formula(ψ)
        ⇒ Formula((φ ∨ ψ)),
    Formula(φ) ∧ Formula(ψ)
        ⇒ Formula((φ → ψ)),
    Formula(φ) ∧ Formula(ψ)
        ⇒ Formula((φ ↔ ψ)),
    Variable(x) ∧ Formula(φ)
        ⇒ Formula(∀x φ),
    Variable(x) ∧ Formula(φ)
        ⇒ Formula(∃x φ)
}

WellFormedFormula :=
    Formula
    ∧ generated_by(FormationRules)

WFF :=
    WellFormedFormula

IllFormedExpression :=
    SymbolSequence
    ∧ not_generated_by(Grammar)

Grammar :=
    ProductionRules
    ∧ StartSymbol
    ∧ Terminals
    ∧ Nonterminals

Production :=
    Nonterminal → SymbolSequence

BNF :=
    GrammarNotation
    ∧ defines(FormalSyntax)

AbstractSyntax :=
    StructuralRepresentation
    independent_of
    SurfaceNotation

ConcreteSyntax :=
    SurfaceRepresentation
    ∧ punctuation
    ∧ delimiters
    ∧ lexical_form

AbstractSyntaxTree :=
    AST
    ∧ TreeRepresentation(ExpressionStructure)

ASTNode :=
    Operator
    ∨ Identifier
    ∨ Literal
    ∨ Binder
    ∨ Application

ParseTree :=
    Tree
    ∧ records(GrammarDerivation)

Parsing :=
    TokenSequence
    → ParseTree
    → AbstractSyntaxTree

LexicalAnalysis :=
    CharacterSequence
    → TokenSequence

Token :=
    SymbolCategory
    ∧ Lexeme

Parser :=
    Grammar
    ∧ TokenSequence
    → ParseResult

ParseResult := {
    ValidAST,
    SyntaxError
}

SyntaxError :=
    Position
    ∧ UnexpectedToken
    ∧ ExpectedConstruct

Precedence :=
    OrderingOfOperators

Associativity := {
    LeftAssociative,
    RightAssociative,
    NonAssociative
}

Parenthesisation :=
    ExplicitGrouping(Expression)

AmbiguousGrammar :=
    ∃Expression :
        multiple(ParseTrees(Expression))

UnambiguousGrammar :=
    ∀Expression :
        at_most_one(ParseTree(Expression))

Metavariable :=
    SymbolInMetalanguage
    ∧ ranges_over(SyntacticObjects)

ObjectLanguage :=
    LanguageBeingDefined

Metalanguage :=
    LanguageUsedToDefine(ObjectLanguage)

SyntacticCategory := {
    Term,
    Formula,
    Variable,
    Identifier,
    Type,
    Expression,
    Statement,
    Declaration
}

Subexpression :=
    ExpressionContainedWithin(Expression)

ImmediateSubexpression :=
    DirectChild(ASTNode)

StructuralComplexity :=
    recursive_measure(Expression)

FormulaLength :=
    NumberOfSymbols(Formula)

TermDepth :=
    max_path_length(AST(Term))

FormulaDepth :=
    max_path_length(AST(Formula))

Binding :=
    Binder
    → VariableOccurrences

Binder := {
    UniversalQuantifier,
    ExistentialQuantifier,
    LambdaBinder
}

Scope :=
    SyntacticRegionControlledBy(Binder)

BoundOccurrence :=
    VariableOccurrence
    ∧ within_scope_of(MatchingBinder)

FreeOccurrence :=
    VariableOccurrence
    ∧ not_bound

FreeVariables :=
    FV(Expression)

FV(x) :=
    {x}

FV(c) :=
    ∅

FV(f(t1,...,tn)) :=
    FV(t1) ∪ ... ∪ FV(tn)

FV(¬φ) :=
    FV(φ)

FV(φ ◦ ψ) :=
    FV(φ) ∪ FV(ψ)

FV(∀x φ) :=
    FV(φ) \ {x}

FV(∃x φ) :=
    FV(φ) \ {x}

ClosedFormula :=
    Formula
    ∧ FV(Formula) = ∅

Sentence :=
    ClosedFormula

OpenFormula :=
    Formula
    ∧ FV(Formula) ≠ ∅

Substitution :=
    Expression[x←Term]

CaptureAvoidingSubstitution :=
    Substitution
    ∧ no_free_variable_becomes_accidentally_bound

VariableCapture :=
    FreeOccurrence
    → BoundOccurrence
    caused_by(Substitution)

AlphaConversion :=
    RenameBoundVariable
    while preserving(BindingStructure)

AlphaEquivalence :=
    ExpressionA ≡α ExpressionB
    iff
    differ_only_by(BoundVariableNames)

SyntacticIdentity :=
    exact_symbolic_structure(ExpressionA)
    =
    exact_symbolic_structure(ExpressionB)

StructuralEquivalence :=
    same(AbstractSyntaxStructure)

SyntacticTransformation :=
    ExpressionA → ExpressionB

RewriteRule :=
    Pattern → Replacement

RewriteSystem :=
    Set(RewriteRules)

Reduction :=
    Expression → ReducedExpression

NormalForm :=
    Expression
    ∧ no_applicable_rewrite_rule

Normalisation :=
    Expression →* NormalForm

Confluence :=
    e →* e1
    ∧ e →* e2
    ⇒
    ∃e3 :
        e1 →* e3
        ∧ e2 →* e3

Termination :=
    no_infinite_rewrite_sequence

CanonicalForm :=
    UniqueNormalRepresentation
    under specified syntactic equivalence

Derivation :=
    StartExpression
    → RuleApplicationSequence
    → DerivedExpression

FormalProofSyntax :=
    Premises
    ∧ InferenceRuleApplications
    ∧ Conclusion

Sequent :=
    Γ ⊢ Δ

Context :=
    OrderedOrUnorderedCollection(Formulae)

InferenceRule :=
    Premises
    ─────────
    Conclusion

ProofTree :=
    Tree
    ∧ Leaves(AxiomsOrAssumptions)
    ∧ InternalNodes(InferenceRules)
    ∧ Root(Conclusion)

PropositionalSyntax :=
    PropositionalVariables
    ∧ Connectives
    ∧ Parentheses

PredicateLogicSyntax :=
    Variables
    ∧ Constants
    ∧ Functions
    ∧ Predicates
    ∧ Quantifiers
    ∧ Connectives

ModalLogicSyntax :=
    Formula
    ∧ ModalOperators{□,◇}

TemporalLogicSyntax :=
    Formula
    ∧ TemporalOperators{X,F,G,U,R}

TypedSyntax :=
    Syntax
    ∧ TypeAnnotations
    ∧ TypingRules

Type :=
    SyntacticOrSemanticClassification

TypingContext :=
    Γ = {x1:τ1, ..., xn:τn}

TypingJudgement :=
    Γ ⊢ e : τ

TypeCorrectSyntax :=
    WellFormedExpression
    ∧ satisfies(TypingRules)

HigherOrderSyntax :=
    FunctionsAsTerms
    ∧ PredicateVariables
    ∧ HigherOrderApplication

LambdaSyntax :=
    Variable
    ∨ Application
    ∨ Abstraction

LambdaTerm :=
    x
    ∨ (M N)
    ∨ (λx.M)

BetaRedex :=
    (λx.M) N

BetaReduction :=
    (λx.M) N
    → M[x←N]

SyntacticSugar :=
    SurfaceConstruct
    ∧ translated_to(CoreSyntax)

Desugaring :=
    ConcreteSyntax
    → CoreAbstractSyntax

MacroExpansion :=
    MacroInvocation
    → ExpandedSyntax

SyntaxDirectedTranslation :=
    AST
    → TargetRepresentation
    based_on(NodeRules)

SyntaxSemanticsBoundary :=
    Syntax
    → SemanticInterpretation

SyntaxDoesNotDetermineMeaningAlone :=
    SameSyntax
    may_receive
    DifferentInterpretations

FormalSyntaxSpecification :=
    Alphabet
    ∧ LexicalRules
    ∧ Grammar
    ∧ BindingRules
    ∧ WellFormednessConstraints

SyntacticValidation :=
    Input
    → Tokenise
    → Parse
    → CheckWellFormedness
    → CheckBinding
    → CheckTypesIfApplicable

SyntacticValidity :=
    generated_by(Grammar)
    ∧ satisfies(StaticSyntacticConstraints)

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

CoreClasses := {
    Syntax,
    FormalLanguage,
    Alphabet,
    Symbol,
    Token,
    Grammar,
    ProductionRule,
    Term,
    Formula,
    AtomicFormula,
    Variable,
    ConstantSymbol,
    FunctionSymbol,
    PredicateSymbol,
    Quantifier,
    Connective,
    Binder,
    Scope,
    ParseTree,
    AbstractSyntaxTree,
    Substitution,
    RewriteRule,
    NormalForm
}

CoreRelations := {
    contains,
    forms,
    binds,
    occursIn,
    hasScope,
    substitutesFor,
    rewritesTo,
    derives,
    parsesAs,
    childOf,
    generatedBy,
    hasArity,
    precedes,
    associatesWith
}

TypedRelations :=
    Grammar --generates--> WellFormedExpression
    Binder --binds--> VariableOccurrence
    VariableOccurrence --occursIn--> Expression
    Binder --hasScope--> SyntacticRegion
    Parser --parsesAs--> AbstractSyntaxTree
    RewriteRule --rewritesTo--> Expression
    Formula --contains--> Subformula
    FunctionSymbol --hasArity--> Arity
    ProductionRule --forms--> SyntacticCategory

InferenceRulesOntology := {
    Variable(x)
        ⇒ Term(x),

    Constant(c)
        ⇒ Term(c),

    FunctionSymbol(f,n)
        ∧ Term(t1)...Term(tn)
        ⇒ Term(f(t1,...,tn)),

    PredicateSymbol(P,n)
        ∧ Term(t1)...Term(tn)
        ⇒ AtomicFormula(P(t1,...,tn)),

    Formula(φ)
        ⇒ Formula(¬φ),

    Formula(φ)
        ∧ Formula(ψ)
        ⇒ Formula(φ ∧ ψ),

    Variable(x)
        ∧ Formula(φ)
        ⇒ Formula(∀x φ),

    FV(φ) = ∅
        ⇒ Sentence(φ),

    AlphaEquivalent(A,B)
        ⇒ same_binding_structure(A,B)
}

SEMANTIC_EQUIVALENCE(ExpressionA, ExpressionB) :=
    Interpretation(ExpressionA)
    =
    Interpretation(ExpressionB)

SYNTACTIC_EQUIVALENCE(ExpressionA, ExpressionB) :=
    CanonicalSyntax(ExpressionA)
    =
    CanonicalSyntax(ExpressionB)

SyntacticSubsumption :=
    Pattern
    structurally_matches
    Expression

CanonicalSyntax :=
    Parse
    → ResolvePrecedence
    → ResolveAssociativity
    → BuildAST
    → AlphaNormalise
    → NormaliseNotation

SyntaxGraph :=
    G = (V,E)

V := {
    Languages,
    Symbols,
    Tokens,
    Terms,
    Formulae,
    Variables,
    Binders,
    Scopes,
    GrammarRules,
    ASTNodes,
    RewriteRules
}

E := {
    contains,
    forms,
    binds,
    occursIn,
    hasScope,
    substitutesFor,
    rewritesTo,
    derives,
    parsesAs,
    childOf,
    generatedBy
}

CONFIDENCE(SyntaxResolution) :=
    weighted_mean(
        GrammarMatch,
        TokenClassification,
        ParseUniqueness,
        BindingResolution,
        TypeConsistency,
        CanonicalisationQuality
    )

AI_QUERY_INTERPRETATION :=
    Query
    → DetectSyntaxConcept
    → ResolveFormalLanguage
    → IdentifySyntacticCategory
    → ParseExpression
    → ResolveBindingAndScope
    → IdentifyRequestedRelation

AI_REASONING_FLOW :=
    Query
    → IdentifyFormalLanguage
    → TokeniseExpression
    → ApplyGrammar
    → ConstructParseTree
    → ConstructAbstractSyntaxTree
    → ResolveOperatorPrecedence
    → ResolveAssociativity
    → ResolveBindings
    → IdentifyFreeAndBoundVariables
    → ValidateWellFormedness
    → ApplySubstitutionOrRewriteIfRequested
    → CanonicaliseSyntax
    → LinkSyntaxToSemanticLayer
    → GenerateExplanation

AI_CONSUMPTION := {
    ParseSyntaxEntities,
    ParseTypedRelations,
    Tokenise,
    ApplyGrammarRules,
    ConstructAST,
    ResolveBindings,
    ResolveScope,
    DetectFreeVariables,
    DetectBoundVariables,
    PerformCaptureAvoidingSubstitution,
    ApplyRewriteRules,
    CompareSyntacticEquivalence,
    ConnectSyntaxToSemantics,
    GenerateFormalExplanation
}

UPDATE_MODEL :=
    NewSyntaxEvidence
    → ValidateEvidence
    → ResolveAffectedGrammar
    → ReparseDependentExpressions
    → RecomputeBindings
    → RecomputeCanonicalSyntax
    → UpdateSyntaxGraph
    → RecomputeConfidence
    → PreserveProvenance
    → VersionModel

GrammarUpdate :=
    ChangedProductionRule
    ⇒ revalidate(
        DependentExpressions,
        ParseTrees,
        AbstractSyntaxTrees
    )

BindingUpdate :=
    ChangedBinderOrScopeRule
    ⇒ recompute(
        BoundOccurrences,
        FreeVariables,
        SubstitutionValidity
    )

RewriteUpdate :=
    ChangedRewriteRule
    ⇒ recheck(
        NormalForms,
        Confluence,
        Termination
    )

FLOW_HASH_INPUT :=
    canonical(
        ONTOLOGY,
        CoreClasses,
        CoreRelations,
        InferenceRulesOntology,
        FormulaFormation,
        Binding,
        Substitution,
        CanonicalSyntax,
        AI_REASONING_FLOW
    )

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT)

OUTPUT_MODEL := {
    SyntaxEntityResolution,
    FormalLanguage,
    TokenStructure,
    ParseStructure,
    AbstractSyntaxTree,
    BindingStructure,
    FreeVariables,
    BoundVariables,
    WellFormednessStatus,
    CanonicalSyntax,
    SyntacticEquivalence,
    SemanticLink,
    Confidence,
    Provenance,
    Explanation
}

END_FLOW

END OF AI SEARCH FLOW ALGEBRA