close
1.

図書

図書
Noga Alon, Joel H. Spencer ; with an appendix on open problems by Paul Erdős
出版情報: New York : Wiley, c1992  xiii, 254 p. ; 25 cm
シリーズ名: Wiley-Interscience series in discrete mathematics and optimization
所蔵情報: loading…
目次情報: 続きを見る
Methods
The Basic Method
Linearity of Expectation
Alterations
The Second Moment
The Local Lemma
Correlation Inequalities
Martingales and Tight Concentration
The Poisson Paradigm
Pseudo-Randomness
Topics
Random Graphs
Circuit Complexity
Discrepancy
Geometry
Codes, Games and Entropy
Derandomization
Appendices
Indexes
References
Methods
The Basic Method
Linearity of Expectation
2.

図書

図書
by Paul Erdős and Joel Spencer
出版情報: New York : Academic Press, 1974  106 p. ; 24 cm
シリーズ名: Probability and mathematical statistics : a series of monographs and textbooks ; 17
所蔵情報: loading…
3.

図書

図書
Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer
出版情報: New York : Wiley, c1980  ix, 174 p. ; 24 cm
シリーズ名: Wiley-Interscience series in discrete mathematics
所蔵情報: loading…
4.

図書

図書
Joel Spencer
出版情報: Philadelphia, Pa. : Society for Industrial and Applied Mathematics, 1994  vi, 88 p. ; 26 cm
シリーズ名: CBMS-NSF regional conference series in applied mathematics ; 64
所蔵情報: loading…
5.

図書

図書
D.A. Dawson, B. Maisonneuve, J. Spencer ; editor, P.L. Hennequin
出版情報: Berlin ; Tokyo : Springer-Verlag, c1993  viii, 356 p. ; 25 cm
シリーズ名: Lecture notes in mathematics ; 1541
所蔵情報: loading…
6.

電子ブック

