Second-order transitive closure without an order
Lax134656.OrderFreeTransitiveClosure · concepts/Lax134656/OrderFreeTransitiveClosure.lean · lax-134656
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An order-free second-order transitive-closure specification over a vocabulary is a specification whose three sentences are over and the copies of the block alone, with no order symbol. It defines, on any -structure, the same graph on the assignments of the block and the same acceptance condition. A decision problem over is order-free SO(TC) definable when some such specification accepts, for every nonempty finite -structure , exactly when is a yes-instance of : no linear order appears in the statement.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Order |
| 2 | import Mathlib.ModelTheory.Semantics |
| 3 | import Mathlib.Logic.Relation |
| 4 | import Lax904597.Problems |
| 5 | import Lax904597.SecondOrder |
| 6 | import Lax535992.InflationaryFixedPoint |
| 7 | import Lax134656.SecondOrderTransitiveClosure |
| 8 | |
| 9 | /-! |
| 10 | --- |
| 11 | title: Second-order transitive closure without an order |
| 12 | type: definition |
| 13 | --- |
| 14 | An order-free second-order transitive-closure specification over a |
| 15 | vocabulary is a specification whose three sentences are over and |
| 16 | the copies of the block alone, with no order symbol. It defines, on any |
| 17 | -structure, the same graph on the assignments of the block and the same |
| 18 | acceptance condition. A decision problem over is order-free SO(TC) |
| 19 | definable when some such specification accepts, for every nonempty finite |
| 20 | -structure , exactly when is a yes-instance of : no linear |
| 21 | order appears in the statement. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax134656.OrderFreeTransitiveClosure |
| 25 | |
| 26 | open Lax904597.Problems Lax904597.SecondOrder Lax535992.InflationaryFixedPoint |
| 27 | open Lax134656.SecondOrderTransitiveClosure |
| 28 | |
| 29 | open FirstOrder |
| 30 | |
| 31 | open Language Structure |
| 32 | |
| 33 | /-- An SO(TC) specification that does **not** see a linear order: as in |
| 34 | `SOTCSpec`, the states of the walk are the assignments of |
| 35 | a block, but the three sentences live over the bare vocabulary expanded by |
| 36 | copies of the block, with no order symbol available. -/ |
| 37 | structure SOTCSpecFree (L : Language.{0, 0}) : Type 1 where |
| 38 | /-- The block whose assignments are the states of the walk. -/ |
| 39 | B : SOBlock |
| 40 | /-- The transition sentence, over two copies of the block: the current state |
| 41 | reads the first copy, the next state the second. -/ |
| 42 | step : ((L.sum B.lang).sum B.lang).Sentence |
| 43 | /-- The sentence defining the admissible starting states. -/ |
| 44 | src : (L.sum B.lang).Sentence |
| 45 | /-- The sentence defining the accepting states. -/ |
| 46 | tgt : (L.sum B.lang).Sentence |
| 47 | |
| 48 | namespace SOTCSpecFree |
| 49 | |
| 50 | section Semantics |
| 51 | |
| 52 | variable {L : Language.{0, 0}} (spec : SOTCSpecFree L) {A : Type} [L.Structure A] |
| 53 | |
| 54 | variable (A) in |
| 55 | /-- A state of the walk: an assignment of the block. -/ |
| 56 | abbrev State : Type := spec.B.Assignment A |
| 57 | |
| 58 | /-- One step of the walk: the transition sentence, read with the current state |
| 59 | in the first copy of the block and the next state in the second. -/ |
| 60 | def Step (ρ σ : spec.State A) : Prop := |
| 61 | @Sentence.Realize _ A (SOBlock.structure₂ (L := L) spec.B ρ σ) spec.step |
| 62 | |
| 63 | /-- Reachability in the walk: the reflexive-transitive closure of |
| 64 | `SOTCSpecFree.Step`. -/ |
| 65 | abbrev Reach : spec.State A → spec.State A → Prop := |
| 66 | Relation.ReflTransGen spec.Step |
| 67 | |
| 68 | /-- A state is a starting state when it satisfies the source sentence. -/ |
| 69 | def IsSrc (ρ : spec.State A) : Prop := |
| 70 | @Sentence.Realize _ A (SOBlock.structure₁ (L := L) spec.B ρ) spec.src |
| 71 | |
| 72 | /-- A state is accepting when it satisfies the target sentence. -/ |
| 73 | def IsTgt (ρ : spec.State A) : Prop := |
| 74 | @Sentence.Realize _ A (SOBlock.structure₁ (L := L) spec.B ρ) spec.tgt |
| 75 | |
| 76 | variable (A) in |
| 77 | /-- The structure is accepted: some accepting state is reachable from some |
| 78 | starting state. No order on `A` is involved. -/ |
| 79 | def Accepts : Prop := |
| 80 | ∃ ρ σ : spec.State A, spec.IsSrc ρ ∧ spec.IsTgt σ ∧ spec.Reach ρ σ |
| 81 | |
| 82 | end Semantics |
| 83 | |
| 84 | end SOTCSpecFree |
| 85 | |
| 86 | /-- A decision problem is *order-free SO(TC) definable* if it is defined by an |
| 87 | `SOTCSpecFree` on nonempty finite structures – with **no linear order in the |
| 88 | statement at all**, unlike `SOTCDefinable`. -/ |
| 89 | def SOTCDefinableFree {L : Language.{0, 0}} [L.IsRelational] (P : DecisionProblem L) : Prop := |
| 90 | ∃ spec : SOTCSpecFree L, |
| 91 | ∀ (A : Type) [L.Structure A] [Finite A] [Nonempty A], P A ↔ spec.Accepts A |
| 92 | |
| 93 | end Lax134656.OrderFreeTransitiveClosure |
| 94 |
Builds on
Used by
Lax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrder
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments