close
1.

図書

図書
Roy Harris
出版情報: Ithaca, N.Y. : Cornell University Press, 1987  182 p. ; 23 cm
所蔵情報: loading…
2.

図書

図書
Gregory J. Chaitin
出版情報: Singapore ; Teaneck, NJ : World Scientific, c1987  x, 272 p. ; 23 cm
シリーズ名: Series in computer science ; v. 8
所蔵情報: loading…
3.

図書

図書
Robin Milner
出版情報: Berlin ; New York : Springer-Verlag, 1980  vi, 171 p. ; 25 cm
シリーズ名: Lecture notes in computer science ; 92
所蔵情報: loading…
4.

図書

図書
Michael A. Arbib
出版情報: New York ; Tokyo : Springer-Verlag, c1987  xvi, 202 p. ; 25 cm
所蔵情報: loading…
5.

図書

図書
Frank S. Beckman
出版情報: Reading, MA : Addison-Wesley, c1980  xviii, 443 p. ; 25 cm
シリーズ名: The systems programming series
所蔵情報: loading…
6.

図書

図書
Gerard Lallement
出版情報: New York : Wiley, c1979  xi, 376 p. ; 24 cm
シリーズ名: Pure and applied mathematics
所蔵情報: loading…
7.

図書

図書
by Václav Pinkava
出版情報: Cambridge, Mass. : Abacus Press, 1988  132 p. ; 25 cm
所蔵情報: loading…
8.

図書

図書
W. Daniel Hillis
出版情報: Cambridge, Mass. : MIT Press, c1985  xiii, 190 p. ; 24 cm
シリーズ名: The MIT Press series in artificial intelligence
所蔵情報: loading…
9.

図書

図書
R.J. Nelson
出版情報: New York : Wiley, c1968  xii, 400 p. ; 24 cm
所蔵情報: loading…
10.

図書

図書
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
11.

図書

図書
James L. Hein
出版情報: Sudbury, Mass. : Jones and Bartlett Publishers, c1996  xvii, 572 p. ; 25 cm
シリーズ名: Jones and Bartlett books in computer science
所蔵情報: loading…
12.

図書

図書
Michael A. Arbib, A.J. Kfoury, Robert N. Moll
出版情報: New York : Springer-Verlag, c1981  viii, 220 p. ; 24 cm
シリーズ名: Texts and monographs in computer science ; . The AKM series in theoretical computer science
所蔵情報: loading…
13.

図書

図書
Jeffrey R. Sampson
出版情報: New York : Springer-Verlag, 1976  x, 214 p. ; 24 cm
シリーズ名: Texts and monographs in computer science
所蔵情報: loading…
14.

図書

図書
Seymour Ginsburg
出版情報: Reading, Mass. : Addison-Wesley Pub. Co, [1962]  ix, 148 p. ; 24 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
15.

図書

図書
B.I. Plotkin, L.Ja. Greenglaz, A.A. Gvaramija
出版情報: Singapore ; River Edge, N.J. : World Scientific, 1992  xiv, 280 p. ; 23 cm
所蔵情報: loading…
16.

図書

図書
by Sze-Tsen Hu
出版情報: Berkeley : University of California Press, 1968  xiv, 261 p. ; 24 cm
所蔵情報: loading…
17.

図書

図書
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…
18.

図書

図書
edited by Stephen L. Bloom ; with a foreword by Dana S. Scott and‘A glimpse back' by Samuel Eilenberg
出版情報: New York ; Heidelberg ; Berlin : Springer-Verlag, c1982  xxiv, 460 p. ; 25 cm
所蔵情報: loading…
19.

図書

図書
J. P. Tremblay, R. Manohar
出版情報: New York : McGraw-Hill, [1975]  xvi, 606 p. ; 24 cm
シリーズ名: McGraw-Hill computer science series
所蔵情報: loading…
20.

図書

図書
W.R. Ashby ... [et al.] ; edited by C.E. Shannon and J. McCarthy
出版情報: Princeton : Princeton University Press, c1956  viii, 285 p. ; 26 cm
シリーズ名: Annals of mathematics studies ; no. 34
所蔵情報: loading…
21.