EB
Erich Gr?del, W. Brauer, J. Hromkovic, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein
出版情報: Springer eBooks Computer Science , Springer Berlin Heidelberg, 2007
所蔵情報: loading…
目次情報: 続きを見る
Unifying Themes in Finite Model Theory / 1:
Definability Theory / 1.1:
Classification of Concepts in Terms of Definitional Complexity / 1.1.1:
What More Do We Know When We Know a Concept Is L-Definable? / 1.1.2:
Logics with Finitely Many Variables / 1.1.3:
Distinguishing Structures: L-Equivalence and Comparison Games / 1.1.4:
Random Graphs and 0-1 Laws / 1.1.5:
Constraint Satisfaction Problems / 1.1.6:
Descriptive Complexity / 1.2:
Satisfaction / 1.2.1:
What Is a Logic for PTIME? / 1.2.2:
Finite Model Theory and Infinite Structures / 1.3:
Tame Fragments and Tame Classes / 1.4:
References
On the Expressive Power of Logics on Finite Models / 2:
Introduction / 2.1:
Basic Concepts / 2.2:
Ehrenfeucht-Fraisse Games for First-Order Logic / 2.3:
Computational Complexity / 2.4:
Complexity Classes / 2.4.1:
The Complexity of Logic / 2.4.2:
Ehrenfeucht-Fraisse Games for Existential Second-Order Logic / 2.5:
Logics with Fixed-Point Operators / 2.6:
Operators and Fixed Points / 2.6.1:
Least Fixed-Point Logic / 2.6.2:
Datalog and Datalog([NotEqual]) / 2.6.3:
The Complementation Problem for LFP[subscript 1] and a Normal Form for LFP / 2.6.4:
Partial Fixed-Point Logic / 2.6.5:
Infinitary Logics with Finitely Many Variables / 2.7:
The Infinitary Logic L[Characters not reproducible] / 2.7.1:
Pebble Games and L[Characters not reproducible]-Definability / 2.7.2:
0-1 Laws for L[Characters not reproducible] / 2.7.3:
Definability and Complexity of L[Characters not reproducible]-Equivalence / 2.7.4:
Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structures / 2.7.5:
Existential Infinitary Logics with Finitely Many Variables / 2.8:
The Infinitary Logics [Characters not reproducible] and [Characters not reproducible] ([NotEqual]) / 2.8.1:
Existential Pebble Games / 2.8.2:
Descriptive Complexity of Fixed Subgraph Homeomorphism Queries / 2.8.3:
Finite Model Theory and Descriptive Complexity / 3:
Definability and Complexity / 3.1:
Complexity Issues in Logic / 3.1.1:
Model Checking for First-Order Logic / 3.1.2:
The Strategy Problem for Finite Games / 3.1.3:
Complexity of First-Order Model Checking / 3.1.4:
Encoding Finite Structures by Words / 3.1.5:
Capturing Complexity Classes / 3.2:
Capturing NP: Fagin's Theorem / 3.2.1:
Logics That Capture Complexity Classes / 3.2.2:
Capturing Polynomial Time on Ordered Structures / 3.2.3:
Capturing Logarithmic Space Complexity / 3.2.4:
Transitive Closure Logics / 3.2.5:
Fixed-Point Logics / 3.3:
Some Fixed-Point Theory / 3.3.1:
The Modal [mu]-Calculus / 3.3.2:
Parity Games / 3.3.4:
Model-Checking Games for Least Fixed-Point Logic / 3.3.5:
Definability of Winning Regions in Parity Games / 3.3.6:
Simultaneous Fixed-Point Inductions / 3.3.7:
Inflationary Fixed-Point Logic / 3.3.8:
Datalog and Stratified Datalog / 3.3.9:
Logics with Counting / 3.4:
Logics with Counting Terms / 3.4.1:
Fixed-Point Logic with Counting / 3.4.2:
Datalog with Counting / 3.4.3:
Capturing PTIME via Canonization / 3.5:
Definable Linear Orders / 3.5.1:
Canonizations and Interpretations / 3.5.2:
Capturing PTIME up to Bisimulation / 3.5.3:
Is There a Logic for PTIME? / 3.5.4:
Algorithmic Model Theory / 3.6:
Beyond Finite Structures / 3.6.1:
Finitely Presentable Structures / 3.6.2:
Metafinite Structures / 3.6.3:
Metafinite Spectra / 3.6.4:
Descriptive Complexity over the Real Numbers / 3.6.5:
Appendix: Alternating Complexity Classes / 3.7:
Logic and Random Structures / 4:
An Instructive Example / 4.1:
Random Graphs / 4.2:
Extension Statements / 4.3:
Closure / 4.4:
The Almost Sure Theory / 4.5:
The Case p Constant / 4.6:
Countable Models / 4.7:
A Dynamic View / 4.8:
Infinite Spectra via Almost Sure Encoding / 4.9:
The Jump Condition / 4.10:
The Complexity Condition / 4.11:
Nonconvergence via Almost Sure Encoding / 4.12:
No Almost Sure Representation of Evenness / 4.13:
The Ehrenfeucht Game / 4.14:
About the References / 4.15:
Embedded Finite Models and Constraint Databases / 5:
Organization / 5.1:
Relational Databases and Embedded Finite Models / 5.2:
Constraint Databases / 5.3:
Collapse and Genericity: An Overview / 5.4:
Approaches to Proving Expressivity Bounds / 5.4.1:
Active-Generic Collapse / 5.5:
The Ramsey Property / 5.5.1:
Collapse Results / 5.5.2:
Natural-Active Collapse / 5.6:
Collapse: Failure and Success / 5.6.1:
Good Structures vs. Bad Structures: O-minimality / 5.6.2:
Collapse Theorem and Corollaries / 5.6.3:
Collapse Algorithm: the Linear Case / 5.6.4:
Collapse Algorithm: the General Case / 5.6.5:
Collapse Without O-minimality / 5.6.6:
Natural-Generic Collapse / 5.6.7:
Model Theory and Collapse Results / 5.7:
Pseudo-finite Homogeneity / 5.7.1:
Finite Cover Property and Collapse / 5.7.2:
Isolation and Collapse / 5.7.3:
The VC Dimension and Collapse Results / 5.8:
Random Graph and Collapse to MSO / 5.8.1:
Complexity Bounds for Generic Queries / 5.8.2:
Expressiveness of Constraint Query Languages / 5.9:
Reductions to the Finite Case / 5.9.1:
Topological Properties / 5.9.2:
Linear vs. Polynomial Constraints / 5.9.3:
Query Safety / 5.10:
Finite and Infinite Query Safety / 5.10.1:
Safe Translations / 5.10.2:
Finite Query Safety: Characterization / 5.10.3:
Infinite Query Safety: Reduction / 5.10.4:
Deciding Safety / 5.10.5:
Dichotomy Theorem for Embedded Finite Models / 5.10.6:
Database Considerations / 5.11:
Aggregate Operators / 5.11.1:
Higher-Order Features / 5.11.2:
Bibliographic Notes / 5.12:
A Logical Approach to Constraint Satisfaction / 6:
Preliminaries / 6.1:
The Computational Complexity of Constraint Satisfaction / 6.3:
Nonuniform Constraint Satisfaction / 6.4:
Monotone Monadic SNP and Nonuniform Constraint Satisfaction / 6.5:
Datalog and Nonuniform Constraint Satisfaction / 6.6:
Datalog, Games, and Constraint Satisfaction / 6.7:
Games and Consistency / 6.8:
Uniform Constraint Satisfaction and Bounded Treewidth / 6.9:
Local Variations on a Loose Theme: Modal Logic and Decidability / 7:
Modal Systems and Bisimulations / 7.1:
Basic Modal Logic / 7.3:
Notes / 7.3.1:
Some Variations / 7.4:
Neither Locality nor Looseness: Grid Logics / 7.4.1:
Universal Access: K / 7.4.2:
Generalizing Looseness: the Until Operator / 7.4.3:
Modal Complexity / 7.5:
NP and the Polysize Model Property / 7.5.1:
PSPACE and Polynomially Deep Paths / 7.5.2:
EXPTIME and Exponentially Deep Paths / 7.5.3:
NEXPTIME / 7.5.4:
Modal Logic and First-Order Logic / 7.5.5:
Guarded Fragments / 7.6.1:
Decidability and Complexity / 7.6.2:
Index / 7.6.3:
Unifying Themes in Finite Model Theory / 1:
Definability Theory / 1.1:
Classification of Concepts in Terms of Definitional Complexity / 1.1.1:
7.

