# Rogério Reis

## Err and err and err again, but less and less and less.

14-10-2013

Lecturer: Rogério Reis

• Formal languages.
• Operations on languages.
• Regular languages.
• Regular expressions.
• Deterministic finite automata (DFA).
• Non-deterministic finite automata.
• NFA to DFA conversion.
• Operations on NFAs.
• Regular expression equivalent to a NFA (Brzozowski state elimination algorithm).
• Regular expression to NFA conversion (the Thompson automaton).
• Uniqueness of the minimum DFA (state distinguishability).
• Minimisation algorithms: Moore, Hopcroft and Brzozowski.
Bibliography
John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. ISBN 0-201-02988.
Subjects of this class can be found in Chapter 2 of Hopcroft & Ullman book (pages 13 to 54)
Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. ISBN 978-0-521-84425-3
21-10-2013

Lecturer: Rogério Reis

• The Myhill-Nerode Theorem
• The "Pumping Lemma" for regular languages and its applications.
• The product semi-automaton. Reunion, intersection and complementation operations in automata.
• Proportional removal and cycle shift operations are closed for regular expressions.
• The notion of derivative of a regular expression with respect to one symbol.
• The Brzozowski derivative DFA of a regular expression.
• The Glushkov nondeterministic automaton of a regular expression.
• The notion of partial derivative of a regular expression with respect to a symbol.
• The Antimirov nondeterministic automaton of a regular expression.
• Antimirov algorithm to test the equivalence of two regular expressions.
• Very brief introduction to Analytic Combinatorics and its application to Descriptional Complexity.
Bibliography
Myhill-Nerode Theorem, Pumping Lemma and the product and complementary automata constructions can be studied in Hopcroft & Ullman' s book.
Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2009. ISBN 798-0-521-86572-2
Regular Languages Class closure for Proportional Removal and Cyclic Shift operations can be seen in this book (pages 58-61).
A brief description of Glushkov and Antimirov automata can be studied here and here. A description and discussion of Antimirov's algorithm to compare regular expressions can be studied here. A brief introduction to Analytics Combinatorics and its application to Descriptional Complexity can be seen here. A paper with the main results of state complexity on Finite Automata is available here.

## Descriptional Complexity DataBase (DesCo)

28-10-2013

Lecturer: Nelma Moreira

• Relations on words.
• Operations on relations: boolean, inverse, composition.
• Regular relations on words.
• Transducers over two alphabets.
• Synchronous and literal transducers.
• Composition of transducers.
• Sequential transducers .
• Determinization and conditions for a transducer to be determinizable.
• Normalization of sequential transducers.
• Minimization of sequential transducers.
• Semirings. Complete semirings.
• Weighted automata and transducers
• Regulated weighted transducers
• Regular operations on transducers
• Composition of transducers over complete semirings (and without epsilon-paths)
• Determinization of weighted automata over a weakly divisible semiring
• Weight pushing
• Minimization of weighted automata
Bibliography
Handbook of Weighted Automata
Editors:
• Manfred Droste,
• Werner Kuich,
• Heiko Vogler

ISBN: 978-3-642-01491-8 , Springer, 2009

Chap. Weighted Automata Algorithms, Mehryar Mohri
04-11-2013

Lecturer: Sabine Broda

• Model checking.
• Linear temporal logic (LTL).
• Transition systems and Kripke models.
• LTL semantics.
• Properties specification in LTL.
• Semantic equivalence in LTL.
• Complete set of connectives.
• Model checking example: mutual exclusion. Specification of models and properties.
• Non-deterministic finite automata and Büchi automata.
• Alternating finite automata.
• Alternating Büchi automata for a LTL formula and models.
• Automata based model checking algorithm for LTL.
Bibliography
Logic in Computer Science: Modelling and reasoning about systems,
Michael Huth and Mark Ryan
Cambridge University Press, 2004

Chapters: 3.2-3.3
An Automata-Theoretic Approach to Linear Temporal Logic, Moshe Y. Vardi. Logics for Concurrency
Lecture Notes in Computer Science Volume 1043, 1996, pp 238-266.

Some exercises on this subject.
10-11-2013
• The notion of cellular automata.
• Conway's "Game of Life" and its universality.
• Linear cellular automata and graphs.
• Unidimentional cellular automata: Wolfram coding.
• Bidimensional Cellular automata. Totalistic and outer-totalistic rules and their numeric coding.
• Reversible automata. Classification of all linear reversible finite cellular automata with support on $P_n$ graph over $\mathbb{Z}_2$ and $\mathbb{Z}_3$.
• Wolfram cipher and the PKC system proposed by P.Guan.
Bibliography
Andrew Ilachinski.
Cellular Automata: a Discrete Universe. World Scientific, 2001.
Stephen Wolfram, Cryptography with Cellular Automata, in "Advances in Cryptology: CRYPTO '85 Proceedings" [Williams, H. C. (Ed.)]. Lecture Notes in Computer Science 218. Springer-Verlag, 429–432, 1986.

Puhua Guan, Cellular Automaton Public-Key Cryptosystem, Complex Systems 1 (1987) 51-57.