TCC-00.317 Computabilidade / Teoria da Computação - PGC

Sala 319, 2a. feira de 14:00 às 17:20.

Objetivo

Apresentar conceitos básicos de computabilidade.

Tópicos

1. Linguagens formais e autômatos
2. Máquinas de Turing
3. Tese de Church
4. Funções recursivas primitivas
5. Minimização
6. Funções recursivas parciais

Apresentação dos projetos

• P1 20/04/18 - Apresentação do projeto 1 - Teoria de autômatos finitos.
• P2 04/05/18 - Apresentação do projeto 2 - Máquinas de Turing (MT).
• P3 29/06/18 - Apresentação do projeto 3 - Funções recursivas parciais (FRP), FPR → MT, MT → FPR.

Apresentação dos seminários

23/03/18

• Büchi automata - Christel Baier and Joost-Pieter Katoen, Principles of Model Checking, Ch. 4.3, Automata on Infinite Words.
• Hybrid automata I - R. Alur, C. Courcoubetis, T.A. Henzinger, P.-H. Ho, Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems, Lecture Notes in Computer Science, 736, Springer-Verlag, New York/Berlin (1993), p. 209–229.

06/04/18

• Vardi M.Y. (2007) Automata-Theoretic Model Checking Revisited. In: Cook B., Podelski A. (eds) Verification, Model Checking, and Abstract Interpretation. VMCAI 2007. Lecture Notes in Computer Science, vol 4349. Springer, Berlin, Heidelberg
• Hybrid automata II - R.L. Grossman, A. Nerode, A.P. Ravn, H. Rischel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, 736, Springer-Verlag, New York/Berlin (1993), pp. 179-208

13/04/18

• Emmi M., Giannakopoulou D., Păsăreanu C.S. (2008) Assume-Guarantee Verification for Interface Automata. In: Cuellar J., Maibaum T., Sere K. (eds) FM 2008: Formal Methods. FM 2008. Lecture Notes in Computer Science, vol 5014. Springer, Berlin, Heidelberg
• Hybrid automata III - Thomas A.Henzinger, Peter W. Kopkeb, Anuj Puria Pravin Varaiyaa, What's Decidable about Hybrid Automata?, Journal of Computer and System Sciences, Volume 57, Issue 1, August 1998, Pages 94-124.

20/04/18, Junto com P1

• Javier Esparza, Orna Kupferman and Moshe Y. Vardi, Automata-Theoretic Verification, Manuscript (https://www.cs.rice.edu/~vardi/papers/hba11.pdf)
• Hybrid automata IV - Nancy Lynch, Roberto Segala, Frits Vaandrager, Hybrid I/O Automata. Information and Computation, volume 185(1), pages 103–157, 2003.

27/04/18

• Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230 - 265.

04/05/18, Junto com P2

11/05/18

18/05/18

25/05/18

08/06/18

15/06/18

22/06/18

29/06/18, Junto com P3

Critério de avaliação

[(Média dos projetos + Média dos seminários) ≥ 6] ⇒ aprovado.

Reprovado, caso contrário.

Referência bibliográfica

• Paulo Blauth Menezes, Linguagens Formais e Autômatos, Bookman, 6a. ed., 2011.
• Richard L. Epstein and Walter Carnielli, Computability, Computable functions, Logic and the Foundations of Mathematics, 3rd. Edition, Advanced Reasoning Forum, 2008.

Referências auxiliares

• George Boolos, John P. Burgess, and Richard C. Jeffrey, Computability and Logic, 5th. edition, Cambridge, 2007.
• José Lucas Rangel, Linguagens Formais, PUC-Rio, 1999, notas de aula.