Lax Lean Archive

First-order relabellings are computed by aperiodic bimachines

Lax314295.AperiodicBimachineOfFORelabelling · concepts/Lax314295/AperiodicBimachineOfFORelabelling.lean · lax-314295

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.

    Natural Language Statement

    Theorem

    Every first-order relabelling is computed by an aperiodic bimachine (Theorem C.4.16 of Transducers, the implication from relabelling to bimachine). For a first-order formula with one free variable, the prefixes and the suffixes on which it holds at the marked position are first-order definable languages, recognised by aperiodic automata (Theorem C.4.11), which become the prefix and suffix automata of the bimachine.

    Concept map
    6 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    Lean source view on GitHub

    1import Lax132576.Bimachines
    2import Lax314295.MSORelabellings
    3
    4/-!
    5---
    6title: First-order relabellings are computed by aperiodic bimachines
    7type: theorem
    8---
    9Every first-order relabelling is computed by an aperiodic bimachine (Theorem
    10C.4.16 of *Transducers*, the implication from relabelling to bimachine). For a
    11first-order formula with one free variable, the prefixes and the suffixes on
    12which it holds at the marked position are first-order definable languages,
    13recognised by aperiodic automata (Theorem C.4.11), which become the prefix and
    14suffix automata of the bimachine.
    15
    16# Formalization notes
    17
    18Both alphabets are assumed finite, as in the book.
    19-/
    20
    21namespace Lax314295.AperiodicBimachineOfFORelabelling
    22
    23open Lax132576.Bimachines Lax314295.MSORelabellings
    24
    25/-- A first-order relabelling is computed by an aperiodic bimachine. -/
    26axiom isAperiodicBimachine_of_isFORelabelling {A B : Type} [Finite A] [Finite B]
    27 {f : List A → List B} (hf : IsFORelabelling f) : IsAperiodicBimachine f
    28
    29end Lax314295.AperiodicBimachineOfFORelabelling
    30
    Show Proof
    Formalization notes

    Both alphabets are assumed finite, as in the book.

    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…