While this submission is a draft, it cannot be used by other submissions.

Resolutions and bounded profiles

Lax369799.Resolutions · concepts/Lax369799/Resolutions.lean · lax-369799

definition

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.

    Natural Language Statement

    Definition

    A resolution consists of a system and a map from its variables to those of the target set-system, such that the renamed system maps into the target. A flatten-resolution resolves both the outer pattern and its labels, keeping track of a separate variable map at each vertex (Section 2.9).

    For a recognising evaluation, a profile records the values and variable maps of resolutions. A map is small when each fibre has at most ∣B0∣+∣B1∣+1|B₀| + |B₁| + 1 elements, accounting for closed continuations, unary continuations, and the immediate exit. This is the bound b_A in the revised Section 4.3. Small profiles and small root profiles are the finite summaries used there.

    Concept map
    5 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax369799.Algebras
    2import Mathlib.SetTheory.Cardinal.Finite
    3
    4/-!
    5---
    6title: Resolutions and bounded profiles
    7type: definition
    8---
    9A resolution consists of a system and a map from its variables to those of
    10the target set-system, such that the renamed system maps into the target.
    11A flatten-resolution resolves both the outer pattern and its labels,
    12keeping track of a separate variable map at each vertex (Section 2.9).
    13
    14For a recognising evaluation, a profile records the values and variable
    15maps of resolutions. A map is small when each fibre has at most
    16`|B₀| + |B₁| + 1` elements, accounting for closed continuations, unary
    17continuations, and the immediate exit. This is the bound b_A in the
    18revised Section 4.3. Small profiles and small root profiles are the finite
    19summaries used there.
    20-/
    21
    22namespace Lax369799.Resolutions
    23open RankedSystems Morphisms Flattening Algebras
    24
    25def rename {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n)
    26 (S : SetSystem A m) : SetSystem A n where
    27 size := S.size
    28 graph := {
    29 label := S.graph.label
    30 initial := S.graph.initial
    31 root := S.graph.root
    32 edge := fun v d t => ∃ s, S.graph.edge v d s ∧ t = Sum.map id σ s
    33 direction_valid := by
    34 rintro v d t ⟨s, hs, _⟩
    35 exact S.graph.direction_valid v d s hs }
    36 reachable := by
    37 intro v
    38 obtain ⟨r, hr, hp⟩ := S.reachable v
    39 refine ⟨r, hr, Relation.ReflTransGen.mono ?_ r v hp⟩
    40 rintro a b ⟨d, hd⟩
    41 exact ⟨d, .inl b, hd, rfl⟩
    42
    43def IsResolution {A : RankedSet} {m n : ℕ} (S : SetSystem A n)
    44 (T : System A m) (σ : Fin m → Fin n) : Prop :=
    45 Nonempty (Morphism (rename σ T.val) S)
    46
    47structure FlattenResolution {A : RankedSet} {n : ℕ}
    48 (S : SetSystem (SetSystem A) n) (T : System (System A) n) where
    49 vertex : T.val.Vertex → S.Vertex
    50 variableMap : ∀ v, Fin (T.val.graph.label v).1 → Fin (S.graph.label (vertex v)).1
    51 initial : ∀ v, v ∈ T.val.graph.initial → vertex v ∈ S.graph.initial
    52 resolves : ∀ v, IsResolution (Inner S (vertex v)) (T.val.graph.label v).2 (variableMap v)
    53 transition : ∀ v (i : Fin (T.val.graph.label v).1) w,
    54 T.val.graph.edge v i.val (.inl w) → S.graph.edge (vertex v) (variableMap v i).val (.inl (vertex w))
    55 exit : ∀ v (i : Fin (T.val.graph.label v).1) j,
    56 T.val.graph.edge v i.val (.inr j) → S.graph.edge (vertex v) (variableMap v i).val (.inr j)
    57
    58abbrev ProfileEntry (B : RankedSet) (n : ℕ) := (m : ℕ) × B m × (Fin m → Fin n)
    59
    60noncomputable def SmallBound (B : RankedSet) : ℕ := Nat.card (B 0) + Nat.card (B 1) + 1
    61
    62def SmallMap (B : RankedSet) {m n : ℕ} (σ : Fin m → Fin n) : Prop :=
    63 ∀ j, Nat.card {i // σ i = j} ≤ SmallBound B
    64
    65def Profile {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ}
    66 (S : SetSystem A n) : Set (ProfileEntry B n) :=
    67 {e | ∃ T : System A e.1, IsResolution S T e.2.2 ∧ ρ e.1 T = e.2.1}
    68
    69def SmallProfile {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ}
    70 (S : SetSystem A n) : Set (ProfileEntry B n) :=
    71 {e | e ∈ Profile ρ S ∧ SmallMap B e.2.2}
    72
    73def ProfileEquivalent {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ}
    74 (S T : SetSystem A n) : Prop :=
    75 Profile ρ S = Profile ρ T ∧ Profile ρ (uproot S) = Profile ρ (uproot T)
    76
    77def SmallProfileEquivalent {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ}
    78 (S T : SetSystem A n) : Prop :=
    79 SmallProfile ρ S = SmallProfile ρ T ∧ SmallProfile ρ (uproot S) = SmallProfile ρ (uproot T)
    80
    81end Lax369799.Resolutions
    82

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…