↓ Skip to main content

Automata and Computability

Overview of attention for book
Cover of 'Automata and Computability'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Course Roadmap and Historical Perspective
  3. Altmetric Badge
    Chapter 2 Strings and Sets
  4. Altmetric Badge
    Chapter 3 Finite Automata and Regular Sets
  5. Altmetric Badge
    Chapter 4 More on Regular Sets
  6. Altmetric Badge
    Chapter 5 Nondeterministic Finite Automata
  7. Altmetric Badge
    Chapter 6 The Subset Construction
  8. Altmetric Badge
    Chapter 7 Pattern Matching
  9. Altmetric Badge
    Chapter 8 Pattern Matching and Regular Expressions
  10. Altmetric Badge
    Chapter 9 Regular Expressions and Finite Automata
  11. Altmetric Badge
    Chapter 10 Kleene Algebra and Regular Expressions
  12. Altmetric Badge
    Chapter 11 Homomorphisms
  13. Altmetric Badge
    Chapter 12 Limitations of Finite Automata
  14. Altmetric Badge
    Chapter 13 Using the Pumping Lemma
  15. Altmetric Badge
    Chapter 14 DFA State Minimization
  16. Altmetric Badge
    Chapter 15 A Minimization Algorithm
  17. Altmetric Badge
    Chapter 16 Myhill—Nerode Relations
  18. Altmetric Badge
    Chapter 17 The Myhill—Nerode Theorem
  19. Altmetric Badge
    Chapter 18 Collapsing Nondeterministic Automata
  20. Altmetric Badge
    Chapter 19 Automata on Terms
  21. Altmetric Badge
    Chapter 20 The Myhill—Nerode Theorem for Term Automata
  22. Altmetric Badge
    Chapter 21 Two-Way Finite Automata
  23. Altmetric Badge
    Chapter 22 2DFAs and Regular Sets
  24. Altmetric Badge
    Chapter 23 Context-Free Grammars and Languages
  25. Altmetric Badge
    Chapter 24 Balanced Parentheses
  26. Altmetric Badge
    Chapter 25 Normal Forms
  27. Altmetric Badge
    Chapter 26 The Pumping Lemma for CFLs
  28. Altmetric Badge
    Chapter 27 Pushdown Automata
  29. Altmetric Badge
    Chapter 28 Final State Versus Empty Stack
  30. Altmetric Badge
    Chapter 29 PDAs and CFGs
  31. Altmetric Badge
    Chapter 30 Simulating NPDAs by CFGs
  32. Altmetric Badge
    Chapter 31 Deterministic Pushdown Automata
  33. Altmetric Badge
    Chapter 32 Parsing
  34. Altmetric Badge
    Chapter 33 The Cocke—Kasami—Younger Algorithm
  35. Altmetric Badge
    Chapter 34 The Chomsky—Schützenberger Theorem
  36. Altmetric Badge
    Chapter 35 Parikh’s Theorem
  37. Altmetric Badge
    Chapter 36 Turing Machines and Effective Computability
  38. Altmetric Badge
    Chapter 37 More on Turing Machines
  39. Altmetric Badge
    Chapter 38 Equivalent Models
  40. Altmetric Badge
    Chapter 39 Universal Machines and Diagonalization
  41. Altmetric Badge
    Chapter 40 Decidable and Undecidable Problems
  42. Altmetric Badge
    Chapter 41 Reduction
  43. Altmetric Badge
    Chapter 42 Rice’s Theorem
  44. Altmetric Badge
    Chapter 43 Undecidable Problems About CFLs
  45. Altmetric Badge
    Chapter 44 Other Formalisms
  46. Altmetric Badge
    Chapter 45 The λ-Calculus
  47. Altmetric Badge
    Chapter 46 While Programs
  48. Altmetric Badge
    Chapter 47 Beyond Undecidability
  49. Altmetric Badge
    Chapter 48 Gödel’s Incompleteness Theorem
  50. Altmetric Badge
    Chapter 49 Proof of the Incompleteness Theorem
  51. Altmetric Badge
    Chapter 50 Gödel’s Proof
Attention for Chapter 41: Reduction
Altmetric Badge

Citations

dimensions_citation
208 Dimensions
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
Reduction
Chapter number 41
Book title
Automata and Computability
Published by
Springer New York, January 1997
DOI 10.1007/978-1-4612-1844-9_41
Book ISBNs
978-1-4612-7309-7, 978-1-4612-1844-9
Authors

Dexter C. Kozen