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

Lax132576.Uniformisation

Uniformisation of total rational relations

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

    If a rational relation is total — every input string has at least one output — then it contains an unambiguous rational relation (Lemma B.2.5 of Transducers). After eliminating ε-transitions, the unambiguous automaton follows the run of the original automaton that is lexicographically minimal for a chosen linear order on the states: its states are pairs PpP \ni p of the set PP of states that can still reach acceptance, chosen deterministically from right to left, and the minimal state pPp \in P reachable so far, chosen deterministically from left to right; the output of a transition is one chosen output of the original automaton between its two states on its letter.

    Lean source view on GitHub

    1import Lax132576.RationalRelations
    2
    3/-!
    4---
    5title: Uniformisation of total rational relations
    6type: theorem
    7---
    8If a rational relation is total — every input string has at least one output —
    9then it contains an unambiguous rational relation (Lemma B.2.5 of
    10*Transducers*). After eliminating ε-transitions, the unambiguous automaton
    11follows the run of the original automaton that is lexicographically minimal
    12for a chosen linear order on the states: its states are pairs PpP \ni p of the
    13set PP of states that can still reach acceptance, chosen deterministically
    14from right to left, and the minimal state pPp \in P reachable so far, chosen
    15deterministically from left to right; the output of a transition is one chosen
    16output of the original automaton between its two states on its letter.
    17
    18# Formalization notes
    19
    20The contained relation `S` is unambiguous in the sense of `IsUnambiguousRel`,
    21and `S ⊆ R` is stated pointwise. Both alphabets are assumed finite.
    22-/
    23
    24namespace Lax132576.Uniformisation
    25
    26open Lax132576.RationalRelations
    27
    28/-- A total rational relation contains an unambiguous rational relation. -/
    29axiom exists_isUnambiguousRel_le {A B : Type} [Finite A] [Finite B]
    30 {R : List A → List B → Prop} (hR : IsRationalRel R) (htotal : ∀ w, ∃ v, R w v) :
    31 ∃ S : List A → List B → Prop, (∀ w v, S w v → R w v) ∧ IsUnambiguousRel S
    32
    33end Lax132576.Uniformisation
    34
    Show Proof

    Formalization notes

    The contained relation SS is unambiguous in the sense of IsUnambiguousRelIsUnambiguousRel, and SRS ⊆ R is stated pointwise. Both alphabets are assumed finite.

    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…