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

Lax916827.RegularOfSST

Every streaming string transducer computes a regular function

concepts/Lax916827/RegularOfSST.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 streaming string transducer is regular (Theorem C.3.2 of Transducers, the implication from sst to regular). The sst is first normalised — the register update depends only on the letter read, and no register occurs twice in a final output string — by annotating the input with the states through a rational function; a two-way transducer then expands the final output string depth-first, moving left to expand a register and right when an expansion is finished, the copyless restriction making the place to resume an expansion a function of the register and the letter returned to. Two-way transducers compute regular functions (Theorem C.2.9).

    Lean source view on GitHub

    1import Lax916827.RegularFunctions
    2import Lax916827.StreamingStringTransducers
    3
    4/-!
    5---
    6title: Every streaming string transducer computes a regular function
    7type: theorem
    8---
    9Every function computed by a streaming string transducer is regular (Theorem
    10C.3.2 of *Transducers*, the implication from sst to regular). The sst is first
    11normalised — the register update depends only on the letter read, and no
    12register occurs twice in a final output string — by annotating the input with
    13the states through a rational function; a two-way transducer then expands the
    14final output string depth-first, moving left to expand a register and right when
    15an expansion is finished, the copyless restriction making the place to resume
    16an expansion a function of the register and the letter returned to. Two-way
    17transducers compute regular functions (Theorem C.2.9).
    18
    19# Formalization notes
    20
    21Both alphabets are assumed finite, as in the book.
    22-/
    23
    24namespace Lax916827.RegularOfSST
    25
    26open Lax916827.RegularFunctions Lax916827.StreamingStringTransducers
    27
    28/-- A function computed by a streaming string transducer is regular. -/
    29axiom isRegularFun_of_isSST {A B : Type} [Finite A] [Finite B] {f : List A → List B}
    30 (hf : IsSST f) : IsRegularFun f
    31
    32end Lax916827.RegularOfSST
    33
    Show Proof

    Formalization notes

    Both alphabets are assumed finite, as in the book.

    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…