close
1.

図書

図書
Heinz-Dieter Ebbinghaus, Jörg Flum
出版情報: Berlin : Springer, c2006  xi, 360 p. ; 24 cm
シリーズ名: Springer monographs in mathematics
所蔵情報: loading…
目次情報: 続きを見る
Preface
Preliminaries / 1:
The Ehrenfeucht-Fraisse Method / 2:
Elementary Classes / 2.1:
Ehrenfeucht's Theorem / 2.2:
Examples and Fraisse's Theorem / 2.3:
Hanf's Theorem / 2.4:
Gaifman's Theorem / 2.5:
More on Games / 3:
Second-Order Logic / 3.1:
Infinitary Logic: The Logics L[subscript infinity omega] and L[subscript [omega]1[omega]] / 3.2:
The Logics FO[superscript s] and L[superscript s subscript infinity omega] / 3.3:
Pebble Games / 3.3.1:
The s-Invariant of a Structure / 3.3.2:
Scott Formulas / 3.3.3:
Logics with Counting Quantifiers / 3.4:
Failure of Classical Theorems in the Finite / 3.5:
0-1 Laws / 4:
0-1 Laws for FO and L[superscript omega subscript infinity omega] / 4.1:
Parametric Classes / 4.2:
Unlabeled 0-1 Laws / 4.3:
Appendix / 4.3.1:
Examples and Consequences / 4.4:
Probabilities of Monadic Second Order Properties / 4.5:
Satisfiability in the Finite / 5:
Finite Model Property of FO[superscript 2] / 5.1:
Finite Model Property of [characters not reproducible]-Sentences / 5.2:
Finite Automata and Logic: A Microcosm of Finite Model Theory / 6:
Languages Accepted by Automata / 6.1:
Word Models / 6.2:
Examples and Applications / 6.3:
First-Order Definability / 6.4:
Descriptive Complexity Theory / 7:
Some Extensions of First-Order Logic / 7.1:
Turing Machines and Complexity Classes / 7.2:
Digression: Trahtenbrot's Theorem / 7.2.1:
Structures as Inputs / 7.2.2:
Logical Descriptions of Computations / 7.3:
The Complexity of the Satisfaction Relation / 7.4:
The Main Theorem and Some Consequences / 7.5:
Logics with Fixed-Point Operators / 7.5.1:
Inflationary and Least Fixed-Points / 8.1:
Simultaneous Induction and Transitivity / 8.2:
Partial Fixed-Point Logic / 8.3:
Fixed-Point Logics and L[superscript omega subscript infinity omega] / 8.4:
The Logic FO(PFP[subscript PTIME]) / 8.4.1:
Fixed-Point Logic with Counting / 8.4.2:
Fixed-Point Logics and Second-Order Logic / 8.5:
Digression: Implicit Definability / 8.5.1:
Transitive Closure Logic / 8.6:
FO(DTC) < FO(TC) / 8.6.1:
FO(posTC) and Normal Forms / 8.6.2:
FO(TC) < FO(LFP) / 8.6.3:
Bounded Fixed-Point Logic / 8.7:
Logic Programs / 9:
DATALOG / 9.1:
I-DATALOG and P-DATALOG / 9.2:
A Preservation Theorem / 9.3:
Normal Forms for Fixed-Point Logics / 9.4:
An Application of Negative Fixed-Point Logic / 9.5:
Hierarchies of Fixed-Point Logics / 9.6:
Optimization Problems / 10:
Polynomially Bounded Optimization Problems / 10.1:
Approximable Optimization Problems / 10.2:
Logics for PTIME / 11:
Logics and Invariants / 11.1:
PTIME on Classes of Structures / 11.2:
Quantifiers and Logical Reductions / 12:
Lindstrom Quantifiers / 12.1:
PTIME and Quantifiers / 12.2:
Logical Reductions / 12.3:
Quantifiers and Oracles / 12.4:
References
Index
Preface
Preliminaries / 1:
The Ehrenfeucht-Fraisse Method / 2:
2.

図書

