close
1.

図書
図書
1. Information, randomness & incompleteness : papers on algorithmic information theory (: pbk.)
Gregory J. Chaitin
出版情報: Singapore ; Teaneck, NJ : World Scientific, c1987  x, 272 p. ; 23 cm
シリーズ名: Series in computer science ; v. 8
所蔵情報: loading…
2.

図書
図書
2. Introduction to the theory of computation
Michael Sipser
出版情報: Boston : PWS Pub., c1997  xv, 396 p.
所蔵情報: loading…
目次情報: 続きを見る
Preface to the First Edition
To the student
To the educator
The first edition
Feedback to the author
Acknowledgments
Preface to the Second Edition
Introduction / 0：
Automata, Computability, and Complexity / 0.1：
Complexity theory
Computability theory
Automata theory
Mathematical Notions and Terminology / 0.2：
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
Definitions, Theorems, and Proofs / 0.3：
Finding proofs
Types of Proof / 0.4：
Proof by construction
Proof by contradiction
Proof by induction
Exercises, Problems, and Solutions
Automata and Languages / Part 1：
Regular Languages / 1：
Finite Automata / 1.1：
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
Nondeterminism / 1.2：
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
Regular Expressions / 1.3：
Formal definition of a regular expression
Equivalence with finite automata
Nonregular Languages / 1.4：
The pumping lemma for regular languages
Context-Free Languages / 2：
Context-free Grammars / 2.1：
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
Pushdown Automata / 2.2：
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
Non-context-free Languages / 2.3：
The pumping lemma for context-free languages
Computability Theory / Part 2：
The Church-Turing Thesis / 3：
Turing Machines / 3.1：
Formal definition of a Turing machine
Examples of Turing machines
Variants of Turing Machines / 3.2：
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
The Definition of Algorithm / 3.3：
Hilbert's problems
Terminology for describing Turing machines
Decidability / 4：
Decidable Languages / 4.1：
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
The Halting Problem / 4.2：
The diagonalization method
The halting problem is undecidable
A Turing-unrecognizable language
Reducibility / 5：
Undecidable Problems from Language Theory / 5.1：
Reductions via computation histories
A Simple Undecidable Problem / 5.2：
Mapping Reducibility / 5.3：
Computable functions
Formal definition of mapping reducibility
Advanced Topics in Computability Theory / 6：
The Recursion Theorem / 6.1：
Self-reference
Terminology for the recursion theorem
Applications
Decidability of logical theories / 6.2：
A decidable theory
An undecidable theory
Turing Reducibility / 6.3：
A Definition of Information / 6.4：
Minimal length descriptions
Optimality of the definition
Incompressible strings and randomness
Complexity Theory / Part 3：
Time Complexity / 7：
Measuring Complexity / 7.1：
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
The Class P / 7.2：
Polynomial time
Examples of problems in P
The Class NP / 7.3：
Examples of problems in NP
The P versus NP question
NP-completeness / 7.4：
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
Additional NP-complete Problems / 7.5：
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Space Complexity / 8：
Savitch's Theorem / 8.1：
The Class PSPACE / 8.2：
PSPACE-completeness / 8.3：
The TQBF problem
Winning strategies for games
Generalized geography
The Classes L and NL / 8.4：
NL-completeness / 8.5：
Searching in graphs
NL equals coNL / 8.6：
Intractability / 9：
Hierarchy Theorems / 9.1：
Exponential space completeness
Relativization / 9.2：
Limits of the diagonalization method
Circuit Complexity / 9.3：
Advanced topics in complexity theory / 10：
Approximation Algorithms / 10.1：
Probabilistic Algorithms / 10.2：
The class BPP
Primality
Read-once branching programs
Alternation / 10.3：
Alternating time and space
The Polynomial time hierarchy
Interactive Proof Systems / 10.4：
Graph nonisomorphism
Definition of the model
IP = PSPACE
Parallel Computation / 10.5：
Uniform Boolean circuits
The class NC
P-completeness
Cryptography / 10.6：
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Selected Bibliography
Preface to the First Edition
To the student
To the educator
3.

図書
図書
3. Complex systems dynamics : an introduction to automata networks (: pbk)
Gérard Weisbuch ; translated by Sylvie Ryckebusch
出版情報: Redwood City, Calif. : Addison-Wesley, c1991  xvii, 189 p. ; 24 cm
シリーズ名: Santa Fe Institute studies in the sciences of complexity ; Lecture notes ; v. 2
所蔵情報: loading…
4.