図書

図書
John von Neumann ; edited and completed by Arthur W. Burks
出版情報: Urbana : University of Illinois Press, 1966  xix, 388 p. ; 24 cm
所蔵情報: loading…
22.

図書

図書
edited by Madan M. Gupta, with associate editors George N. Saridis, Brian R. Gaines
出版情報: New York : North-Holland, c1977  xiv, 496 p. ; 24 cm
所蔵情報: loading…
23.

図書

図書
Wang, Hao, 1921-
出版情報: New York : Chelsea Pub. Co, [1970]  x, 651 p ; 24 cm
所蔵情報: loading…
24.

図書

図書
by Jiří Adámek and Věra Trnková
出版情報: Dordrecht ; Boston : Kluwer Academic Publishers, c1990  xiv, 470 p. ; 25 cm
シリーズ名: Mathematics and its applications ; . East European series ; [v. 37]
所蔵情報: loading…
25.

図書

図書
Arthur Gill
出版情報: Englewood Cliffs, N.J. : Prentice-Hall, c1976  xv, 432 p. ; 24 cm
シリーズ名: Prentice-Hall series in automatic computation
所蔵情報: loading…
26.

図書

図書
Franco P. Preparata, Raymond T. Yeh
出版情報: Reading, Mass. : Addison-Wesley, c1973  xi, 354 p. ; 25 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
27.

図書

図書
Azriel Rosenfeld
出版情報: New York : Academic Press, 1979  xiii, 225 p. ; 24 cm
シリーズ名: Computer science and applied mathematics
所蔵情報: loading…
28.

図書

図書
Lokendra Shastri
出版情報: London : Pitman , Los Altos, Calif. : M. Kaufmann, 1988  222 p. ; 25 cm
シリーズ名: Research notes in artificial intelligence
所蔵情報: loading…
29.

図書

図書
John E. Hopcroft, Jeffrey D. Ullman
出版情報: Reading, Mass. : Addison-Wesley Pub. Co., c1969  vii, 242 p. ; 24 cm
シリーズ名: Addison-Wesley series in computer science and information processing
所蔵情報: loading…
30.

図書

図書
Rafael C. Gonzalez, Michael G. Thomason
出版情報: Reading, Mass. : Addison-Wesley Pub. Co., Advanced Book Program, 1978  xix, 283 p. ; 24 cm
シリーズ名: Applied mathematics and computation : a series of graduate textbooks, monographs, reference works / Series Editor Robert Kalaba ; no. 14
所蔵情報: loading…
31.

図書

図書
Emile Aarts, Jan Korst
出版情報: Chichester, England : Wiley, c1989  xii, 272 p. ; 25 cm
シリーズ名: Wiley-Interscience series in discrete mathematics and optimization
所蔵情報: loading…
目次情報: 続きを見る
Simulated Annealing
Combinatorial Optimization
Asymptotic Convergence
Finite-Time Approximation
Simulated Annealing in Practice
Parallel Simulated Annealing Algorithms
Boltzmann Machines
Neural Computing
Combinatorial Optimization and Boltzmann Machines
Classification and Boltzmann Machines
Learning and Boltzmann Machines
Appendix
Bibliography
Indices
Simulated Annealing
Combinatorial Optimization
Asymptotic Convergence
32.

図書

図書
Peter J. Denning, Jack B. Dennis, Joseph E. Qualitz
出版情報: Englewood Cliffs, N.J. : Prentice-Hall, c1978  xxii, 601 p. ; 24 cm
所蔵情報: loading…
33.

図書

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

図書

図書
W. Daniel Hillis
出版情報: Cambridge, Mass. : MIT Press, 1989  xiii, 190 p. ; 24 cm
シリーズ名: ACM distinguished dissertations ; 1985
所蔵情報: loading…
35.

図書

