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.

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

Applied combinatorics on words, M. Lothaire CUP, 2005 ISBN: 9780521848022

Chapter 1 (transducers: pp 39-50)

Chapter 1 (transducers: pp 39-50)

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

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

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.

Lecture Notes in Computer Science Volume 1043, 1996, pp 238-266.

Some exercises on this subject.

10-11-2013

Lecturer: António Machiavelo

- 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.

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.

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