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
Stacks Image 2445
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)
Stacks Image 2451
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.
Stacks Image 2483
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
Stacks Image 2549
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
Stacks Image 2611
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
Stacks Image 2602
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.