図書
図書
4. Stochastic complexity in statistical inquiry
Jorma Rissanen
出版情報: Singapore ; Teaneck, N.J. : World Scientific, c1989  iii, 177 p. ; 23 cm
シリーズ名: Series in computer science ; v. 15
所蔵情報: loading…
5.

図書
図書
5. Problem solving in automata, languages, and complexity
Ding-Zhu Du, Ker-I Ko
出版情報: New York : John Wiley & Sons, c2001  viii, 396 p. ; 25 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Regular Languages / 1：
Strings and Languages / 1.1：
Regular Languages and Regular Expressions / 1.2：
Graph Representations for Regular Expressions / 1.3：
Finite Automata / 2：
Deterministic Finite Automata / 2.1：
Examples of Deterministic Finite Automata / 2.2：
Nondeterministic Finite Automata / 2.3：
Converting an NFA to a DFA / 2.4：
Finite Automata and Regular Expressions / 2.5：
Closure Properties of Regular Languages / 2.6：
Minimum Deterministic Finite Automata / 2.7：
Pumping Lemmas / 2.8：
Context-Free Languages / 3：
Context-Free Grammars / 3.1：
More Examples of Context-Free Grammars / 3.2：
Parsing and Ambiguity / 3.3：
Pushdown Automata / 3.4：
Pushdown Automata and Context-Free Grammars / 3.5：
Pumping Lemmas for Context-Free Languages / 3.6：
Turing Machines / 4：
One-Tape Turing Machines / 4.1：
Examples of Turing Machines / 4.2：
Multi-Tape Turing Machines / 4.3：
Church-Turing Thesis / 4.4：
Unrestricted Grammars / 4.5：
Primitive Recursive Functions / 4.6：
Pairing Functions and Godel Numberings / 4.7：
Partial Recursive Functions / 4.8：
Computability Theory / 5：
Universal Turing Machines / 5.1：
R. E. Sets and Recursive Sets / 5.2：
Diagonalization / 5.3：
Reducibility / 5.4：
Recursion Theorem / 5.5：
Undecidable Problems / 5.6：
Computational Complexity / 6：
Asymptotic Growth Rate / 6.1：
Time and Space Complexity / 6.2：
Hierarchy Theorems / 6.3：
Nondeterministic Turing Machines / 6.4：
Context-Sensitive Languages / 6.5：
NP-Completeness / 7：
NP / 7.1：
Polynomial-Time Reducibility / 7.2：
Cook's Theorem / 7.3：
More NP-Complete Problems / 7.4：
NP-Complete Optimization Problems / 7.5：
References
Index
Preface
Regular Languages / 1：
Strings and Languages / 1.1：
6.