図書
W.M.L. Holcombe
出版情報: Cambridge : Cambridge University Press, 1982  xi, 228 p. ; 24 cm
シリーズ名: Cambridge studies in advanced mathematics ; 1
所蔵情報: loading…
目次情報: 続きを見る
Introduction
Semigroups and their relatives / 1:
Machines and semigroups / 2:
Decompositions / 3:
The holonomy decomposition / 4:
Recognizers / 5:
Sequential machines and functions / 6:
Appendix
References
Index of notation
Index
Introduction
Semigroups and their relatives / 1:
Machines and semigroups / 2:
36.

図書

図書
Michael A. Arbib
出版情報: New York : McGraw-Hill, c1964  xiv, 152 p. ; 21 cm
所蔵情報: loading…
37.

図書

図書
Erwin Engeler
出版情報: Chicago : Markham Pub. Co, c1968  vii, 81 p. ; 22 cm
シリーズ名: Lectures in advanced mathematics ; 3
所蔵情報: loading…
38.

図書

図書
Robert W. Floyd, Richard Beigel
出版情報: New York : Computer Science Press, c1994  xvii, 706 p. ; 25 cm
所蔵情報: loading…
39.

図書

図書
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…
40.

図書

図書
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:
41.

図書

図書
Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.)
出版情報: Berlin ; Tokyo : Springer, c2002  viii, 385 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 2500
所蔵情報: loading…
42.

図書

図書
Mark V. Lawson
出版情報: Boca Raton : Chapman & Hall/CRC, c2004  xii, 307 p. ; 25 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Introduction to finite automata / 1:
Alphabets and strings / 1.1:
Languages / 1.2:
Language operations / 1.3:
Finite automata: motivation / 1.4:
Finite automata and their languages / 1.5:
Summary of Chapter 1 / 1.6:
Remarks on Chapter 1 / 1.7:
Recognisable languages / 2:
Designing automata / 2.1:
Incomplete automata / 2.2:
Automata that count / 2.3:
Automata that locate patterns / 2.4:
Boolean operations / 2.5:
The Pumping Lemma / 2.6:
Summary of Chapter 2 / 2.7:
Remarks on Chapter 2 / 2.8:
Non-deterministic automata / 3:
Accessible automata / 3.1:
Applications / 3.2:
Trim automata / 3.4:
Grammars / 3.5:
Summary of Chapter 3 / 3.6:
Remarks on Chapter 3 / 3.7:
[varepsilon]-automata / 4:
Automata with [varepsilon]-transitions / 4.1:
Applications of [varepsilon]-automata / 4.2:
Summary of Chapter 4 / 4.3:
Remarks on Chapter 4 / 4.4:
Kleene's Theorem / 5:
Regular languages / 5.1:
Kleene's theorem: proof / 5.2:
Kleene's theorem: algorithms / 5.3:
Language equations / 5.4:
Summary of Chapter 5 / 5.5:
Remarks on Chapter 5 / 5.6:
Local languages / 6:
Myhill graphs / 6.1:
Linearisation / 6.2:
Summary of Chapter 6 / 6.3:
Remarks on Chapter 6 / 6.4:
Minimal automata / 7:
Partitions and equivalence relations / 7.1:
The indistinguishability relation / 7.2:
Isomorphisms of automata / 7.3:
The minimal automaton / 7.4:
The method of quotients / 7.5:
Summary of Chapter 7 / 7.6:
Remarks on Chapter 7 / 7.7:
The transition monoid / 8:
Functions on states / 8.1:
The extended transition table / 8.2:
The Cayley table of an automaton / 8.3:
Semigroups and monoids / 8.4:
Summary of Chapter 8 / 8.5:
Remarks on Chapter 8 / 8.6:
The syntactic monoid / 9:
Introduction to semigroups / 9.1:
Congruences / 9.2:
The transition monoid of an automaton / 9.3:
The syntactic monoid of a language / 9.4:
Summary of Chapter 9 / 9.5:
Remarks on Chapter 9 / 9.6:
Algebraic language theory / 10:
Finite semigroups / 10.1:
Recognisability by a monoid / 10.2:
Two counterexamples / 10.3:
Summary of Chapter 10 / 10.4:
Remarks on Chapter 10 / 10.5:
Star-free languages / 11:
Introduction / 11.1:
Groups / 11.2:
Aperiodic semigroups / 11.3:
Schutzenberger's theorem / 11.4:
An example / 11.5:
Summary of Chapter 11 / 11.6:
Remarks on Chapter 11 / 11.7:
Varieties of languages / 12:
Pseudovarieties and varieties / 12.1:
Equations for pseudovarieties / 12.2:
Summary of Chapter 12 / 12.3:
Remarks on Chapter 12 / 12.4:
Discrete mathematics / A:
Logic and proofs / A.1:
Set theory / A.2:
Numbers and matrices / A.3:
Graphs / A.4:
Functions / A.5:
Relations / A.6:
Bibliography
Index
Preface
Introduction to finite automata / 1:
Alphabets and strings / 1.1:
43.

