Lax53.AutomatonLinearTime
Word-RAM evaluation of tree automata
concepts/Lax53/AutomatonLinearTime.lean · lax-53
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Evidence
This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.
1st statement exists_fixed_automatonAcceptance proven
2nd statement exists_uniform_automatonAcceptance proven
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 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
| 1 | import Lax58.RamComplexity |
| 2 | import Lax53.TreeModelCheckingEncoding |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Word-RAM evaluation of tree automata |
| 7 | type: theorem |
| 8 | --- |
| 9 | |
| 10 | Finite bottom-up tree-automaton acceptance has one uniform implementation on |
| 11 | the Lax word RAM. The program is chosen before the automaton, tree, and word |
| 12 | width. Its actual machine instruction count is bounded by a fixed constant |
| 13 | times a quadratic function of the automaton workload and a linear function of |
| 14 | the number of tree nodes. The workload is the certified constructor size plus |
| 15 | the largest symbol rank; the latter is relevant because a node may have that |
| 16 | many ordered children even though a rank is one primitive natural payload. |
| 17 | |
| 18 | The only physical input admitted by the theorem is the distinguished |
| 19 | constructor-certified `lax-58` arena input. Lax58's reusable complexity |
| 20 | predicate supplies the program quantifier and requires correctness at every |
| 21 | word width satisfying payload, arena-address, and implementation-capacity |
| 22 | bounds. The natural output is one word: zero for rejection and one for |
| 23 | acceptance. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax53.AutomatonLinearTime |
| 27 | |
| 28 | open Lax53.RankedTree |
| 29 | open Lax53.TreeAutomaton |
| 30 | open Lax53.ValueTranslations |
| 31 | open Lax53.TreeModelCheckingEncoding |
| 32 | open Lax58.RamComplexity |
| 33 | |
| 34 | /-- Intrinsic workload of an automaton for the simple uniform evaluator. It |
| 35 | keeps constructor count separate from the magnitude of its largest arity. -/ |
| 36 | def automatonWorkSize (M : EncodedAutomaton) : Nat := |
| 37 | automatonSize M + maximumRank M.1 |
| 38 | |
| 39 | /-- Public instruction bound for the uniform evaluator. -/ |
| 40 | def 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 |
| 45 | largest primitive payload because machine values and the fixed compiler layout |
| 46 | must both fit in one word. -/ |
| 47 | def 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 | |
| 52 | open Classical in |
| 53 | /-- One program handles every certified automaton/tree input and every |
| 54 | sufficiently large word width. The reusable predicate contains the program |
| 55 | and width quantifiers and all three input/resource-fit premises. -/ |
| 56 | axiom 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 | |
| 64 | open Classical in |
| 65 | /-- With the automaton fixed before program choice, acceptance is linear in |
| 66 | the number of tree nodes. This existential specialization claim does not |
| 67 | assert an effective program-producing function. -/ |
| 68 | axiom 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 | |
| 76 | end Lax53.AutomatonLinearTime |
| 77 |
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