Lax Lean Archive

Aperiodic bimachines compute first-order relabellings

Lax314295.FORelabellingOfAperiodicBimachine · concepts/Lax314295/FORelabellingOfAperiodicBimachine.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 function computed by an aperiodic bimachine is a first-order relabelling (Theorem C.4.16 of Transducers, the implication from bimachine to relabelling). By Theorem C.4.11 the runs of the two aperiodic automata are described in first-order logic: for each pair of a transition of the prefix automaton and one of the suffix automaton there is a first-order formula selecting the positions at which they are used, and the output map is the output function 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: Aperiodic bimachines compute first-order relabellings
    7type: theorem
    8---
    9Every function computed by an aperiodic bimachine is a first-order
    10relabelling (Theorem C.4.16 of *Transducers*, the implication from bimachine to
    11relabelling). By Theorem C.4.11 the runs of the two aperiodic automata are
    12described in first-order logic: for each pair of a transition of the prefix
    13automaton and one of the suffix automaton there is a first-order formula
    14selecting the positions at which they are used, and the output map is the
    15output function of the bimachine.
    16
    17# Formalization notes
    18
    19Both alphabets are assumed finite, as in the book.
    20-/
    21
    22namespace Lax314295.FORelabellingOfAperiodicBimachine
    23
    24open Lax132576.Bimachines Lax314295.MSORelabellings
    25
    26/-- A function computed by an aperiodic bimachine is a first-order relabelling. -/
    27axiom isFORelabelling_of_isAperiodicBimachine {A B : Type} [Finite A] [Finite B]
    28 {f : List A → List B} (hf : IsAperiodicBimachine f) : IsFORelabelling f
    29
    30end Lax314295.FORelabellingOfAperiodicBimachine
    31
    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…