図書

図書
М.Л. Цетлин
出版情報: Москва : Изд-во "Наука", главная редакция физико-математической литературы, 1969  316 p. ; 21 cm
所蔵情報: loading…
44.

図書

図書
Wilfried Brauer ... [et al.] (eds.)
出版情報: Berlin : Springer, c2002  xxxvi, 429 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 2300
所蔵情報: loading…
目次情報: 続きを見る
Bibliography of Grzegorz Rozenberg
Words, Languages, Automata / I:
Balanced Grammars and Their Languages / Jean Berstel ; Luc Boasson
Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids / Volker Diekert ; Paul Gastin
The Delta Operation: From Strings to Trees to Strings / Joost Engelfriet
Infinite Solutions of Marked Post Correspondence Problem / Vesa Halava ; Tero Harju
The Branching Point Approach to ConwayÆs Problem / Juhani Karhumaki ; Ion Petre
A Survey of Some Quantitative Approaches to the Notion of Information / Aldo de Luca
Nondeterministic Trajectories / Alexandru Mateescu ; Arto Salomaa
Binary Patterns in Infinite Binary Words / Antonio Restivo ; Sergio Salemi
Graph Transformations / II:
A Sight-seeing Tour of the Computational Landscape of Graph Transformation / Hans-Jörg Kreowski
Local Action Systems and DPO Graph Transformation / DirkJanssens
Bisimulation Equivalences for Graph Grammars / Paolo Baldan ; Andrea Corradini ; Ugo Montanari
Petri Nets / III:
High-Level Net Processes / Hartmut Ehrig ; Kathrin Hoffmann ; Julia Padberg ; Reiko Heckel
Petri Net Control for Grammar Systems / Maurice ter Beek ; Jetty Kleijn
Regular Event Structures and Finite Petri Nets: A Conjecture / P.S. Thiagarajan
Concurrent Computing / IV:
Towards Team-Automata-Driven Object-Oriented Collaborative Work / Gregor Engels ; LuukGroenewegen
Grammars as Processes / Javier Esparza
Temporal Concurrent Constraint Programming: Applications and Behavior / Mogens Nielsen ; FrankD. Valencia
Molecular Computing / V:
Rewriting P Systems with Conditional Communication / Paolo Bottoni ; Anna Labella ; Carlos Martín-Vide ; Gheorghe Paun
An Aqueous Algorithm for Finding the Bijections Contained in a Binary Relation / Tom Head
Upper Bounds for Restricted Splicing / HendrikJan Hoogeboom ; Nikè van Vugt
Codes, Involutions, and DNA Encodings / Lila Kari ; Rob Kitto ; Gabriel Thierrin
DNA Manipulations in Ciliates / David M. Prescott
A Magic Pot Self-assembly Computation Revisited / Takashi Yokomori ; Yasubumi Sakakibara ; Satoshi Kobayashi
Author Index
Bibliography of Grzegorz Rozenberg
Words, Languages, Automata / I:
Balanced Grammars and Their Languages / Jean Berstel ; Luc Boasson
45.

図書

