Computation Engineering Applied Automata Theory and Logic /

• Main Author: Gopalakrishnan, Ganesh (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Boston, MA : Springer US, 2006.
• Subjects: Computer science.; Computers.; Mathematical logic.; Electrical engineering.; Electronic circuits.; Computer Science.; Theory of Computation.; Circuits and Systems.; Mathematical Logic and Formal Languages.; Electrical Engineering.

"This classroom-tested undergraduate textbook is unique in presenting logic and automata theory as a single subject...I highly recommend this book to you as the best route I know into the concepts underlying modern industrial formal verification." - Dr. Michael J.C. Gordon FRS, The Univers...

Table of Contents:

• Mathematical Preliminaries
• Cardinalities and Diagonalization
• Binary Relations
• Mathematical Logic, Induction, Proofs
• Dealing with Recursion
• Strings and Languages
• Machines, Languages, DFA
• NFA and Regular Expressions
• Operations on Regular Machinery
• The Automaton/Logic Connection, Symbolic Techniques
• The ‘Pumping’ Lemma
• Context-free Languages
• Push-down Automata and Context-free Grammars
• Turing Machines
• Basic Undecidability Proofs
• Advanced Undecidability Proofs
• Basic Notions in Logic including SAT
• Complexity Theory and NP-Completeness
• DFA for Presburger Arithmetic
• Model Checking: Basics
• Model Checking: Temporal Logics
• Model Checking: Algorithms
• Conclusions.