図書
図書
6. Introduction to automata theory, languages, and computation. 3rd ed (: hbk ; : student access kit ; : Pearson international ed.)
by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: Boston : Pearson Addison-Wesley, c2007  xvii, 535 p. ; 24 cm
所蔵情報: loading…
目次情報: 続きを見る
Automata: The Methods and the Madness / Chapter 1：
Why Study Automata Theory / 1.1：
Introduction to Formal Proof / 1.2：
Additional Forms of Proof / 1.3：
Inductive Proofs / 1.4：
The Central Concepts of Automata Theory / 1.5：
Summary of Chapter 1 / 1.6：
Gradiance Problems for Chapter 1 / 1.7：
References for Chapter 1 / 1.8：
Finite Automata / Chapter 2：
An Informal Picture of Finite Automata / 2.1：
Deterministic Finite Automata / 2.2：
Nondeterministic Finite Automata / 2.3：
An Application_ Text Search / 2.4：
Finite Automata With EpsilonTransitions / 2.5：
Summary of Chapter 2 / 2.6：
Gradiance Problems for Chapter 2 / 2.7：
References for Chapter 2 / 2.8：
Regular Expressions and Languages / Chapter 3：
Regular Expressions / 3.1：
Finite Automata and Regular Expressions / 3.2：
Applications of Regular Expressions / 3.3：
Algebraic Laws for Regular Expressions / 3.4：
Summary of Chapter 3 / 3.5：
Gradiance Problems for Chapter 3 / 3.6：
References for Chapter 3 / 3.7：
Properties of Regular Languages / Chapter 4：
Proving Languages Not to Be Regular / 4.1：
Closure Properties of Regular Languages / 4.2：
Decision Properties of Regular Languages / 4.3：
Equivalence and Minimization of Automata / 4.4：
Summary of Chapter 4 / 4.5：
Gradiance Problems for Chapter 4 / 4.6：
References for Chapter 4 / 4.7：
Context-Free Grammars and Languages / Chapter 5：
Context-Free Grammars / 5.1：
Parse Trees / 5.2：
Applications of Context-Free Grammars / 5.3：
Ambiguity in Grammars and Languages / 5.4：
Summary of Chapter 5 / 5.5：
Gradiance Problems for Chapter 5 / 5.6：
References for Chapter 5 / 5.7：
Pushdown Automata / Chapter 6：
Definition of the Pushdown Automaton / 6.1：
The Languages of a PDA / 6.2：
Equivalence of PDA's and CFG's / 6.3：
Deterministic Pushdown Automata / 6.4：
Summary of Chapter 6 / 6.5：
Gradiance Problems for Chapter 6 / 6.6：
References for Chapter 6 / 6.7：
Properties of Context-Free Languages / Chapter 7：
Normal Forms for Context-Free Grammars / 7.1：
The Pumping Lemma for Context-Free Languages / 7.2：
Closure Properties of Context-Free Languages / 7.3：
Decision Properties of CFL's / 7.4：
Summary of Chapter 7 / 7.5：
Gradiance Problems for Chapter 7 / 7.6：
References for Chapter 7 / 7.7：
Introduction to Turing Machines / Chapter 8：
Problems That Computers Cannot Solve / 8.1：
The Turing Machine / 8.2：
Programming Techniques for Turing Machines / 8.3：
Extensions to the Basic Turing Machine / 8.4：
Restricted Turing Machines / 8.5：
Turing Machines and Computers / 8.6：
Summary of Chapter 8 / 8.7：
Gradiance Problems for Chapter 8 / 8.8：
References for Chapter 8 / 8.9：
Undecidability / Chapter 9：
A Language That Is Not Recursively Enumerable / 9.1：
An Undecidable Problem That Is RE / 9.2：
Undecidable Problems About Turing Machines / 9.3：
Post's Correspondence Problem / 9.4：
Other Undecidable Problems / 9.5：
Summary of Chapter 9 / 9.6：
Gradiance Problems for Chapter 9 / 9.7：
References for Chapter 9 / 9.8：
Intractable Problems / Chapter 10：
The Classes P and NP / 10.1：
An NP-Complete Problem / 10.2：
A Restricted Satisfiability Problem / 10.3：
Additional NP-Complete Problems / 10.4：
Summary of Chapter 10 / 10.5：
Gradiance Problems for Chapter 10 / 10.6：
References for Chapter 10 / 10.7：
Additional Classes of Problems / Chapter 11：
Complements of Languages in NP / 11.1：
Problems Solvable in Polynomial Space / 11.2：
A Problem That Is Complete for PS / 11.3：
Language Classes Based on Randomization / 11.4：
The Complexity of Primality Testing / 11.5：
Summary of Chapter 11 / 11.6：
Gradiance Problems for Chapter 11 / 11.7：
References for Chapter 11 / 11.8：
Index
Automata: The Methods and the Madness / Chapter 1：
Why Study Automata Theory / 1.1：
Introduction to Formal Proof / 1.2：
7.

図書
図書
7. The complexity of computing
John E. Savage
出版情報: New York : Wiley, c1976  xiii, 391 p. ; 24 cm
所蔵情報: loading…
8.

