Lax132576.WeightedCodes
Codes of weighted automata over the rationals
concepts/Lax132576/WeightedCodes.lean · lax-132576
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 61 of the paper of lax-157538, Transducers
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 with states and letters in is described by a finite code: its transitions , from to , reading , with weight 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
| 1 | import Mathlib.Computability.Halting |
| 2 | import Mathlib.Data.Rat.Defs |
| 3 | import Lax132576.WeightedAutomata |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Codes of weighted automata over the rationals |
| 8 | type: definition |
| 9 | --- |
| 10 | The decision problems of Section B.3 of *Transducers* — equivalence and |
| 11 | zeroness of weighted automata over the field of rationals — are about |
| 12 | algorithms whose inputs are weighted automata. A weighted automaton over |
| 13 | with states and letters in is described by a finite |
| 14 | *code*: its transitions , from to , reading , with |
| 15 | weight given by an integer and a natural number, and its lists of |
| 16 | initial and final states. A code is *valid* if the automaton it describes is a |
| 17 | genuine weighted automaton, i.e. every input string has finitely many accepting |
| 18 | runs; validity is the promise under which the decision procedures of Theorems |
| 19 | B.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 |
| 25 | transition is the rational number `a / b`; a zero denominator gives the weight |
| 26 | `0`, as division by zero does in mathlib. |
| 27 | -/ |
| 28 | |
| 29 | namespace Lax132576.WeightedCodes |
| 30 | |
| 31 | open 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. -/ |
| 35 | structure 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. -/ |
| 44 | def 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 | |
| 50 | instance : Primcodable WCode := Primcodable.ofEquiv _ wcodeEquiv |
| 51 | |
| 52 | /-- The weighted automaton over `ℚ` described by a code. -/ |
| 53 | def 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. -/ |
| 63 | noncomputable def wcodeEval (c : WCode) : List ℕ → ℚ := wEval (wcodeAut c) |
| 64 | |
| 65 | /-- A code is valid if it describes a genuine weighted automaton: every input has |
| 66 | finitely many accepting runs. -/ |
| 67 | def WCodeValid (c : WCode) : Prop := FinitelyManyRuns (wcodeAut c) |
| 68 | |
| 69 | end Lax132576.WeightedCodes |
| 70 |
Formalization notes
is a structure with the three lists as named fields and is through the evident bijection with a tuple. The weight of a coded transition is the rational number ; a zero denominator gives the weight , 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