Weighted Automata and Transducers

---

Course Description

---

Notes

Math

• Semi Ring
  • Polynomial and matrices over semi rings form semi rings

Weighted Automata

• Multiplicity Automata
• Weighted Automata
  • Weighted Automata on Series
• Algorithm for Finding the Weight of a Word
• Threshold Languages
• Reachable Vectors
• Emptiness Of Support
• Reducing a Weighted Automata
  • Example for Reduction of Weighted Automata
• Transpose of a Weighted Automata
• Minimizing a Weighted Automata
• Equality in Tropical Weighted Automata
• L* Learning Algorithm
  • L* example
• Closure Properties of Recognizable functions

Algebraic Characterization of Rational Functions

• Weighted Automata as Formal Power Series
• Monomials, Polynomials and Series
  • Locally Finite and Summable Series
• Rational Series
  • Weighted Automata on Series
  • Arden’s Lemma
    • Choumsky Normal Form to Greibach Normal Form using Arden’s Lemma
• Kleene Shutzenberger Theorem
• Modules
  • Semi-Modules
  • Types of Modules
  • Stable Subsemodule of Series
• Algebraic Classification of Recognizable functions

Probabilistic Automata

• Probabilistic Automata
  • Stochastic Languages
  • Stochastic Languages are Regular if Threshold Point is Isolated
  • Stochastic Languages are Undecidable in General
  • Showing a Point is Isolated is Undecidable
    • Post Correspondence Problem
    • PCP’

Transducers

• Pure Sequential Transducers
  • Prefix Preserving
  • Mealy Machines and Moore Machines
• Sequential Transducers
• Image of a Regular Language under a Sequential Transducer is Regular
• Pre-Image of a Regular Language under a Sequential Transducer is Regular
• A Language if Regular iff its Characteristic Function is regular
• Composition of Sequential Transducers
• Normalizing a Transducer
  • Computing m_q
• Residuals using Longest Common Prefixes

Relations on Words

• Rational, Automatic and Recognizable relations
• Closure Properties of Rational Relations
• Equivalence of Rational Relations is Undecidable
• Rational Relations as Weighted Automata
• Checking if a word is related to Sigma*
• Nivat’s Theorem

Machines realising Rational Functions

• Rational Functions
• Machines Realising Rational Functions
• Equivalence between Machines

---

MOCs

• Algebraic Automata Theory

---

Practicle Information

• Professor : Aiswarya
• Timings : 9:10 MWF?
• Location: LH6

---

References