Teoria de Linguagens
Segundo semestre/2008

• Livro texto: Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
  Veja soluções dos exercícios do capítulo 1 (em um formato provisorio).
  Algumas livrarias com venda on line:
  • Cultura
  • Saraiva
  • Siciliano
• Veja o Plano de Curso (pdf).
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • Language Emulator
  • JFLAP; veja como usar .
  • Turing's World
  • The Java Computability Toolkit
  • Turing Machine (C++ Simulator)
• Veja um texto bom e conciso sobre demonstrações de teoremas. Ele foi baixado de http://www.math.dartmouth.edu/archive/m38s04/public_html/. Observe, particularmente, os itens 4 e 7 da seção 3!
• Veja algumas técnicas de prova que nunca devem ser usadas...
• ANTLR: a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, or C++.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Provas:
  • Primeira Prova:
    • Data: 8/09. Adiada para 17/9.
    • Assunto: Até item 2.4, inclusive.
    • Valor: 26 pontos (ou 18; veja a lista preparatória).
    • Veja a lista preparatória a ser entregue até o dia 8/09. Adiada para 17/9.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 13/10. Adiada para 22/10.
    • Assunto: Até capítulo 3, inclusive.
    • Valor: 27 pontos (ou 18; veja a lista preparatória).
    • Veja a lista preparatória a ser entregue até o dia 13/10. Adiada para 22/10.
  • Terceira Prova:
    • Data: 24/11. Adiada para 26/11.
    • Assunto: Até capítulo 5, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 24/11. Adiada para 26/11.
  • Prova Suplementar (não obrigatória):
    • Data: 08/12. Adiada para 10/12.
    • Assunto: Toda a matéria.
    • Valor: 27 pontos.
    • Importante: a nota substituirá a menor das 3 notas anteriores.
• Seminário a ser apresentado no dia 24/11:
  1. Petri nets plans.
     Celso Augusto Raposo Lisboa Brennand.
• Seminários a serem apresentados no dia 1/12:
  1. Artificial immune systems.
     João Guilherme Maia de Menezes.
  2. Abstract state machines.
     César Francisco de Moura Couto.
  3. Programação genética baseada em gramáticas.
     Humberto Mossri.
  4. Gramáticas de atributos.
     Elton Máximo Cardoso.
  5. Princípios básicos do processamento computacional de linguagem natural.
     Carlos Salvador Murray.
  6. Casamento exato e aproximado de padrões.
     Leandro Aparecido Villas.
• Seminários a serem apresentados no dia 3/12:
  1. A new approach to image retrieval using multi-level generalized finite automata.
     Marcelo de Miranda Coelho.
  2. Image compression method based on generalized finite automata.
     Sandra Eliza Fontes de Ávila
  3. Autômatos celulares.
     Rafael Sachetto Oliveira.
  4. Uso de autômatos celulares na modelagem e simulação de redes de sensores sem fio.
     Heitor Soares Ramos Filho.
  5. Linguagens de domínio específico embutidas utilizando syntax definition formalism e Stratego/XT.
     Leonardo Vieira dos Santos Reis.
  6. Verificação formal de sistemas utilizando BDDs e lógica temporal.
     Pedro de Carvalho Gomes.
  7. Parsing with a finite dictionary.
     Antônio Wilson Vieira.
• Referências boas para escolha de tópicos para Seminários:
  • Handbook of Formal Languages, vols. 1, 2 and 3., Springer, 1997.
  • Handbook of Theoretical Computer Science, vols. A and B, The MIT Press, 1990.
  • Periódico: Theoretical Computer Science, Elsevier, 14 vols. (28 issues per year.)
  • Os melhores periódicos de sua área.
• Alguns assuntos para Seminários:
  • Ben-Davida, S., Fismanb, D., Ruahc, S. Embedding finite automata within regular expressions, Theoretical Computer Science 404, 2008, pp. 202-218.
  • Campeanu, A., Paun, A., Smith, J.R. Incremental construction of minimal deterministic cover automata, Theoretical Computer Science 363, 2006, pp. 124-134.
  • Cherubini, M., Crespi Reghizzi, S., Pradella, M., San Pietro, P. Picture Languages: Tiling systems versus tile rewrinting grammars, Theoretical Computer Science 356, 2006, pp. 90-103.
  • Crespi Reghizzi, S., Pradella, M. Tile rewrinting grammars and picture languages, Theoretical Computer Science 340, 2005, pp. 257-272.
  • Garcia, P., de Parga, M.V., Álvarez, G.I, Ruiz, J. Universal automata and NFA learning, Theoretical Computer Science 407, 2008, pp. 192-202.
  • Geeraerts, G., Raskin, J-F., Van Begin, L. Well-structured languages, Acta Informatica 44, 2007, pp. 249-288.
  • Glabbeek, R.J. On the expressiveness of higher dimensional automata, Theoretical Computer Science 356, 2006, pp. 265-290.
  • Gurevich, Y., Veanes, M., Wallace, C. Can abstract state machines be useful in language theory?, Theoretical Computer Science 376, 2007, pp. 17-29.
  • Han, Y.-S., Wood, D. Obtaining shorter regular expressions from finite-state automata, Theoretical Computer Science 370, 2007, 110-120.
  • Hoogeboom, H.J., Kosters, W.A. Tetris and decidability, Information Processing Letters 89, 2004, pp. 267-272.
  • Hromkovic, J., Shnitger, G. Comparing the size of NFAs with and without e-transitionss, Theoretical Computer Science 380, 2007, pp. 100-114.
  • Jurdzinski, T., Otto, F. Restarting automata with restricted utilization of auxiliary symbols, Theoretical Computer Science 363, 2006, pp. 162-181.
  • Jurgensen, H., Staiger, L., Yamasaki, H. Finite automata enconding geometric figures, Theoretical Computer Science 381, 2007, pp. 33-43.
  • Kari, J. Theory of cellular automata: A survey, Theoretical Computer Science 334, 2005, pp. 3-33.
  • Kugel, P. Toward a theory of intelligence, Theoretical Computer Science 317, 2004, pp. 13-30.
  • Kutrib, M., Malcher, A. Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science 376, 2007, pp. 101-111.
  • Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  • Neary, T., Woods, D. Small fast Turing machines, Theoretical Computer Science 362, 2006, pp. 171-195.
  • Okhotin, A. An overview of conjunctive grammars, in: Paun, Rozenberg, Salomaa (eds.), Current Trends in Theoretical Computer Science: The Challenge of the Century, vol. II, World Scientific, 2004, pp. 545-566.
  • Panduranga Rao, M.V. Interference automata, Theoretical Computer Science 403, 2008, pp. 89-103.
  • Timmis, J., Hone, A., Stibor, T., Clark, E. Theoretical advances in artificial immune systems, Theoretical Computer Science 403, 2008, pp. 11-32.
  • van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.