Teoria de Linguagens
Segundo semestre/2004

• Plano de curso: PostScript (Para leitura de PostScript, pegue o software apropriado.)
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • Language Emulator
  • JFLAP.
  • Deus ex Machina
  • Turing's World
  • Webworks Laboratory
  • Ganimal
  • The Java Computability Toolkit
  • Turing Machine (C++ Simulator)
• Apostila: PS.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• ANTLR: a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, or C++.
• Listas de exercícios:
  • Primeira Lista. Entrega: 28/09/2004. Adiada para 30/09.
  • Segunda Lista. Entrega: 04/11/2004. Adiada para 11/11.
  • Terceira Lista. Entrega: 09/12/2004.
• Trabalho especial (4 pontos). Entrega: até 13/11/2004. Adiada para 16/11.
• Provas:
  • Primeira Prova:
    • Data: 28/09. Adiada para 30/09.
    • Assunto: Até item 2.4, inclusive.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 09/11. Adiada para 11/11.
    • Assunto: Até capítulo 3, inclusive.
  • Terceira Prova:
    • Data: 09/12. Adiada para 14/12.
    • Assunto: Até capítulo 5, inclusive.
• Seminários de 16/12:
  • NFA reduction algorithms by means of regular inequalities
    Fábio Enrique Brochero Martinez
  • An overview of conjunctive grammars
    André Luiz Lins de Araújo
  • A brief history of cellular automata
    Georgia Penido Safe
• Seminários de 17/12 (14h, sala 2016):
  • Applications of finite automata representing large vocabularies
    Álvaro Rodrigues Pereira Júnior
  • Optimal insertion in deterministic DAWGs
    David Menoti Gomes
  • Hypercomputation: philosophical issues
    Geraldo Augusto Massahud Rodrigues dos Santos
  • Job-shop scheduling using timed automata
    Martin Gomez Ravetti
  • Redes de Petri
    Max do Val Machado
  • Lindenmayer systems (L-systems)
    Wagner Ferreira de Barros
• 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 da sua área.
• Alguns artigos que podem ser apresentados em Seminários:
  • Cleland, C.E. The concept of computability, Theoretical Computer Science 317, 2004, pp. 209-225.
  • Copeland, B.J. Hypercomputation: philosophical issues, Theoretical Computer Science 317, 2004, pp. 251-267.
  • Daciuk, J., van Noord, G. Finite automata for compact representation of tuple dictionaries, Theoretical Computer Science 313, 2004, pp. 45-56.
  • Daley, M., Kari, L., McQuillan, I. Family of languages defined by ciliate bio-operations, Theoretical Computer Science 320, 2004, pp. 51-69.
  • Hoogeboom, H.J., Kosters, W.A. Tetris and decidability, Information Processing Letters 89, 2004, pp. 267-272.
  • Leitgeb, H., Hieke, A. Circular languages, Journal of Logic, Language and Information 13, 2004, pp. 341-371.
  • Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  • Neven, F., Schwentick, T., Vianu, V. Finite state machines for strings over infinite alphabets, ACM Transactions on Computational Logic 5(3), 2004, pp. 403-435.
  • Neven, F. Automata theory for XML researchers, SIGMOD Record 31(3), 2002, pp. 39-46.
  • Okhotin, A. Boolean grammars, Journal of Automata, Languages and Combinatorics 6(4), 2001, pp. 519-535.
  • 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.
  • Salomaa, A., Wood, D., Yu, S. On the state complexity of reversals of regular languages, Theoretical Computer Science 320, 2004, pp. 315-329.
  • Sarkar, P. A brief history of cellular automata, ACM Computing Surveys 32(1), 2000, pp. 80-107. (Já escolhido.)
  • van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.