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

Lax132576.WeightedCodes

Codes of weighted automata over the rationals

concepts/Lax132576/WeightedCodes.lean · lax-132576

definition

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

    In the paper

    Definition

    The decision problems of Section B.3 of Transducers — equivalence and zeroness of weighted automata over the field of rationals — are about algorithms whose inputs are weighted automata. A weighted automaton over Q\mathbb{Q} with states and letters in N\mathbb{N} is described by a finite code: its transitions (p,u,(a,b),q)(p, u, (a, b), q), from pp to qq, reading uu, with weight a/ba / b given by an integer and a natural number, and its lists of initial and final states. A code is valid if the automaton it describes is a genuine weighted automaton, i.e. every input string has finitely many accepting runs; validity is the promise under which the decision procedures of Theorems B.3.3 and B.3.7 are correct.

    Lean source view on GitHub

    1import Mathlib.Computability.Halting
    2import Mathlib.Data.Rat.Defs
    3import Lax132576.WeightedAutomata
    4
    5/-!
    6---
    7title: Codes of weighted automata over the rationals
    8type: definition
    9---
    10The decision problems of Section B.3 of *Transducers* — equivalence and
    11zeroness of weighted automata over the field of rationals — are about
    12algorithms whose inputs are weighted automata. A weighted automaton over
    13Q\mathbb{Q} with states and letters in N\mathbb{N} is described by a finite
    14*code*: its transitions (p,u,(a,b),q)(p, u, (a, b), q), from pp to qq, reading uu, with
    15weight a/ba / b given by an integer and a natural number, and its lists of
    16initial and final states. A code is *valid* if the automaton it describes is a
    17genuine weighted automaton, i.e. every input string has finitely many accepting
    18runs; validity is the promise under which the decision procedures of Theorems
    19B.3.3 and B.3.7 are correct.
    20
    21# Formalization notes
    22
    23`WCode` is a structure with the three lists as named fields and is
    24`Primcodable` through the evident bijection with a tuple. The weight of a coded
    25transition is the rational number `a / b`; a zero denominator gives the weight
    26`0`, as division by zero does in mathlib.
    27-/
    28
    29namespace Lax132576.WeightedCodes
    30
    31open Lax132576.LabelledAutomata Lax132576.WeightedAutomata
    32
    33/-- A code of a weighted automaton over `ℚ`: transitions `(p, u, (a, b), q)` from
    34`p` to `q` reading `u` with weight `a / b`, and the initial and final states. -/
    35structure WCode where
    36 /-- The transitions `(p, u, (a, b), q)`. -/
    37 transitions : List (ℕ × List ℕ × (ℤ × ℕ) × ℕ)
    38 /-- The initial states. -/
    39 init : List ℕ
    40 /-- The final states. -/
    41 final : List ℕ
    42
    43/-- A code is the tuple of its three lists. -/
    44def wcodeEquiv : WCode ≃ List (ℕ × List ℕ × (ℤ × ℕ) × ℕ) × List ℕ × List ℕ where
    45 toFun c := (c.transitions, c.init, c.final)
    46 invFun x := ⟨x.1, x.2.1, x.2.2
    47 left_inv := by rintro ⟨t, i, f⟩; rfl
    48 right_inv := by rintro ⟨t, i, f⟩; rfl
    49
    50instance : Primcodable WCode := Primcodable.ofEquiv _ wcodeEquiv
    51
    52/-- The weighted automaton over `ℚ` described by a code. -/
    53def wcodeAut (c : WCode) : LabAut ℕ ℚ ℕ where
    54 init := {q | q ∈ c.init}
    55 final := {q | q ∈ c.final}
    56 δ := {t | ∃ s ∈ c.transitions, t = (s.1, s.2.1, (s.2.2.1.1 : ℚ) / (s.2.2.1.2 : ℚ), s.2.2.2)}
    57 δ_finite := Set.Finite.ofFinset
    58 (c.transitions.toFinset.image
    59 (fun s => (s.1, s.2.1, (s.2.2.1.1 : ℚ) / (s.2.2.1.2 : ℚ), s.2.2.2)))
    60 (by intro t; simp [eq_comm])
    61
    62/-- The function computed by the weighted automaton described by a code. -/
    63noncomputable def wcodeEval (c : WCode) : List ℕ → ℚ := wEval (wcodeAut c)
    64
    65/-- A code is valid if it describes a genuine weighted automaton: every input has
    66finitely many accepting runs. -/
    67def WCodeValid (c : WCode) : Prop := FinitelyManyRuns (wcodeAut c)
    68
    69end Lax132576.WeightedCodes
    70

    Formalization notes

    WCodeWCode is a structure with the three lists as named fields and is PrimcodablePrimcodable through the evident bijection with a tuple. The weight of a coded transition is the rational number a/ba / b; a zero denominator gives the weight 00, as division by zero does in mathlib.

    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…