Logical Foundations of Computer Science: Third International Symposium, LFCS ’94 St. Petersburg, Russia, July 11–14, 1994 Proceedings

Farid Ablayev (auth.), Anil Nerode, Yu. V. Matiyasevich (eds.)3540581405, 9783540581406

This volume presents the refereed papers accepted for the international symposium Logical Foundations of Computer Science ’94, Logic at St. Petersburg, held in St. Petersburg, Russia in July 1994. The symposium was the third in a series of joint efforts of logicians from both the former Soviet Union and the West.
The volume reflects that the interaction of logic and computer science is an especially fertile ground for interdisciplinary work providing mutual understanding and benefits. The totally 35 papers are devoted to topics as linear logic, Horn clauses, model-checking, lambda-calculi, modal logic, and problem complexity.

---

Table of contents :
Lower bounds for probabilistic space complexity: Communication-automata approach….Pages 1-7
On model checking infinite-state systems….Pages 8-17
Concurrency problem for Horn fragment of Girard’s Linear Logic….Pages 18-22
Referential data structures and labeled modal logic….Pages 23-33
Yet another correctness criterion for Multiplicative Linear Logic with MIX….Pages 34-46
An approach to effective model-checking of real-time Finite-State Machines in mu-calculus….Pages 47-55
Allegories of circuits….Pages 56-68
The complexity of propositional modal theories and the complexity of consistency of propositional modal theories….Pages 69-80
Multiplicative Linear Logic for resource transformation nets….Pages 81-88
The parameterized complexity of some problems in logic and linguistics….Pages 89-100
Foundations of proof search strategies design in linear logic….Pages 101-113
On extreme points of convex compact turing located set….Pages 114-128
Application of typed lambda calculi in the untyped lambda calculus….Pages 129-139
Classes with pairwise equivalent enumerations….Pages 140-141
Strong normalization in a non-deterministic typed lambda-calculus….Pages 142-152
On expressive completeness of modal logic….Pages 153-163
Comparing models of the non-extensional typed λ-calculus extended abstract….Pages 164-172
Coalgebras and approximation….Pages 173-183
Computational and concurrency models of linear logic….Pages 184-190
The longest perpetual reductions in Orthogonal Expression Reduction Systems….Pages 191-203
The notion of rank and games….Pages 204-217
A predicate logic of well-founded actions….Pages 218-226
Predicative recurrence in finite types….Pages 227-239
Arity vs. alternation in second order logic….Pages 240-252
Hereditarily sequential functionals….Pages 253-264
Propositional linear temporal logic and language homomorphisms….Pages 265-277
An abstract property of confluence applied to the study of the lazy partial lambda calculus….Pages 278-290
On specialization of derivations in axiomatic equality theories….Pages 291-303
Preserving of admissible inference rules in modal logic….Pages 304-315
Pure Type Systems with definitions….Pages 316-328
Craig interpolation property in modal logics with provability interpretation….Pages 329-340
Representing null values in logic programming….Pages 341-352
Comparing cubes….Pages 353-365
A logic of capabilities….Pages 366-378
Weak orthogonality implies confluence: The higher-order case….Pages 379-392