Logical Foundations of Computer Science

1. Front Matter

   PDF

2. Topological semantics for hybrid systems

   • Sergei Artemov, Jennifer Davoren, Anil Nerode

   Pages 1-8

3. Domain-free pure type systems

   • Gilles Barthe, Morten Heine SØrensen

   Pages 9-20

4. Generic queries over quasi-o-minimal domains

   • Oleg V. Belegradek, Alexei P. Stolboushkin, Michael A. Taitslin

   Pages 21-32

5. Towards computing distances between programs via Scott domains

   • Michael A. Bukatin, Joshua S. Scott

   Pages 33-43

6. A safe recursion scheme for exponential time

   • Peter Clote

   Pages 44-52

7. Finite model theory, universal algebra and graph grammars

   • Bruno Courcelle

   Pages 53-55

8. Complexity of query answering in logic databases with complex values

   • Evgeny Dantsin, Andrei Voronkov

   Pages 56-66

9. Recognition of deductive data base stability

   • Michael I. Dekhtyar, Alexander Ja. Dikovsky

   Pages 67-77

10. The concurrency complexity for the Horn fragment of linear logic

    • Sergey M. Dudakov

    Pages 78-87

11. Studying algorithmic problems for free semi-groups and groups

    • Valery Durnev

    Pages 88-101

12. Learning small programs with additional information

    • Rüsiņš Freivalds, Gints Tervits, Rolf Wiehagen, Carl Smith

    Pages 102-112

13. Cut elimination for the second order propositional logic with Hilbert's ε-symbol, extensionality, and full comprehension

    • Michael Gavrilovich

    Pages 113-118

14. Finite bases of admissible rules for the logic S5₂ C

    • Mikhail Golovanov

    Pages 119-129

15. An algebraic correctness criterion for intuitionistic proof-nets

    • Philippe de Groote

    Pages 130-140

16. Towards a theory of recursive structures

    • David Harel

    Pages 141-144

17. On the complexity of prefix formulas in modal logic of subset spaces

    • Bernhard Heinemann

    Pages 145-155

18. The undecidability of second order linear affine logic

    • Alexei P. Kopylov

    Pages 156-166

19. Operational logic of proofs with functionality condition on proof predicate

    • Vladimir N. Krupski

    Pages 167-177

20. On linear ordering of strongly extensional finitely-branching graphs and non-well-founded sets

    • Alexei Lisitsa, Vladimir Sazonov

    Pages 178-188

This book constitutes the refereed proceedings of the 4th International Symposium on Logical Foundations of Computer Science, LFCS'97, held in Yaroslavl, Russia, in July 1997.
The volume presents 42 revised refereed papers carefully selected by the program committee. All current issues of computer science logic are addressed. There is a certain emphasis on reporting the progress achieved by scientists from various parts of the former Soviet Union; but there are also many other strong papers from the international research community.

• Bisimulation
• Cut-elimination theorem
• Endliche Modelltheorie
• Ersetzungssysteme
• Informatik-Logik
• Nichtklassische Logiken
• Variable
• calculus
• complexity
• finite model theory
• logic
• proof
• rewriting systems
• sets
• verification

Policies and ethics