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

Lax916827.RegularOfTwoWay

Every two-way transducer computes a regular function

concepts/Lax916827/RegularOfTwoWay.lean · lax-916827

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 function computed by a two-way transducer is regular, i.e. decomposes into rational functions, map reverse and map duplicate (Theorem C.2.9 of Transducers, the hard implication). The run of the transducer is described by its snake graph, computed by a rational function, and the output of a snake graph of width at most kk is a regular function of its representation (the snake lemma, Lemma C.2.12), by induction on the width: a snake of width kk is cut, at the record-breaking columns, into looping and progressing parts of smaller width, whose outputs are computed by the induction hypothesis on factors cut out by rational functions and glued back by the closure properties of Lemma C.2.10. A run that halts visits every column at most Q|Q| times, so the transducer's function is its own width-Q|Q| snake output.

    Lean source view on GitHub

    1import Lax916827.RegularFunctions
    2import Lax916827.TwoWayTransducers
    3
    4/-!
    5---
    6title: Every two-way transducer computes a regular function
    7type: theorem
    8---
    9Every function computed by a two-way transducer is regular, i.e. decomposes
    10into rational functions, map reverse and map duplicate (Theorem C.2.9 of
    11*Transducers*, the hard implication). The run of the transducer is described by
    12its *snake graph*, computed by a rational function, and the output of a snake
    13graph of width at most kk is a regular function of its representation (the
    14snake lemma, Lemma C.2.12), by induction on the width: a snake of width kk is
    15cut, at the record-breaking columns, into looping and progressing parts of
    16smaller width, whose outputs are computed by the induction hypothesis on factors
    17cut out by rational functions and glued back by the closure properties of
    18Lemma C.2.10. A run that halts visits every column at most Q|Q| times, so the
    19transducer's function is its own width-Q|Q| snake output.
    20
    21# Formalization notes
    22
    23Both alphabets are assumed finite, as in the book.
    24-/
    25
    26namespace Lax916827.RegularOfTwoWay
    27
    28open Lax916827.RegularFunctions Lax916827.TwoWayTransducers
    29
    30/-- A function computed by a two-way transducer is regular. -/
    31axiom isRegularFun_of_isTwoWay {A B : Type} [Finite A] [Finite B] {f : List A → List B}
    32 (hf : IsTwoWay f) : IsRegularFun f
    33
    34end Lax916827.RegularOfTwoWay
    35
    Show Proof

    Formalization notes

    Both alphabets are assumed finite, as in the book.

    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…