1.
|
図書
|
Roy Harris
出版情報: |
Ithaca, N.Y. : Cornell University Press, 1987 182 p. ; 23 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
2.
|
図書
|
Gregory J. Chaitin
|
3.
|
図書
|
Robin Milner
|
4.
|
図書
|
Frank S. Beckman
|
5.
|
図書
|
Gerard Lallement
|
6.
|
図書
|
by Václav Pinkava
出版情報: |
Cambridge, Mass. : Abacus Press, 1988 132 p. ; 25 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
7.
|
図書
|
W. Daniel Hillis
|
8.
|
図書
|
R.J. Nelson
出版情報: |
New York : Wiley, c1968 xii, 400 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
9.
|
図書
|
Michael Sipser
出版情報: |
Boston : PWS Pub., c1997 xv, 396 p. |
子書誌情報: |
loading… |
所蔵情報: |
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 |
|
10.
|
図書
|
James L. Hein
|
11.
|
図書
|
Michael A. Arbib, A.J. Kfoury, Robert N. Moll
|
12.
|
図書
|
Jeffrey R. Sampson
|
13.
|
図書
|
Seymour Ginsburg
|
14.
|
図書
|
B.I. Plotkin, L.Ja. Greenglaz, A.A. Gvaramija
出版情報: |
Singapore ; River Edge, N.J. : World Scientific, 1992 xiv, 280 p. ; 23 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
15.
|
図書
|
by Sze-Tsen Hu
出版情報: |
Berkeley : University of California Press, 1968 xiv, 261 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
16.
|
図書
|
Gérard Weisbuch ; translated by Sylvie Ryckebusch
|
17.
|
図書
|
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… |
所蔵情報: |
loading… |
|
18.
|
図書
|
J. P. Tremblay, R. Manohar
|
19.
|
図書
|
W.R. Ashby ... [et al.] ; edited by C.E. Shannon and J. McCarthy
|
20.
|
図書
|
John von Neumann ; edited and completed by Arthur W. Burks
出版情報: |
Urbana : University of Illinois Press, 1966 xix, 388 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
21.
|
図書
|
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… |
所蔵情報: |
loading… |
|
22.
|
図書
|
Wang, Hao, 1921-
出版情報: |
New York : Chelsea Pub. Co, [1970] x, 651 p ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
23.
|
図書
|
by Jiří Adámek and Věra Trnková
|
24.
|
図書
|
Franco P. Preparata, Raymond T. Yeh
|
25.
|
図書
|
Azriel Rosenfeld
|
26.
|
図書
|
Lokendra Shastri
|
27.
|
図書
|
John E. Hopcroft, Jeffrey D. Ullman
|
28.
|
図書
|
Rafael C. Gonzalez, Michael G. Thomason
|
29.
|
図書
|
Emile Aarts, Jan Korst
目次情報:
続きを見る
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 |
|
30.
|
図書
|
Peter J. Denning, Jack B. Dennis, Joseph E. Qualitz
出版情報: |
Englewood Cliffs, N.J. : Prentice-Hall, c1978 xxii, 601 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
31.
|
図書
|
Jorma Rissanen
|
32.
|
図書
|
W. Daniel Hillis
|
33.
|
図書
|
Erwin Engeler
|
34.
|
図書
|
Javed Ahsan, John N. Mordeson, and Muhammad Shabir
|
35.
|
図書
|
Ding-Zhu Du, Ker-I Ko
出版情報: |
New York : John Wiley & Sons, c2001 viii, 396 p. ; 25 cm |
子書誌情報: |
loading… |
所蔵情報: |
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: |
|
36.
|
図書
|
Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.)
|
37.
|
図書
|
Mark V. Lawson
出版情報: |
Boca Raton : Chapman & Hall/CRC, c2004 xii, 307 p. ; 25 cm |
子書誌情報: |
loading… |
所蔵情報: |
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: |
|
38.
|
図書
|
М.Л. Цетлин
出版情報: |
Москва : Изд-во "Наука", главная редакция физико-математической литературы, 1969 316 p. ; 21 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
39.
|
図書
|
Wilfried Brauer ... [et al.] (eds.)
目次情報:
続きを見る
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 |
|
40.
|
図書
|
[редколлегия, Г.Ф. Фрицнович (ответственный редактор) ... и др.]
出版情報: |
Рига : "Зинатне", 1967 225 p. ; 22 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
41.
|
図書
|
Aart Middeldorp ... [et al.] (eds.)
|
42.
|
図書
|
by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: |
Boston : Pearson Addison-Wesley, c2007 xvii, 535 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
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: |
|
43.
|
図書
|
John E. Savage
出版情報: |
New York : Wiley, c1976 xiii, 391 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
44.
|
図書
|
Werner Kuich, Arto Salomaa
|
45.
|
図書
|
R.E. Kalman, P.L. Falb, M.A. Arbib
|
46.
|
図書
|
[by] M.L. Tsetlin ; translated by Scitran (Scientific Translation Service)
|
47.
|
図書
|
[by] Richard Y. Kain
|
48.
|
図書
|
[by] Leonard S. Bobrow [and] Michael A. Arbib
出版情報: |
Philadelphia : Saunders, c1974 xiii, 719 p. ; 25 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
49.
|
図書
|
Marvin L. Minsky
|
50.
|
図書
|
[by] R.J. Nelson
出版情報: |
New York : Wiley, c1968 xii, 400 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
51.
|
図書
|
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
出版情報: |
Boston : Addison-Wesley, c2001 xiv, 521 p. ; 25 cm |
子書誌情報: |
loading… |
所蔵情報: |
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: |
|
52.
|
図書
|
[von] Peter H. Starke
出版情報: |
Berlin : Deutscher Verlag der Wissenschaften, 1969 392 p ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
53.
|
図書
|
Michael A. Arbib
|
54.
|
図書
|
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… |
所蔵情報: |
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: |
|
55.
|
EB
|
Paulo Tabuada ; foreword by Rajeev Alur
出版情報: |
[Cham] : SpringerLink, [20--] 1 online resource (xv, 202 p.) |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
目次情報:
続きを見る
Basic concepts / Part I: |
Systems / 1: |
System definition / 1.1: |
System behavior / 1.2: |
Examples / 1.3: |
Composing systems / 1.4: |
Notes / 1.5: |
Verification problems / 2: |
Sa $$ Sb / 2.1: |
Control problems / 2.2: |
Sc $$ Sa $$ Sb / 3.1: |
Finite systems / 3.2: |
Exact system relationships / 4: |
Behavioral relationships / 4.1: |
Similarity relationships / 4.2: |
Alternating similarity relationships / 4.3: |
Verification / 4.4: |
Behavioral relations / 5.1: |
Similarity relations / 5.2: |
Control / 5.3: |
Feedback composition / 6.1: |
Safety games / 6.2: |
Reachability games / 6.3: |
Behavioral games / 6.4: |
Similarity games / 6.5: |
Infinite Systems: Exact symbolic models / 6.6: |
Exact symbolic models for verification / 7: |
Dynamical and hybrid dynamical systems as systems / 7.1: |
Timed automata / 7.2: |
Order minimal hybrid dynamical systems / 7.3: |
Sign based abstractions / 7.4: |
Barrier certificates / 7.5: |
Computation of reachable sets / 7.6: |
Advanced topics / 7.7: |
Exact symbolic models for control / 7.8: |
Control systems as systems / 8.1: |
Controller refinement / 8.2: |
Discrete-time linear control systems / 8.3: |
Continuous-time multi-affine control systems / 8.4: |
Infinite Systems: Approximate symbolic models / 8.5: |
Approximate system relationships / 9: |
Approximate similarity relationships / 9.1: |
Approximate alternating similarity relationships / 9.2: |
Approximate symbolic models for verification / 9.3: |
Stability of linear dynamical systems / 10.1: |
Dynamical systems as systems / 10.2: |
Symbolic models for affine dynamical systems / 10.3: |
Approximate symbolic models for control / 10.4: |
Stability of linear control systems / 11.1: |
Control and switched systems as systems / 11.2: |
Approximate feedback composition and controller refinement / 11.3: |
Symbolic models for affine control systems / 11.4: |
Symbolic models for switched affine systems / 11.5: |
Appendix / 11.6: |
Lattice theory / A.1: |
Fixed-points / A.2: |
References |
Index |
Basic concepts / Part I: |
Systems / 1: |
System definition / 1.1: |
|
56.
|
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… |
所蔵情報: |
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: |
|
57.
|
EB
|
Derek F. Holt, University of Warwick, Sarah Rees, University of Newcastle upon Tyne, Claas E. Röver, National University of Ireland, Galway
出版情報: |
1 online resource (xi, 294 p.) |
シリーズ名: |
London Mathematical Society student texts ; 88 |
子書誌情報: |
loading… |
所蔵情報: |
loading… |
|
58.
|
EB
|
Michael Sipser
出版情報: |
[東京] : Maruzen eBook Library 1 online resource (xxii, 458 p) |
子書誌情報: |
loading… |
所蔵情報: |
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 |
|
59.
|
図書
|
Michael Sipser
出版情報: |
Boston, MA : Cengage Learning, c2013 xxii, 458 p. ; 24 cm |
子書誌情報: |
loading… |
所蔵情報: |
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 |
|
60.
|
図書
|
[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… |
所蔵情報: |
loading… |
|
61.
|
図書
|
John E. Hopcroft, Jeffrey D. Ullman
目次情報:
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 |
|