図書
図書
8. Introduction to automata theory, languages, and computation. 2nd ed
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: Boston : Addison-Wesley, c2001  xiv, 521 p. ; 25 cm
所蔵情報: loading…
目次情報: 続きを見る
Automata: The Methods and the Madness / Chapter 1：
Why Study Automata Theory / 1.1：
Introduction to Formal Proof / 1.2：
Additional Forms of Proof / 1.3：
Inductive Proofs / 1.4：
The Central Concepts of Automata Theory / 1.5：
Summary of Chapter 1 / 1.6：
Gradiance Problems for Chapter 1 / 1.7：
References for Chapter 1 / 1.8：
Finite Automata / Chapter 2：
An Informal Picture of Finite Automata / 2.1：
Deterministic Finite Automata / 2.2：
Nondeterministic Finite Automata / 2.3：
An Application_ Text Search / 2.4：
Finite Automata With EpsilonTransitions / 2.5：
Summary of Chapter 2 / 2.6：
Gradiance Problems for Chapter 2 / 2.7：
References for Chapter 2 / 2.8：
Regular Expressions and Languages / Chapter 3：
Regular Expressions / 3.1：
Finite Automata and Regular Expressions / 3.2：
Applications of Regular Expressions / 3.3：
Algebraic Laws for Regular Expressions / 3.4：
Summary of Chapter 3 / 3.5：
Gradiance Problems for Chapter 3 / 3.6：
References for Chapter 3 / 3.7：
Properties of Regular Languages / Chapter 4：
Proving Languages Not to Be Regular / 4.1：
Closure Properties of Regular Languages / 4.2：
Decision Properties of Regular Languages / 4.3：
Equivalence and Minimization of Automata / 4.4：
Summary of Chapter 4 / 4.5：
Gradiance Problems for Chapter 4 / 4.6：
References for Chapter 4 / 4.7：
Context-Free Grammars and Languages / Chapter 5：
Context-Free Grammars / 5.1：
Parse Trees / 5.2：
Applications of Context-Free Grammars / 5.3：
Ambiguity in Grammars and Languages / 5.4：
Summary of Chapter 5 / 5.5：
Gradiance Problems for Chapter 5 / 5.6：
References for Chapter 5 / 5.7：
Pushdown Automata / Chapter 6：
Definition of the Pushdown Automaton / 6.1：
The Languages of a PDA / 6.2：
Equivalence of PDA's and CFG's / 6.3：
Deterministic Pushdown Automata / 6.4：
Summary of Chapter 6 / 6.5：
Gradiance Problems for Chapter 6 / 6.6：
References for Chapter 6 / 6.7：
Properties of Context-Free Languages / Chapter 7：
Normal Forms for Context-Free Grammars / 7.1：
The Pumping Lemma for Context-Free Languages / 7.2：
Closure Properties of Context-Free Languages / 7.3：
Decision Properties of CFL's / 7.4：
Summary of Chapter 7 / 7.5：
Gradiance Problems for Chapter 7 / 7.6：
References for Chapter 7 / 7.7：
Introduction to Turing Machines / Chapter 8：
Problems That Computers Cannot Solve / 8.1：
The Turing Machine / 8.2：
Programming Techniques for Turing Machines / 8.3：
Extensions to the Basic Turing Machine / 8.4：
Restricted Turing Machines / 8.5：
Turing Machines and Computers / 8.6：
Summary of Chapter 8 / 8.7：
Gradiance Problems for Chapter 8 / 8.8：
References for Chapter 8 / 8.9：
Undecidability / Chapter 9：
A Language That Is Not Recursively Enumerable / 9.1：
An Undecidable Problem That Is RE / 9.2：
Undecidable Problems About Turing Machines / 9.3：
Post's Correspondence Problem / 9.4：
Other Undecidable Problems / 9.5：
Summary of Chapter 9 / 9.6：
Gradiance Problems for Chapter 9 / 9.7：
References for Chapter 9 / 9.8：
Intractable Problems / Chapter 10：
The Classes P and NP / 10.1：
An NP-Complete Problem / 10.2：
A Restricted Satisfiability Problem / 10.3：
Additional NP-Complete Problems / 10.4：
Summary of Chapter 10 / 10.5：
Gradiance Problems for Chapter 10 / 10.6：
References for Chapter 10 / 10.7：
Additional Classes of Problems / Chapter 11：
Complements of Languages in NP / 11.1：
Problems Solvable in Polynomial Space / 11.2：
A Problem That Is Complete for PS / 11.3：
Language Classes Based on Randomization / 11.4：
The Complexity of Primality Testing / 11.5：
Summary of Chapter 11 / 11.6：
Gradiance Problems for Chapter 11 / 11.7：
References for Chapter 11 / 11.8：
Index
Automata: The Methods and the Madness / Chapter 1：
Why Study Automata Theory / 1.1：
Introduction to Formal Proof / 1.2：
9.

図書
図書
9. Elements of the theory of computation (: UK)
Harry R. Lewis, Christos H. Papadimitriou
出版情報: Englewood Cliffs, N.J. : Prentice-Hall , London : Prentice-Hall International, c1981  xiv, 466 p. ; 24 cm
シリーズ名: Prentice-Hall software series
所蔵情報: loading…
目次情報: 続きを見る
Sets, Relations, and Languages / 1：
Finite Automata / 2：
Context-Free Languages / 3：
Turing Machines / 4：
Church's Thesis / 5：
Uncomputability / 6：
Computational Complexity / 7：
The Propositional Calculus / 8：
The Predicate Calculus / 9：
Sets, Relations, and Languages / 1：
Finite Automata / 2：
Context-Free Languages / 3：
10.

