Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax53.AutomatonLinearTime

Word-RAM evaluation of tree automata

concepts/Lax53/AutomatonLinearTime.lean · lax-53

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Theorem

    Finite bottom-up tree-automaton acceptance has one uniform implementation on the Lax word RAM. The program is chosen before the automaton, tree, and word width. Its actual machine instruction count is bounded by a fixed constant times a quadratic function of the automaton workload and a linear function of the number of tree nodes. The workload is the certified constructor size plus the largest symbol rank; the latter is relevant because a node may have that many ordered children even though a rank is one primitive natural payload.

    The only physical input admitted by the theorem is the distinguished constructor-certified lax58lax-58 arena input. Lax58's reusable complexity predicate supplies the program quantifier and requires correctness at every word width satisfying payload, arena-address, and implementation-capacity bounds. The natural output is one word: zero for rejection and one for acceptance.

    Lean source view on GitHub

    1import Lax58.RamComplexity
    2import Lax53.TreeModelCheckingEncoding
    3
    4/-!
    5---
    6title: Word-RAM evaluation of tree automata
    7type: theorem
    8---
    9
    10Finite bottom-up tree-automaton acceptance has one uniform implementation on
    11the Lax word RAM. The program is chosen before the automaton, tree, and word
    12width. Its actual machine instruction count is bounded by a fixed constant
    13times a quadratic function of the automaton workload and a linear function of
    14the number of tree nodes. The workload is the certified constructor size plus
    15the largest symbol rank; the latter is relevant because a node may have that
    16many ordered children even though a rank is one primitive natural payload.
    17
    18The only physical input admitted by the theorem is the distinguished
    19constructor-certified `lax-58` arena input. Lax58's reusable complexity
    20predicate supplies the program quantifier and requires correctness at every
    21word width satisfying payload, arena-address, and implementation-capacity
    22bounds. The natural output is one word: zero for rejection and one for
    23acceptance.
    24-/
    25
    26namespace Lax53.AutomatonLinearTime
    27
    28open Lax53.RankedTree
    29open Lax53.TreeAutomaton
    30open Lax53.ValueTranslations
    31open Lax53.TreeModelCheckingEncoding
    32open Lax58.RamComplexity
    33
    34/-- Intrinsic workload of an automaton for the simple uniform evaluator. It
    35keeps constructor count separate from the magnitude of its largest arity. -/
    36def automatonWorkSize (M : EncodedAutomaton) : Nat :=
    37 automatonSize M + maximumRank M.1
    38
    39/-- Public instruction bound for the uniform evaluator. -/
    40def uniformTimeBound (constant : Nat) (M : EncodedAutomaton)
    41 (t : Tree M.1.toRankedAlphabet) : Nat :=
    42 constant * (automatonWorkSize M + 1) ^ 2 * (treeSize t + 1)
    43
    44/-- Explicit word-resource bound. Besides structural workload it includes the
    45largest primitive payload because machine values and the fixed compiler layout
    46must both fit in one word. -/
    47def uniformWordBound (constant : Nat) (M : EncodedAutomaton)
    48 (t : Tree M.1.toRankedAlphabet) : Nat :=
    49 constant * (automatonWorkSize M + 1) ^ 2 *
    50 (inputStructuralSize M t + inputPayloadMax M t + 1)
    51
    52open Classical in
    53/-- One program handles every certified automaton/tree input and every
    54sufficiently large word width. The reusable predicate contains the program
    55and width quantifiers and all three input/resource-fit premises. -/
    56axiom exists_uniform_automatonAcceptance :
    57 ∃ timeConstant wordConstant : Nat,
    58 RamComputableWithinUsing automatonAcceptancePresentation natOutput
    59 (fun input => if input.automaton.2.toAutomaton input.automaton.1 |>.Accepts
    60 input.tree then 1 else 0)
    61 (fun input => uniformTimeBound timeConstant input.automaton input.tree)
    62 (fun input => uniformWordBound wordConstant input.automaton input.tree)
    63
    64open Classical in
    65/-- With the automaton fixed before program choice, acceptance is linear in
    66the number of tree nodes. This existential specialization claim does not
    67assert an effective program-producing function. -/
    68axiom exists_fixed_automatonAcceptance (M : EncodedAutomaton) :
    69 ∃ timeCoefficient wordCoefficient : Nat,
    70 RamComputableWithinUsing (fixedAutomatonPresentation M) natOutput
    71 (fun t => if M.2.toAutomaton M.1 |>.Accepts t then 1 else 0)
    72 (fun t => timeCoefficient * (treeSize t + 1))
    73 (fun t => wordCoefficient * inputMagnitudeUsing
    74 (fixedAutomatonPresentation M) t)
    75
    76end Lax53.AutomatonLinearTime
    77
    Show ProofShow Proof

    Used by

    none

    From Mathlib

    none

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…