図書
Jörg Flum, Mario Rodríguez-Artalejo (eds.)
出版情報: Berlin : Springer, c1999  xi, 580 p. ; 24 cm
シリーズ名: Lecture notes in computer science ; 1683
所蔵情報: loading…
目次情報: 続きを見る
Invited Papers
Topological Queries in Spatial Databases / V. Vianu
The Consistency Dimension, Compactness, and Query Learning / J.L. Balcázar
Descriptive and Parameterized Complexity / M. Grohe
Logical Specification of Operational Semantics / P.D. Mosses
Constraint-Based Analysis of Broadcast Protocols / G. Delzanno ; J. Esparza ; A. Podelski
Contributed Papers
Descriptive Complexity, I
Descriptive Complexity Theory for Constraint Databases / E. Grädel ; S. Kreutzer
Applicative Control and Computational Complexity / D. Leivant
Verification
Applying Rewriting Techniques to the Verification of Erlang Processes / T. Arts ; J. Giesl
Difference Decision Diagrams / J. Møller ; J. Lichtenberg ; H.R. Andersen ; H. Hulgaard
Analysis of Hybrid Systems: An Ounce of Realism Can Save an Infinity of States / M. Fränzle
Verifying Liveness by Augmented Abstraction / Y. Kesten ; A. Pnueli
Temporal Logic
Signed Interval Logic / T.M. Rasmussen
Quantitative Temporal Logic / Y. Hirshfeld ; A. Rabinovich
An Expressively Complete Temporal Logic without Past Tense Operators for Mazurkiewicz Traces / V. Diekert ; P. Gastin
Lambda Calculus, Linear Logic
Using Fields and Explicit Substitutions to Implement Objects and Functions in a de Bruijn Setting / E. Bonelli
Closed Reductions in the λ-Calculus / M. Fernández ; I. Mackie
Kripke Resource Models of a Dependently-Typed, Bunched λ-Calculus / S. Ishtiaq ; D.J. Pym
A Linear Logical View of Linear Type Isomorphisms / V. Balat ; R. Di Cosmo
Logic Programming, Modal Logic, Description Logic
Choice Logic Programs and Nash Equilibria in Strategic Games / M. De Vos ; D. Vermeir
Resolution Method for Modal Logic with Well-Founded Frames / S. Hagihara ; N. Yonezaki
A NExpTime-Complete Description Logic Strictly Contained in C2 / S. Tobies
A Road-Map on Complexity for Hybrid Logics / C. Areces ; P. Blackburn ; M. Marx
Descriptive Complexity, II
MonadicNLIN and Quantifier-Free Reductions / C. Lautemann ; B. Weinzinger
Directed Reachability: From Ajtai-Fagin to Ehrenfeucht-Fraïssé Games / J. Marcinkowski
Fixpoint Alternation and the Game Quantifier / J.C. Bradfield
Logic and Complexity
Lower Bounds for Space in Resolution / J. Torán
Program Schemes, Arrays, Lindstrom Quantifiers and Zero-One Laws / I.A. Stewart
Open Least Element Principle and Bounded Query Computation / L.D. Blekemishev
Lambda Calculus, Type Theory
A Universal Innocent Game Model for the Bohm Tree Lambda Theory / A.D. Ker ; H. Nickau ; C.-H.L. Ong
Anti-Symmetry of Higher-Order Subtyping / A. Compagnoni ; H. Goguen
Safe Proof Checking in Type Theory with Y / H. Geuvers ; E. Poll ; J. Zwanenburg
Monadic Presentations of Lambda Terms Using Generalized Inductive Types / T. Altenkirch ; B. Reus
Linear Logic, Mu Calculus, Concurrency
A P-Time Completeness Proof for Light Logics / L. Roversi
On Guarding Nested Fixpoints / H. Seidl ; A. Neumann
A Logical Viewpoint on Process-Algebraic Quotients / A. Kučera
A Truly Concurrent Semantics for a Simple Parallel Programming Language / M. Mislove
Specification, Data Refinement
Specification Refinement with System F / J.E. Hannay
Pre-logical Relations / F. Honsell ; D. Sannella
Data-Refinement for Call-By-Value Programming Languages / Y. Kinoshita ; J. Power
Tutorials
Term Rewriting / A. Middeldorp
Interactive Theorem Proving Using Type Theory / D.J. Howe
Author Index
Invited Papers
Topological Queries in Spatial Databases / V. Vianu
The Consistency Dimension, Compactness, and Query Learning / J.L. Balcázar
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