Apress

Computation Engineering

Applied Automata Theory and Logic

By Ganesh Gopalakrishnan

Computation Engineering Cover Image

Many Computation Engineering textbooks emphasize automata theory only, not logic, losing a the opportunity to tie these subjects together and reinforce learning. This textbook ties theory and logic together, using interactive tools, such as simple BDD and SAT tools. By providing a blend of theory and practical applications the material is presented as both inviting and current. Key concepts are illustrated in multiple domains so that information is reinforced and students can begin to tie theory and logic together.

Full Description

  • ISBN13: 978-0-3872-4418-1
  • 508 Pages
  • User Level: Students
  • Publication Date: September 10, 2006
  • Available eBook Formats: PDF
  • eBook Price: $124.00
Buy eBook Buy Print Book Add to Wishlist
Full Description
The computer hardware and software industry is committed to using formal methods. As a result, it is crucial that students who take automata theory and logic courses retain what they have learned and understand how to use their knowledge. Yet many textbooks typically emphasize automata theory only, not logic, thus losing a valuable opportunity to tie these subjects together and reinforce learning. In fact, automata theory and logic evolved hand-in-hand, yet this connection was severed in the '70s as separate automata-theory and logic courses became possible. Now, with computer science departments suffering from overcrowded syllabi, it is often possible for undergraduates to get a BS without having had to take a course in mathematical logic! Today's students want to know how knowledge can work for them -- learning theory as a tool is preferable to learning theory for theory's sake. To prove that theoretical tenents are not only applicable, but also necessary and relevant, useful examples must be presented. This textbook uses interactive tools throughout, such as simple BDD and SAT tools. By providing a blend of theory and practical applications the material is shown to be both inviting and current. Topics are also illustrated in multiple domains so that information is reinforced and students can begin to tie automata theory and logic together. They will also learn multiple uses of fixed-points, including BDD based model checking and understanding context-free productions. Having used this book, students will not only know and understand automata theory, but also be able to apply their knowledge in real practice.
Table of Contents

Table of Contents

  1. Foreword.
  2. Introduction.
  3. Mathematical Preliminaries.
  4. Cardinalities and Diagonalization.
  5. Binary Relations.
  6. Mathematical Logic, Induction, Proofs.
  7. Dealing with Recursion.
  8. Strings and Languages.
  9. Machines, Languages, DFA.
  10. NFA and Regular Expressions.
  11. Operations on Regular Machinery.
  12. The Automaton/Logic Connection, Symbolic Techniques.
  13. The `Pumping' Lemma.
  14. Context
  15. free Languages.
  16. Push
  17. down Automata and Context
  18. free Grammars.
  19. Turing Machines.
  20. Basic Undecidability Proofs.
  21. Advanced Undecidability Proofs.
  22. Basic Notions in Logic including SAT.
  23. Complexity Theory and NP
  24. Completeness.
  25. DFA for Presburger Arithmetic.
  26. Model Checking: Basics.
  27. Model Checking: Temporal Logics.
  28. Model Checking: Algorithms.
  29. Conclusions.
Errata

If you think that you've found an error in this book, please let us know about it. You will find any confirmed erratum below, so you can check if your concern has already been addressed.

* Required Fields

No errata are currently published