Lax132576.Uniformisation
Uniformisation of total rational relations
concepts/Lax132576/Uniformisation.lean · lax-132576
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 47 of the paper of lax-157538, Transducers
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 of the set of states that can still reach acceptance, chosen deterministically from right to left, and the minimal state 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
| 1 | import Lax132576.RationalRelations |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Uniformisation of total rational relations |
| 6 | type: theorem |
| 7 | --- |
| 8 | If a rational relation is total — every input string has at least one output — |
| 9 | then it contains an unambiguous rational relation (Lemma B.2.5 of |
| 10 | *Transducers*). After eliminating ε-transitions, the unambiguous automaton |
| 11 | follows the run of the original automaton that is lexicographically minimal |
| 12 | for a chosen linear order on the states: its states are pairs of the |
| 13 | set of states that can still reach acceptance, chosen deterministically |
| 14 | from right to left, and the minimal state reachable so far, chosen |
| 15 | deterministically from left to right; the output of a transition is one chosen |
| 16 | output of the original automaton between its two states on its letter. |
| 17 | |
| 18 | # Formalization notes |
| 19 | |
| 20 | The contained relation `S` is unambiguous in the sense of `IsUnambiguousRel`, |
| 21 | and `S ⊆ R` is stated pointwise. Both alphabets are assumed finite. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax132576.Uniformisation |
| 25 | |
| 26 | open Lax132576.RationalRelations |
| 27 | |
| 28 | /-- A total rational relation contains an unambiguous rational relation. -/ |
| 29 | axiom 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 | |
| 33 | end Lax132576.Uniformisation |
| 34 |
Formalization notes
The contained relation is unambiguous in the sense of , and is stated pointwise. Both alphabets are assumed finite.
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