Flávio da Silva, Marcelo Finger and Ana de Melo, Lógica para Computação, 2006. (LC)
João de Souza, Lógica para Ciência da Computação e áreas afins, 2015. (LCC)
Stuart Russel and Peter Norvig, Artificial Intelligence: A Modern Approach, 2009. (AIMA)
Michael Huth and Mark Ryan, Logic in Computer Science: Modelling and Reasoning About Systems, 2004. (LCS)
Mordechai Ben-Ari, Mathematical Logic for Computer Science, 2012. (MLCS)
Armin Biere, et al., Handbook of Satisfiability, 2009. (HS)
Donald Knuth, The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability, 2015. (TACP)
| Topics | Readings |
|---|---|
| Introduction and Motivation | LCS: Sec. 1.1, LCC: Sec. 1.1, LC: Sec. 1.1 |
| Formulas of Propositional Logic | LC: Sec. 1.2, LCC: Sec. 1.2-1.7, LCS: Sec. 1.3, Sec. 1.4.2 |
| Semantics of Propositional Logic | LC: Sec. 1.3, LCC: Ch. 2, LCS: Sec. 1.4.1-1.4.2 |
| Logical Consequence | LC: Sec. 1.5, LCC: Sec. 3.7, AIMA: Sec. 7.4.4 |
| Logical Equivalence | LC: Sec. 1.5, LCC: Sec. 3.6 |
| Validity | LC: Sec 1.4, LCC: Sec. 3.2 |
| Satisfiability | LC: Sec 1.4, LCC: Sec. 3.3, MLCS: Sec. 6.4.1, HS: Sec. 2.3.1-2.3.3 |
| Natural Deduction | LCS: Sec. 1.2 |
Assignment 01 - Propositional Formulas
Assignment 02 - Interpretations
Assignment 03 - Semantic Properties
John Hopcroft, Rajeev Motwani and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, 2006. (IATLC)
Michael Sipser, Introduction to the Theory of Computation, 2012. (ITC)
| Topics | Readings |
|---|---|
| Introduction and Motivation | IATLC: Sec. 1.1, Sec. 2.1 |
| Deterministic Finite Automata | IATLC: Sec. 1.5, Sec. 2.2.1-2.2.3, ITC: Sec 1.1 |
| Extended Transition Function, Language of a DFA and Regular Languages | IATLC: Sec. 2.2.4-2.2.5, ITC: Sec 1.1 |
| Proofs and Complement of a Regular Language | IATLC: Sec. 1.2-1.4, Sec. 4.2.1 |
| Nondeterministic Finite Automata | IATLC: Sec. 2.3.1-2.3.2, Sec. 2.5.1-2.5.2, ITC: Sec. 1.2 |
| Epsilon-Closures, Extended Transition Function of an NFA | IATLC: Sec. 2.5.3-2.5.4 |
| Equivalence of DFA and NFA | IATLC: Sec. 2.5.5, Sec. 2.3.5, ITC: Sec. 1.2 |
| Regular Expressions | IATLC: Sec. 3.1, ITC: Sec. 1.3 |
| Regular Expressions and Finite Automata | IATLC: Sec. 3.2 |
| Pumping Lemma for Regular Languages | IATLC: Sec. 4.1 |
| Equivalence and Minimization of Automata | IATLC: Sec. 4.4 |
Assignment 01 - Deterministic Finite Automata
Assignment 02 - Nondeterministic Finite Automata
Thiago Alves Rocha, Ana Teresa Martins and Francicleber Martins Ferreira. Synthesis of a DNF Formula from a Sample of Strings using Ehrenfeucht-Fraïssé Games. Theoretical Computer Science, 2019.
Thiago Alves Rocha, Ana Teresa Martins and Francicleber Martins Ferreira. On Finding a First-Order Sentence Consistent with a Sample of Strings. Electronic Proceedings in Theoretical Computer Science, 2018.
Thiago Alves Rocha, Ana Teresa Martins and Francicleber Martins Ferreira. On Distinguishing Sets of Structures by First-Order Sentences of Minimal Quantifier Rank. Electronic Notes in Theoretical Computer Science, 2018.
Thiago Alves Rocha and Ana Teresa Martins. Synthesis of Quantifier-Free First-Order Sentences from Noisy Samples of Strings. In 8th Brazilian Conference on Intelligent Systems, 2019.
Thiago Alves Rocha, Ana Teresa Martins and Francicleber Martins Ferreira. Synthesis of a DNF Formula from a Sample of Strings. In 7th Brazilian Conference on Intelligent Systems, 2018.
Savio Lopes Rabelo, Helio Henrique Rocha e Thiago Alves Rocha. Comparação de codificações para solução de puzzles Sudoku via algoritmo DPLL. In Escola de Informática Teórica e Métodos Formais, 2016.
Thiago Alves Rocha and Ana Teresa Martins. Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers. In 1º Encontro de Teoria da Computação, 2016.
Lucas Leite, Thiago Alves Rocha and João Alcântara. Merging Argumentation Frameworks. In 4th Brazilian Conference on Intelligent Systems, 2015.
Wellington Franco, Thiago Alves Rocha, Henrique Viana and João Alcântara. A Description Logic for InferenceNet.Br. In 10th International Conference on Computational Processing of the Portuguese Language, 2012.
Henrique Viana, Thiago Alves Rocha, João Alcântara and Ana Teresa Martins. A Tractable Paraconsistent Fuzzy Description Logic. In 6th International Workshop on Uncertainty Reasoning for the Semantic Web, 2010.