Lax Lean Archive

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

Lax194892.BalancedRunReachability

Balanced runs between configurations are regular

concepts/Lax194892/BalancedRunReachability.lean · lax-194892

proven

Loading review…

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

    Each proof establishes this claim relative to its assumptions.

    In the paper

    Theorem

    For every height ℓ∈{1,…,k}\ell \in \{1, \ldots, k\}, the existence of a balanced run between two configurations (x,y1)(x, y_1) and (x,y2)(x, y_2) of height ℓ\ell — sharing the stack xx of the lower ℓ−1\ell - 1 pebbles, with yiy_i the state and the position of the top pebble — is mso-definable (Claim D.2.3 of Transducers): during a balanced run the pebble at height ℓ\ell is never popped, although it may be moved.

    Lean source view on GitHub

    1import Mathlib.Computability.DFA
    2import Lax194892.PebbleConfigurationEncoding
    3
    4/-!
    5---
    6title: Balanced runs between configurations are regular
    7type: theorem
    8---
    9For every height ℓ∈{1,…,k}\ell \in \{1, \ldots, k\}, the existence of a *balanced
    10run* between two configurations (x,y1)(x, y_1) and (x,y2)(x, y_2) of height ℓ\ell —
    11sharing the stack xx of the lower ℓ−1\ell - 1 pebbles, with yiy_i the state
    12and the position of the top pebble — is mso-definable (Claim D.2.3 of
    13*Transducers*): during a balanced run the pebble at height ℓ\ell is never
    14popped, although it may be moved.
    15
    16# Formalization notes
    17
    18As for Lemma D.2.2, the mso formula is replaced by a regular language of
    19encodings of the pair of configurations, correct on genuine encodings; the two
    20stacks are `x ++ [p₁]` and `x ++ [p₂]` with `x` of length `ℓ - 1`.
    21-/
    22
    23namespace Lax194892.BalancedRunReachability
    24
    25open Lax194892.PebbleTransducers Lax194892.PebbleConfigurationEncoding
    26
    27/-- The encodings of pairs of configurations of height `ℓ` connected by a balanced
    28run form a regular language. -/
    29axiom exists_regular_balancedLang {A B Q : Type} {k : ℕ} [Finite A] [Finite Q]
    30 (M : Pebble A B Q k) (ℓ : ℕ) (hℓ1 : 1 ≤ ℓ) (hℓk : ℓ ≤ k) :
    31 ∃ L : Language (PairLetter A Q k), L.IsRegular ∧
    32 ∀ (q₁ q₂ : Q) (x : List ℕ) (p₁ p₂ : ℕ) (w : List A),
    33 (∀ p ∈ x, p ≤ w.length) → p₁ ≤ w.length → p₂ ≤ w.length → x.length = ℓ - 1 →
    34 (pairEnc q₁ q₂ (x ++ [p₁]) (x ++ [p₂]) w ∈ L ↔
    35 BalancedRun M w ℓ (PebbleCfg.conf q₁ (x ++ [p₁])) (PebbleCfg.conf q₂ (x ++ [p₂])))
    36
    37end Lax194892.BalancedRunReachability
    38
    Show Proof

    Formalization notes

    As for Lemma D.2.2, the mso formula is replaced by a regular language of encodings of the pair of configurations, correct on genuine encodings; the two stacks are x++[p1]x ++ [p₁] and x++[p2]x ++ [p₂] with xx of length ℓ−1ℓ - 1.

    Builds on

    Used by

    none

    From Mathlib

    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…