Computer Science Logic -

. .

Résumé :
The 1998Annual Conference of the EuropeanAssociation for Computer Science Logic, CSL?98, was held in Brno, Czech Republic, during August 24-28, 1998. CSL?98wasthe12thinaseriesofworkshopsandthe7thtobeheldasthe Annual Conference of the EACSL. The conference was organized at Masaryk University in Brno by the Faculty of Informatics in cooperation with universities in Aaachen, Caen, Haagen, Linz, Metz, Pisa, Szeged, Vienna, and other institutions. CSL?98 formed one part of a federated conferences event, the other part being MFCS?98, the 23rd Int- national Symposium on the Mathematical Foundations of Computer Science. This federated conferences event consisted of common plenary sessions, invited talks, several parallel technical programme tracks, a dozen satellite workshops organized in parallel, and tutorials. The Federated CSL/MFCS?98 Conferences event included 19 invited talks, four of them joint CSL/MFCS?98 talks (D. Harel, W. Maass, Y. Matiyasevic, and M. Yannakakis), four for CSL (P. Hajek, J. Mitchell, Th. Schwentick, and J. Tiuryn), and eleven for MFCS. Last but not least, two tutorials were organized by CSL on the day preceding the symposium on ?Inference Rules in Fragments of Arithmetic? by Lev Beklemishev and on ?Proofs, Types, and Safe Mobile Code? by Greg Morrisett. A total of 345 persons attended the Federated CSL/MFCS?98 Conference which was a great success. The program committee of CSL?98 selected 27 of 74 papers submitted for the conference.From the 27 papers selected for presentation,25 havebeen accepted, following the standard refereeeing procedure, for publication in the present p- ceedings. Three invited speakers submitted papers, that were likewise refereeed and accepted.

Sommaire:
Invited Papers.- Trakhtenbrot Theorem and Fuzzy Logic.- Descriptive Complexity, Lower Bounds and Linear Time.- Testing of Finite State Systems.- Contributed Papers.- On the Power of Quantifiers in First-Order Algebraic Specification.- On the Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases.- Revision Programming = Logic Programming + Integrity Constraints.- Quantifiers and the System KE: Some Surprising Results.- Choice Construct and Lindstr?m Logics.- Monadic NP and Graph Minors.- Invariant Definability and P/poly.- Computational Complexity of Ehrenfeucht-Fra?ss? Games on Finite Structures.- An Upper Bound for Minimal Resolution Refutations.- On an Optimal Deterministic Algorithm for SAT.- Characteristic Properties of Majorant-Computability Over the Reals.- Theorems of P?ter and Parsons in Computer Programming.- Kripke, Belnap, Urquhart and Relevant Decidability & Complexity.- Existence and Uniqueness of Normal Forms in Pure Type Systems with ??-conversion.- Normalization of Typable Terms by Superdevelopments.- Subtyping Functional+Nonempty Record Types.- Monotone Fixed-Point Types and Strong Normalization.- Morphisms and Partitions of V-sets.- Computational Adequacy in an Elementary Topos.- Logical Relations and Inductive/Coinductive Types.- On the Complexity of H-Subsumption.- Complexity Classes and Rewrite Systems with Polynomial Interpretation.- RPO Constraint Solving Is in NP.- Quantifier Elimination in Fuzzy Logic.- Many-Valued First-Order Logics with Probabilistic Semantics....