國立虎尾科技大學 |

An introduction to theory of computation = an algorithmic approach /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	An introduction to theory of computation/ by Mitsunori Ogihara.
Reminder of title:	an algorithmic approach /
Author:	Ogihara, Mitsunori.
Published:	Cham :Springer Nature Switzerland : : 2025.,
Description:	xxiii, 382 p. :ill. (some col.), digital ; : 24 cm.;
Contained By:	Springer Nature eBook
Subject:	Machine theory. -
Online resource:	https://doi.org/10.1007/978-3-031-84740-0
ISBN:	9783031847400

An introduction to theory of computation = an algorithmic approach /
Ogihara, Mitsunori.

An introduction to theory of computationan algorithmic approach /[electronic resource] :by Mitsunori Ogihara. - Cham :Springer Nature Switzerland :2025. - xxiii, 382 p. :ill. (some col.), digital ;24 cm.

Part I Preparation -- Chapter 0 Mathematics and Computer Science Basics -- Part II Formal Language Theory and Automata -- Chapter 1 The Regular Languages -- Chapter 2 Non-Regularity -- Chapter 3 The Context-Free Languages -- Chapter 4 The Pushdown Automaton Model -- Part III Undecidability and Turing Machines -- Chapter 5 The Turing Machines -- Chapter 6 Decidable Languages -- Chapter 7 Undecidable Languages -- Part IV Computational Complexity and Resource-Bounded Turing Machine Computation -- Chapter 8 The Time Complexity -- Chapter 9 The Space Complexity -- Chapter 10 The Theory of NP-Completeness -- Chapter 11 Beyond NP-Completeness -- Part V Advanced Topics in Computational Complexity Theory -- Chapter 12 The Probabilistic Polynomial-Time Classes -- Chapter 13 Circuit Complexity and Unambiguity.

This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in computer science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation. The book begins with regular languages, exploring finite automata, nondeterministic finite automata, regular expressions, and the equivalence among these apparatuses. It explores state minimization and the Myhill-Nerode Theorem, offering techniques such as pumping lemmas to identify non-regular languages and using the Myhill-Nerode Theorem for non-regularity proofs. Additionally, the closure properties of regular languages are examined. Context-free languages are another focal point, where the text discusses context-free grammars, Chomsky normal form grammars, pushdown automata, and their equivalences. The book includes pumping lemmas and closure properties using CNF grammars and PDA analysis, as well as identifying non-context-free languages and understanding leftmost derivations. Turing machine models are thoroughly covered, with various models and simulations explained. The book outlines configurations, the Church-Turing Thesis, and differentiates between recursive and recursively enumerable languages. Decidability and undecidability are critical topics in the text, addressing decidable problems, diagonalization, the halting problem, and Rice's Theorem. It also provides a characterization of decidability, discusses the Post Correspondence Problem, and examines the lower levels of the arithmetical hierarchy. The textbook also delves into computational complexity classes, defining time and space complexity classes, and presenting efficient simulations and hierarchy theorems, including the Hennie-Stearns Theorem. It includes examples of problems in P and NP, providing a clear understanding of these classifications. NP-completeness is explored in detail, covering SAT and 3SAT, canonical complete problems, and various NP-complete problems. The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL. Finally, the text ventures beyond NP-completeness, discussing Ladner's construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy. It also examines polynomial size circuits, providing a comprehensive view of the landscape of computational complexity.

ISBN: 9783031847400

Standard No.: 10.1007/978-3-031-84740-0doiSubjects--Topical Terms:

527775
Machine theory.

LC Class. No.: QA267

Dewey Class. No.: 511.3

An introduction to theory of computation = an algorithmic approach /
LDR:04328nam a2200325 a 4500 001 1161750
003 DE-He213
005 20250408165827.0
006 m d
007 cr nn 008maaau
008 251029s2025 sz s 0 eng d
020 $a 9783031847400 $q (electronic bk.)
020 $a 9783031847394 $q (paper)
024 7 $a 10.1007/978-3-031-84740-0 $2 doi
035 $a 978-3-031-84740-0
040 $a GP $c GP
041 0 $a eng
050 4 $a QA267
072 7 $a UYA $2 bicssc
072 7 $a COM014000 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 511.3 $2 23
090 $a QA267 $b .O34 2025
100 1 $a Ogihara, Mitsunori. $3 785748
245 1 3 $a An introduction to theory of computation $h [electronic resource] : $b an algorithmic approach / $c by Mitsunori Ogihara.
260 $a Cham : $c 2025. $b Springer Nature Switzerland : $b Imprint: Springer,
300 $a xxiii, 382 p. : $b ill. (some col.), digital ; $c 24 cm.
505 0 $a Part I Preparation -- Chapter 0 Mathematics and Computer Science Basics -- Part II Formal Language Theory and Automata -- Chapter 1 The Regular Languages -- Chapter 2 Non-Regularity -- Chapter 3 The Context-Free Languages -- Chapter 4 The Pushdown Automaton Model -- Part III Undecidability and Turing Machines -- Chapter 5 The Turing Machines -- Chapter 6 Decidable Languages -- Chapter 7 Undecidable Languages -- Part IV Computational Complexity and Resource-Bounded Turing Machine Computation -- Chapter 8 The Time Complexity -- Chapter 9 The Space Complexity -- Chapter 10 The Theory of NP-Completeness -- Chapter 11 Beyond NP-Completeness -- Part V Advanced Topics in Computational Complexity Theory -- Chapter 12 The Probabilistic Polynomial-Time Classes -- Chapter 13 Circuit Complexity and Unambiguity.
520 $a This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in computer science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation. The book begins with regular languages, exploring finite automata, nondeterministic finite automata, regular expressions, and the equivalence among these apparatuses. It explores state minimization and the Myhill-Nerode Theorem, offering techniques such as pumping lemmas to identify non-regular languages and using the Myhill-Nerode Theorem for non-regularity proofs. Additionally, the closure properties of regular languages are examined. Context-free languages are another focal point, where the text discusses context-free grammars, Chomsky normal form grammars, pushdown automata, and their equivalences. The book includes pumping lemmas and closure properties using CNF grammars and PDA analysis, as well as identifying non-context-free languages and understanding leftmost derivations. Turing machine models are thoroughly covered, with various models and simulations explained. The book outlines configurations, the Church-Turing Thesis, and differentiates between recursive and recursively enumerable languages. Decidability and undecidability are critical topics in the text, addressing decidable problems, diagonalization, the halting problem, and Rice's Theorem. It also provides a characterization of decidability, discusses the Post Correspondence Problem, and examines the lower levels of the arithmetical hierarchy. The textbook also delves into computational complexity classes, defining time and space complexity classes, and presenting efficient simulations and hierarchy theorems, including the Hennie-Stearns Theorem. It includes examples of problems in P and NP, providing a clear understanding of these classifications. NP-completeness is explored in detail, covering SAT and 3SAT, canonical complete problems, and various NP-complete problems. The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL. Finally, the text ventures beyond NP-completeness, discussing Ladner's construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy. It also examines polynomial size circuits, providing a comprehensive view of the landscape of computational complexity.
650 0 $a Machine theory. $3 527775
650 1 4 $a Theory of Computation. $3 669322
650 2 4 $a Formal Languages and Automata Theory. $3 1365747
650 2 4 $a Computational Complexity. $3 1366362
650 2 4 $a Models of Computation. $3 1365746
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
856 4 0 $u https://doi.org/10.1007/978-3-031-84740-0
950 $a Computer Science (SpringerNature-11645)