電子ブック
ＥＢ
10. Introduction to the theory of computation. 3rd ed (: electronic bk)
Michael Sipser
出版情報: [東京] : Maruzen eBook Library  1 online resource (xxii, 458 p)
所蔵情報: loading…
目次情報: 続きを見る
Preface to the First Edition
To the student
To the educator
The first edition
Feedback to the author
Acknowledgments
Preface to the Second Edition
Preface to the Third Edition
Introduction / 0：
Automata, Computability, and Complexity / 0.1：
Complexity theory
Computability theory
Automata theory
Mathematical Notions and Terminology / 0.2：
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
Definitions, Theorems, and Proofs / 0.3：
Finding proofs
Types of Proof / 0.4：
Proof by construction
Proof by contradiction
Proof by induction
Exercises, Problems, and Solutions
Automata and Languages / Part 1：
Regular Languages / 1：
Finite Automata / 1.1：
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
Nondeterminism / 1.2：
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
Regular Expressions / 1.3：
Formal definition of a regular expression
Equivalence with finite automata
Nonregular Languages / 1.4：
The pumping lemma for regular languages
Context-Free Languages / 2：
Context-Free Grammars / 2.1：
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
Pushdown Automata / 2.2：
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
Non-Context-Free Languages / 2.3：
The pumping lemma for context-free languages
Deterministic Context-Free Languages / 2.4：
Properties of DCFLs
Deterministic context-free grammars
Relationship of DPDAs and DCFGs
Parsing and LR(k) Grammars
Computability Theory / Part 2：
The Church-Turing Thesis / 3：
Turing Machines / 3.1：
Formal definition of a Turing machine
Examples of Turing machines
Variants of Turing Machines / 3.2：
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
The Definition of Algorithm / 3.3：
Hilbert's problems
Terminology for describing Turing machines
Decidability / 4：
Decidable Languages / 4.1：
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
Undecidability / 4.2：
The diagonalization method
An undecidable language
A Turing-unrecognizable language
Reducibility / 5：
Undecidable Problems from Language Theory / 5.1：
Reductions via computation histories
A Simple Undecidable Problem / 5.2：
Mapping Reducibility / 5.3：
Computable functions
Formal definition of mapping reducibility
Advanced Topics in Computability Theory / 6：
The Recursion Theorem / 6.1：
Self-reference
Terminology for the recursion theorem
Applications
Decidability of logical theories / 6.2：
A decidable theory
An undecidable theory
Turing Reducibility / 6.3：
A Definition of Information / 6.4：
Minimal length descriptions
Optimality of the definition
Incompressible strings and randomness
Complexity Theory / Part 3：
Time Complexity / 7：
Measuring Complexity / 7.1：
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
The Class P / 7.2：
Polynomial time
Examples of problems in P
The Class NP / 7.3：
Examples of problems in NP
The P versus NP question
NP-completeness / 7.4：
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
Additional NP-complete Problems / 7.5：
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Exercises, Problems, arid Solutions
Space Complexity / 8：
SavitchÆs Theorem / 8.1：
The Class PSPACE / 8.2：
PSPACE-completeness / 8.3：
The TQBF problem
Winning strategies for games
Generalized geography
The Classes L and NL / 8.4：
NL-completeness / 8.5：
Searching in graphs
NL equals coNL / 8.6：
Intractability / 9：
Hierarchy Theorems / 9.1：
Exponential space completeness
Relativization / 9.2：
Limits of the diagonalization method
Circuit Complexity / 9.3：
Advanced Topics in Complexity Theory / 10：
Approximation Algorithms / 10.1：
Probabilistic Algorithms / 10.2：
The class BPP
Primality
Read-once branching programs
Alternation / 10.3：
Alternating time and space
The Polynomial time hierarchy
Interactive Proof Systems / 10.4：
Graph nonisomorphism
Definition of the model
IP = PSPACE
Parallel Computation / 10.5：
Uniform Boolean circuits
The class NC
P-completeness
Cryptography / 10.6：
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Selected Bibliography
Index
Preface to the First Edition
To the student
To the educator
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