Computer Science Logic: 12th International Workshop, CSL’98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998. Proceedings

Petr Hájek (auth.), Georg Gottlob, Etienne Grandjean, Katrin Seyr (eds.)3540659226, 9783540659228

This book constitutes the strictly refereed post-workshop proceedings of the 12th International Workshop on Computer Science Logic, CSL ’98, held as the Annual Conference of the European Association on Computer Science Logic in Brno, Czech Republic in August 1998.
The 25 revised full papers presented were carefully reviewed and selected during two rounds of reviewing and revision. Also included are three reviewed invited papers. The papers span the whole scope of computer science logic and mathematical foundations and represent the state of the art in the area.

---

Table of contents :
Front Matter….Pages –
Trakhtenbrot Theorem and Fuzzy Logic….Pages 1-8
Descriptive Complexity, Lower Bounds and Linear Time….Pages 9-28
Testing of Finite State Systems….Pages 29-44
On the Power of Quantifiers in First-Order Algebraic Specification….Pages 45-57
On the Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases….Pages 58-72
Revision Programming = Logic Programming + Integrity Constraints….Pages 73-89
Quantifiers and the System KE: Some Surprising Results….Pages 90-104
Choice Construct and Lindström Logics….Pages 105-125
Monadic NP and Graph Minors….Pages 126-141
Invariant Definability and P / poly ….Pages 142-158
Computational Complexity of Ehrenfeucht-Fraïssé Games on Finite Structures….Pages 159-170
An Upper Bound for Minimal Resolution Refutations….Pages 171-178
On an Optimal Deterministic Algorithm for SAT….Pages 179-187
Characteristic Properties of Majorant-Computability Over the Reals….Pages 188-203
Theorems of Péter and Parsons in Computer Programming….Pages 204-223
Kripke, Belnap, Urquhart and Relevant Decidability & Complexity….Pages 224-240
Existence and Uniqueness of Normal Forms in Pure Type Systems with βη -conversion….Pages 241-259
Normalization of Typable Terms by Superdevelopments….Pages 260-282
Subtyping Functional+Nonempty Record Types….Pages 283-297
Monotone Fixed-Point Types and Strong Normalization….Pages 298-312
Morphisms and Partitions of V -sets….Pages 313-322
Computational Adequacy in an Elementary Topos….Pages 323-342
Logical Relations and Inductive/Coinductive Types….Pages 343-354
On the Complexity of H-Subsumption….Pages 355-371
Complexity Classes and Rewrite Systems with Polynomial Interpretation….Pages 372-384
RPO Constraint Solving Is in NP….Pages 385-398
Quantifier Elimination in Fuzzy Logic….Pages 399-414
Many-Valued First-Order Logics with Probabilistic Semantics….Pages 415-429
Back Matter….Pages –