図書
[редколлегия, Г.Ф. Фрицнович (ответственный редактор) ... и др.]
出版情報: Рига : "Зинатне", 1967  225 p. ; 22 cm
所蔵情報: loading…
46.

図書

図書
Aart Middeldorp ... [et al.] (eds.)
出版情報: Berlin : Springer, c2005  xviii, 638 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 3838
所蔵情報: loading…
47.

図書

図書
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:
48.

図書

図書
John E. Savage
出版情報: New York : Wiley, c1976  xiii, 391 p. ; 24 cm
所蔵情報: loading…
49.

図書

図書
Abraham Kandel, Samuel C. Lee
出版情報: New York : Crane Russak, c1979  x, 303 p. ; 24 cm
シリーズ名: Computer systems engineering series
所蔵情報: loading…
50.

図書

図書
Werner Kuich, Arto Salomaa
出版情報: Berlin ; Tokyo : Springer-Verlag, c1986  374 p. ; 25 cm
シリーズ名: EATCS monographs on theoretical computer science ; v. 5
所蔵情報: loading…
51.

図書

図書
R.E. Kalman, P.L. Falb, M.A. Arbib
出版情報: New York : McGraw-Hill, c1969  xiv, 358 p. ; 23 cm
シリーズ名: International series in pure and applied mathematics
所蔵情報: loading…
52.

図書

図書
[by] M.L. Tsetlin ; translated by Scitran (Scientific Translation Service)
出版情報: New York : Academic Press, c1973  xvi, 288 p. ; 24 cm
シリーズ名: Mathematics in science and engineering : a series of monographs and textbooks ; v. 102
所蔵情報: loading…
53.

図書

図書
[by] Richard Y. Kain
出版情報: New York : McGraw-Hill, [1972]  xvii, 301 p. ; 24 cm
シリーズ名: McGraw-Hill computer science series
所蔵情報: loading…
54.

図書

図書
[by] Leonard S. Bobrow [and] Michael A. Arbib
出版情報: Philadelphia : Saunders, c1974  xiii, 719 p. ; 25 cm
所蔵情報: loading…
55.

図書

図書
Marvin L. Minsky
出版情報: Englewood Cliffs, N.J. : Prentice-Hall, c1967  xvii, 317 p. ; 24 cm
シリーズ名: Prentice-Hall series in automatic computation
所蔵情報: loading…
56.

図書

図書
[by] R.J. Nelson
出版情報: New York : Wiley, c1968  xii, 400 p. ; 24 cm
所蔵情報: loading…
57.

図書

図書
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:
58.

図書

図書
[von] Peter H. Starke
出版情報: Berlin : Deutscher Verlag der Wissenschaften, 1969  392 p ; 24 cm
所蔵情報: loading…
59.

図書

図書
Michael A. Arbib
出版情報: Englewood Cliffs, N.J. : Prentice-Hall, 1969  xiii, 412 p. ; 24 cm
シリーズ名: Prentice-Hall series in automatic computation
所蔵情報: loading…
60.

図書

図書
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:
61.

図書

図書
Keith Clark, Don Cowell
出版情報: London ; New York : McGraw-Hill, c1976  xi, 176 p. ; 24 cm
所蔵情報: loading…
62.

図書

図書
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
63.

図書

図書
[by] Peter H. Starke ; [translated from the German by I. Shepherd]
出版情報: Amsterdam : North-Holland Pub. Co. , New York : American Elsevier Pub. Co., 1972  419 p. ; 23 cm
所蔵情報: loading…
64.

図書

図書
John E. Hopcroft, Jeffrey D. Ullman
出版情報: Reading, Mass. : Addison-Wesley, c1979  x, 418 p. ; 25 cm
シリーズ名: Addison-Wesley series in computer science
所蔵情報: loading…
目次情報:
It includes end-of-chapter questions, bibliographies, and exercises
Problems of highest and intermediate difficulty are marked respectively with double or single stars. 020102988XB04062001
It includes end-of-chapter questions, bibliographies, and exercises
Problems of highest and intermediate difficulty are marked respectively with double or single stars. 020102988XB04062001
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