Filip Mazowiecki Papers Slides Course

This is the webpage of the Automata and sequences course given by Filip Mazowiecki and Joël Ouaknine. The tutorials are given by Toghrul Karimov.

  • The lectures are on Mondays at 10am. The tutorials are on Fridays at 11am.

  • All on Zoom https://zoom.us/j/91551010384

  • Previous recordings on BBB https://bbb.mpi-klsb.mpg.de/b/fil-47n-h9e

  • Course description

    • Finite automata are one of the models that describe regular languages. One can think that they define languages by providing function from the set of words to the set {0,1}, where 1 means that the word is accepted and 0 means that the word is rejected. Weighted automata are a quantitative variant of the finite automata model, where we assign to each word numbers from a different domain, like natural numbers. The course is about expressiveness and algorithmic properties of weighted automata and a related class of linear recursive sequences. Here are examples for both models:
    - Weighted automata. An automaton A can count the number of a's and then for example A(abbaa) = 3.
    - Linear recursive sequences. For example the Fibonacci sequence 0,1,1,2,3,5,8,13,... where the first two elements are 0 and 1 and the next elements are defined as the sum of two preceding elements.

  • Requirements

    • I assume basic knowledge of finite automata theory (regular languages etc), basic complexity theory (what does it mean to be decidable in PSPACE or in NP), and basic properties of linear recursive sequences (like the characterisitic polynomial).

  • Lecture slides

    1. Weighted automata definitions [slides]
    2. Linear recursive sequences [slides]
    3. Ambiguity of automata [slides] and the paper on which it's based
    4. Ambiguity for 1-letter alphabets [slides] and one of the papers on which it's based
    5. Ambiguity for max-plus semiring and decision problems [slides] and one of the papers on which it's based
    6. Skolem Mahler Lech theorem [notes]
    7. The Skolem problem for LRS of order 2 and 3 [notes]
    8. NP-hardness of Skolem and decision problems for weighted automata [slides]
    9. Equivalence of weighted automata over fields [slides]

  • Exercises for May 15th [pdf]
  • Exercises for May 22nd [pdf]
  • Exercises for May 29th [pdf]
  • Exercises for June 12th [pdf]
  • Exercises for June 19th [pdf]
  • Exercises for July 3rd [pdf]
  • Exercises for July 10th [pdf]