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

Lax132576.RationalMealyCharacterisation

Which rational functions are Mealy machines

concepts/Lax132576/RationalMealyCharacterisation.lean · lax-132576

proven

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.

    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

    A rational function f:ABf : A^* \to B^* is computed by a Mealy machine if and only if it is letter-to-letter — the output has the length of the input — and deterministic: input strings that agree on their first nn letters have outputs that agree on their first nn letters (Theorem B.2.7 of Transducers). Mealy machines are the special case of the rational functions that the theorem pins down; the proof goes through the machine-independent characterisation of Theorem B.4.1, since a rational function is continuous.

    Lean source view on GitHub

    1import Lax765601.MealyMachine
    2import Lax765601.ElementaryProperties
    3import Lax132576.RationalFunctions
    4
    5/-!
    6---
    7title: Which rational functions are Mealy machines
    8type: theorem
    9---
    10A rational function f:ABf : A^* \to B^* is computed by a Mealy machine if and only
    11if it is letter-to-letter — the output has the length of the input — and
    12deterministic: input strings that agree on their first nn letters have outputs
    13that agree on their first nn letters (Theorem B.2.7 of *Transducers*). Mealy
    14machines are the special case of the rational functions that the theorem
    15pins down; the proof goes through the machine-independent characterisation of
    16Theorem B.4.1, since a rational function is continuous.
    17
    18# Formalization notes
    19
    20"Letter-to-letter" is `LengthPreserving` and "deterministic" is
    21`PrefixDetermined` of `Lax765601.ElementaryProperties`. Both alphabets are
    22assumed finite, as Theorem B.4.1 needs.
    23-/
    24
    25namespace Lax132576.RationalMealyCharacterisation
    26
    27open Lax765601.MealyMachine Lax765601.ElementaryProperties Lax132576.RationalFunctions
    28
    29/-- A rational function is computed by a Mealy machine if and only if it is
    30letter-to-letter and prefix determined. -/
    31axiom isMealy_iff_of_isRationalFun {A B : Type} [Finite A] [Finite B] {f : List A → List B}
    32 (hf : IsRationalFun f) : IsMealy f ↔ LengthPreserving f ∧ PrefixDetermined f
    33
    34end Lax132576.RationalMealyCharacterisation
    35
    Show Proof

    Formalization notes

    "Letter-to-letter" is LengthPreservingLengthPreserving and "deterministic" is PrefixDeterminedPrefixDetermined of Lax765601.ElementaryPropertiesLax765601.ElementaryProperties. Both alphabets are assumed finite, as Theorem B.4.1 needs.

    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…