図書

図書
edited by Joel Spencer
出版情報: Cambridge, Mass. : MIT Press, c1973  xxiii, 742 p. ; 26 cm
シリーズ名: Mathematicians of our time ; v. 5
所蔵情報: loading…
8.

図書

図書
Noga Alon, Joel H. Spencer
出版情報: Hoboken, New Jersey : Wiley, c2016  xiv, 375 p. ; 25 cm
シリーズ名: Wiley-Interscience series in discrete mathematics and optimization
所蔵情報: loading…
9.

電子ブック

EB
Erich Grädel, W. Brauer, J. Hromkovic, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein, M. Marx, G. Rozenberg, J. Spencer, Scott A. Weinstein
出版情報: SpringerLink Books - AutoHoldings , Springer Berlin Heidelberg, 2007
所蔵情報: loading…
目次情報: 続きを見る
Unifying Themes in Finite Model Theory / 1:
Definability Theory / 1.1:
Classification of Concepts in Terms of Definitional Complexity / 1.1.1:
What More Do We Know When We Know a Concept Is L-Definable? / 1.1.2:
Logics with Finitely Many Variables / 1.1.3:
Distinguishing Structures: L-Equivalence and Comparison Games / 1.1.4:
Random Graphs and 0-1 Laws / 1.1.5:
Constraint Satisfaction Problems / 1.1.6:
Descriptive Complexity / 1.2:
Satisfaction / 1.2.1:
What Is a Logic for PTIME? / 1.2.2:
Finite Model Theory and Infinite Structures / 1.3:
Tame Fragments and Tame Classes / 1.4:
References
On the Expressive Power of Logics on Finite Models / 2:
Introduction / 2.1:
Basic Concepts / 2.2:
Ehrenfeucht-Fraisse Games for First-Order Logic / 2.3:
Computational Complexity / 2.4:
Complexity Classes / 2.4.1:
The Complexity of Logic / 2.4.2:
Ehrenfeucht-Fraisse Games for Existential Second-Order Logic / 2.5:
Logics with Fixed-Point Operators / 2.6:
Operators and Fixed Points / 2.6.1:
Least Fixed-Point Logic / 2.6.2:
Datalog and Datalog([NotEqual]) / 2.6.3:
The Complementation Problem for LFP[subscript 1] and a Normal Form for LFP / 2.6.4:
Partial Fixed-Point Logic / 2.6.5:
Infinitary Logics with Finitely Many Variables / 2.7:
The Infinitary Logic L[Characters not reproducible] / 2.7.1:
Pebble Games and L[Characters not reproducible]-Definability / 2.7.2:
0-1 Laws for L[Characters not reproducible] / 2.7.3:
Definability and Complexity of L[Characters not reproducible]-Equivalence / 2.7.4:
Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structures / 2.7.5:
Existential Infinitary Logics with Finitely Many Variables / 2.8:
The Infinitary Logics [Characters not reproducible] and [Characters not reproducible] ([NotEqual]) / 2.8.1:
Existential Pebble Games / 2.8.2:
Descriptive Complexity of Fixed Subgraph Homeomorphism Queries / 2.8.3:
Finite Model Theory and Descriptive Complexity / 3:
Definability and Complexity / 3.1:
Complexity Issues in Logic / 3.1.1:
Model Checking for First-Order Logic / 3.1.2:
The Strategy Problem for Finite Games / 3.1.3:
Complexity of First-Order Model Checking / 3.1.4:
Encoding Finite Structures by Words / 3.1.5:
Capturing Complexity Classes / 3.2:
Capturing NP: Fagin's Theorem / 3.2.1:
Logics That Capture Complexity Classes / 3.2.2:
Capturing Polynomial Time on Ordered Structures / 3.2.3:
Capturing Logarithmic Space Complexity / 3.2.4:
Transitive Closure Logics / 3.2.5:
Fixed-Point Logics / 3.3:
Some Fixed-Point Theory / 3.3.1:
The Modal [mu]-Calculus / 3.3.2:
Parity Games / 3.3.4:
Model-Checking Games for Least Fixed-Point Logic / 3.3.5:
Definability of Winning Regions in Parity Games / 3.3.6:
Simultaneous Fixed-Point Inductions / 3.3.7:
Inflationary Fixed-Point Logic / 3.3.8:
Datalog and Stratified Datalog / 3.3.9:
Logics with Counting / 3.4:
Logics with Counting Terms / 3.4.1:
Fixed-Point Logic with Counting / 3.4.2:
Datalog with Counting / 3.4.3:
Capturing PTIME via Canonization / 3.5:
Definable Linear Orders / 3.5.1:
Canonizations and Interpretations / 3.5.2:
Capturing PTIME up to Bisimulation / 3.5.3:
Is There a Logic for PTIME? / 3.5.4:
Algorithmic Model Theory / 3.6:
Beyond Finite Structures / 3.6.1:
Finitely Presentable Structures / 3.6.2:
Metafinite Structures / 3.6.3:
Metafinite Spectra / 3.6.4:
Descriptive Complexity over the Real Numbers / 3.6.5:
Appendix: Alternating Complexity Classes / 3.7:
Logic and Random Structures / 4:
An Instructive Example / 4.1:
Random Graphs / 4.2:
Extension Statements / 4.3:
Closure / 4.4:
The Almost Sure Theory / 4.5:
The Case p Constant / 4.6:
Countable Models / 4.7:
A Dynamic View / 4.8:
Infinite Spectra via Almost Sure Encoding / 4.9:
The Jump Condition / 4.10:
The Complexity Condition / 4.11:
Nonconvergence via Almost Sure Encoding / 4.12:
No Almost Sure Representation of Evenness / 4.13:
The Ehrenfeucht Game / 4.14:
About the References / 4.15:
Embedded Finite Models and Constraint Databases / 5:
Organization / 5.1:
Relational Databases and Embedded Finite Models / 5.2:
Constraint Databases / 5.3:
Collapse and Genericity: An Overview / 5.4:
Approaches to Proving Expressivity Bounds / 5.4.1:
Active-Generic Collapse / 5.5:
The Ramsey Property / 5.5.1:
Collapse Results / 5.5.2:
Natural-Active Collapse / 5.6:
Collapse: Failure and Success / 5.6.1:
Good Structures vs. Bad Structures: O-minimality / 5.6.2:
Collapse Theorem and Corollaries / 5.6.3:
Collapse Algorithm: the Linear Case / 5.6.4:
Collapse Algorithm: the General Case / 5.6.5:
Collapse Without O-minimality / 5.6.6:
Natural-Generic Collapse / 5.6.7:
Model Theory and Collapse Results / 5.7:
Pseudo-finite Homogeneity / 5.7.1:
Finite Cover Property and Collapse / 5.7.2:
Isolation and Collapse / 5.7.3:
The VC Dimension and Collapse Results / 5.8:
Random Graph and Collapse to MSO / 5.8.1:
Complexity Bounds for Generic Queries / 5.8.2:
Expressiveness of Constraint Query Languages / 5.9:
Reductions to the Finite Case / 5.9.1:
Topological Properties / 5.9.2:
Linear vs. Polynomial Constraints / 5.9.3:
Query Safety / 5.10:
Finite and Infinite Query Safety / 5.10.1:
Safe Translations / 5.10.2:
Finite Query Safety: Characterization / 5.10.3:
Infinite Query Safety: Reduction / 5.10.4:
Deciding Safety / 5.10.5:
Dichotomy Theorem for Embedded Finite Models / 5.10.6:
Database Considerations / 5.11:
Aggregate Operators / 5.11.1:
Higher-Order Features / 5.11.2:
Bibliographic Notes / 5.12:
A Logical Approach to Constraint Satisfaction / 6:
Preliminaries / 6.1:
The Computational Complexity of Constraint Satisfaction / 6.3:
Nonuniform Constraint Satisfaction / 6.4:
Monotone Monadic SNP and Nonuniform Constraint Satisfaction / 6.5:
Datalog and Nonuniform Constraint Satisfaction / 6.6:
Datalog, Games, and Constraint Satisfaction / 6.7:
Games and Consistency / 6.8:
Uniform Constraint Satisfaction and Bounded Treewidth / 6.9:
Local Variations on a Loose Theme: Modal Logic and Decidability / 7:
Modal Systems and Bisimulations / 7.1:
Basic Modal Logic / 7.3:
Notes / 7.3.1:
Some Variations / 7.4:
Neither Locality nor Looseness: Grid Logics / 7.4.1:
Universal Access: K / 7.4.2:
Generalizing Looseness: the Until Operator / 7.4.3:
Modal Complexity / 7.5:
NP and the Polysize Model Property / 7.5.1:
PSPACE and Polynomially Deep Paths / 7.5.2:
EXPTIME and Exponentially Deep Paths / 7.5.3:
NEXPTIME / 7.5.4:
Modal Logic and First-Order Logic / 7.5.5:
Guarded Fragments / 7.6.1:
Decidability and Complexity / 7.6.2:
Index / 7.6.3:
Unifying Themes in Finite Model Theory / 1:
Definability Theory / 1.1:
Classification of Concepts in Terms of Definitional Complexity / 1.1.1:
10.

電子ブック

EB
Dawson, Paul-Louis Hennequin, Bernard Maisonneuve, Joel Spencer
出版情報: SpringerLink Books - AutoHoldings , Springer Berlin Heidelberg, 1993
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