close
1.

図書

図書
Javed Ahsan, John N. Mordeson, and Muhammad Shabir
出版情報: Berlin ; New York : Springer, c2012  xv, 227 p. ; 25 cm
シリーズ名: Studies in fuzziness and soft computing ; v. 278
所蔵情報: loading…
2.

電子ブック

EB
edited by A. Arnold, D. Niwiński
出版情報: Elsevier : Amsterdam, c2019  1 online resource (xi, 277 p.)
シリーズ名: Studies in logic and the foundations of mathematics ; v. 146
所蔵情報: loading…
目次情報: 続きを見る
Complete lattices and fixed-point theorems / 1:
The mu-calculi: Syntax and semantics / 2:
The Boolean mu-calculus / 3:
Parity Games / 4:
The mu-calculus on words / 5:
The mucalculus over powerset al.gebras / 6:
The mu-calculus versus automata / 7:
Hierachy problems / 8:
Distributivity and normal form results / 9:
Decision problems / 10:
Algorithms / 11:
Complete lattices and fixed-point theorems / 1:
The mu-calculi: Syntax and semantics / 2:
The Boolean mu-calculus / 3:
3.

図書

図書
Michael Sipser
出版情報: Boston, MA : Cengage Learning, c2013  xxii, 458 p. ; 24 cm
所蔵情報: 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
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