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

Lax132576.BimachineOfRational

Rational functions are computed by bimachines

concepts/Lax132576/BimachineOfRational.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

    Every rational function is computed by a bimachine: the implication (1) ⇒ (3) of Theorem B.2.3 of Transducers (Eilenberg), through the unambiguous automaton of (2). Given an unambiguous automaton whose accepting runs end with a single empty-input transition, the bimachine's prefix automaton computes the states reachable from an initial state on the prefix, its suffix automaton computes the first letter of the suffix and the states that can reach acceptance on the rest, and the output function reads off the output of the unique transition consuming the letter at the gap — or of the final empty-input transition at the last gap.

    Lean source view on GitHub

    1import Lax132576.RationalFunctions
    2import Lax132576.Bimachines
    3
    4/-!
    5---
    6title: Rational functions are computed by bimachines
    7type: theorem
    8---
    9Every rational function is computed by a bimachine: the implication (1) ⇒ (3)
    10of Theorem B.2.3 of *Transducers* (Eilenberg), through the unambiguous
    11automaton of (2). Given an unambiguous automaton whose accepting runs end with
    12a single empty-input transition, the bimachine's prefix automaton computes the
    13states reachable from an initial state on the prefix, its suffix automaton
    14computes the first letter of the suffix and the states that can reach
    15acceptance on the rest, and the output function reads off the output of the
    16unique transition consuming the letter at the gap — or of the final
    17empty-input transition at the last gap.
    18
    19# Formalization notes
    20
    21Both alphabets are assumed finite, as the construction of the unambiguous
    22automaton needs.
    23-/
    24
    25namespace Lax132576.BimachineOfRational
    26
    27open Lax132576.RationalFunctions Lax132576.Bimachines
    28
    29/-- A rational function is computed by a bimachine. -/
    30axiom isBimachine_of_isRationalFun {A B : Type} [Finite A] [Finite B]
    31 {f : List A → List B} (hf : IsRationalFun f) : IsBimachine f
    32
    33end Lax132576.BimachineOfRational
    34
    Show Proof

    Formalization notes

    Both alphabets are assumed finite, as the construction of the unambiguous automaton needs.

    Used by

    none

    From Mathlib

    none

    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…