Introduction to the theory of computation
By: Michael Sipser
Edition: 3rd ed.
Publisher: Cengage Learning
Published: 2013
Place of publication: Boston, MA
Language: eng
Number of pages: 458
ISBN-13: 9781133187790
Subjects: Machine theory; Computational complexity
Notes: Includes bibliographical references (p. 443-447) and index.
Table of contents: title: Part 1:; title: Automata and languages. -- 1.; title: Regular languages ; -- 2.; title: Context-free languages -- -- Part 2:; title: Computability theory. -- 3.; title: The Church-Turing thesis ; -- 4.; title: Decidability ; -- 5.; title: Reducibility ; -- 6.; title: Advanced topics in computability theory -- -- Part 3:; title: Complexity theory. -- 7.; title: Time complexity ; -- 8.; title: Space complexity ; -- 9.; title: Interactibility ; -- 10.; title: Advanced topics in complexity theory.