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 in Zoom 769 838 6113
  • The tutorials are on Fridays at 11am in Zoom 967 3521 8730
  • 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

  • Exercises for 15th of May [pdf]
  • Exercises for 22nd of May [pdf]
  • Exercises for 29th of May [pdf]