Computer Science Logic: 4th Workshop, CSL '90, Heidelberg, Germany, October 1-5, 1990. Proceedings

ISBN-13: 9783540544876 / Angielski / Miękka / 1991 / 402 str.

Egon Bvrger; Hans Kleine B]ning; Michael M. Richter

Opis

This volume contains 24 papers presented at a workshop held in Heidelberg in October 1990. The papers cover a wide range of topics in computer science logic.

Spis treści

Monadic second order logic, tree automata and forbidden minors.- On the reduction theory for average case complexity.- From prolog algebras towards WAM-A mathematical study of implementation.- A formal operational semantics for languages of type Prolog III.- Efficiency considerations on goal-directed forward chaining for logic programs.- Decision problems for tarski and presburger arithmetics extended with sets.- A fast garbage collection algorithm for WAM — based PROLOG.- A resolution variant deciding some classes of clause sets.- Subclasses of quantified boolean formulas.- Algorithmic proof with diminishing resources part 1.- Cutting plane versus frege proof systems.- RAM with compact memory: a realistic and robust model of computation.- Randomness and turing reducibility restraints.- Towards an efficient tableau proof procedure for multiple-valued logics.- Interactive proof systems: Provers, rounds, and error bounds.- Logics for belief dependence.- A generalization of stability and its application to circumscription of positive introspective knowledge.- The complexity of adaptive error-correcting codes.- Ramsey's theorem in bounded arithmetic.- Nontrivial lower bounds for some NP-problems on directed graphs.- Expansions and models of autoepistemic theories.- On the existence of fixpoints in moore's autoepistemic logic and the non-monotonic logic of McDermott and Doyle.- On the tracking of loops in automated deductions.- The gap-language-technique revisited.

O autorze

Egon Börger ist Professor für Informatik an der Universität Pisa (Italien) und Alexander-von-Humboldt-Forschungspreisträger.