14. MFCS 1989: Porabka-Kozubnik, Poland

Invited Lectures

• Valery N. Agafonov:
  From Specification Languages to Specification Knowledge Bases: The PTO Approach. 1-17
  
• Bruno Courcelle:
  Monadic Second-Order Logic and Context-Free Graph-Grammars. 18-34
  
• David Harel:
  A Thesis for Bounded Concurrency. 35-48
  
• Juris Hartmanis, Desh Ranjan:
  Space Bounded Computations: Review And New Separation Results. 49-66
  
• Ludmila Cherkasova, Vadim E. Kotov:
  Concurrent Nondeterministic Processes: Adequacy of Structure and Behaviour. 67-87
  
• Kurt Mehlhorn, Stefan Näher:
  LEDA: A Library of Efficient Data Types and Algorithms. 88-106
  
• Ernst-Rüdiger Olderog:
  Correctness of Concurrent Processes. 107-132
  
• Boris A. Trakhtenbrot:
  Understanding Nets. 133-134
  

Communications

• Hajnal Andréka, István Németi, Ildikó Sain:
  On the Strength of Temporal Proofs. 135-144
  
• James H. Andrews:
  Proof-Theoretic Characterisations of Logic Programs. 145-154
  
• Eric Badouel:
  Algebraic Closed Theories. 155-164
  
• Frank S. de Boer, Joost N. Kok, Catuscia Palamidessi, Jan J. M. M. Rutten:
  Control Flow versus Logic: A Denotational and a Declarative Model for Guarded Horn Clauses. 165-176
  
• Cristian Calude, Dragos Vaida:
  Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse. 177-184
  
• Bogdan S. Chlebus, Krzysztof Diks, Wojciech Rytter, Tomasz Szymacha:
  Parallel Complexity of Lexicographically First Order Problems for Tree-Structured Graphs (Extended Abstract). 185-195
  
• Jürgen Dassow, Juraj Hromkovic, Juhani Karhumäki, Branislav Rovan, Anna Slobodová:
  On the Power of Synchronization in Parallel Computations. 196-206
  
• Krzysztof Diks, Torben Hagerup, Wojciech Rytter:
  Optimal Parallel Algorithms For The Recognition And Colouring Outerplanar Graphs (Extended Abstract). 207-217
  
• Charles Elkan:
  Logical Characterizations of Nonmonotonic TMSs. 218-224
  
• Jordi Farrés-Casals:
  Proving Correctness of Constructor Implementations. 225-235
  
• Rob J. van Glabbeek, Ursula Goltz:
  Equivalence Notions for Concurrent Systems and Refinement of Actions (Extended Abstract). 237-248
  
• Mohamed G. Gouda, Rodney R. Howell, Louis E. Rosier:
  System Simulation and the Sensitivity of Self-Stabilization. 249-258
  
• Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes:
  Polynomial-Time Functions Generate SAT: On P-Splinters. 259-269
  
• Uschi Heuter:
  Generalized Definite Tree Languages. 270-280
  
• Robert Holte, Louis E. Rosier, Igor Tulchinsky, Donald A. Varvel:
  Pinwheel Scheduling With Tow Distinct Numbers. 281-290
  
• Sebastian Iwanowski:
  Testing Approximate Symmetry in the Plane is NP-hard. 291-304
  
• C. Jousselin, J.-P. Moskowitz:
  Memory and Algebra. 305-313
  
• Bettina Just:
  Integer Relations Among Algebraic Numbers. 314-320
  
• Joost N. Kok:
  An Iterative Metric Fully Abstract Semantics for Nondeterministic Dataflow (Extended Abstract). 321-330
  
• Wojciech Kowalczyk:
  Complexity of Decision Problems Under Incomplete Information. 331-337
  
• Vincenzo Manca, Antonino Salibra, Giuseppe Scollo:
  On the Nature of TELLUS (a Typed Equational Logic Look over Uniform Specification). 338-349
• Christoph Meinel:
  Switching Graphs and Their Complexity. 350-359
  
• John-Jules Ch. Meyer, Erik P. de Vink:
  Pomset Semantics for True Concurrency with Synchronization and Recursion (Extended Abstract). 360-369
  
• David A. Mix Barrington, Pierre McKenzie:
  Oracle Branching Programs and Logspace versus P. 370-379
  
• David T. H. Ng, B. John Oommen:
  Generalizing Singly-Linked List Reorganizing Heuristics for Doubly-Linked Lists. 380-389
  
• Vladimir Palko, Ondrej Sýkora, Imrich Vrto:
  Area Complexity of Merging. 390-396
  
• Pierre Péladeau:
  Logically Defined Subsets of N^k. 397-407
  
• Uwe Petermann:
  An Extended Herbrand Theorem for First-Order Theories with Equality Interpreted in Partial Algebras. 408-417
  
• Antoine Petit:
  Characterization of Recognizable Trace Languages by Distributed Automata (Extended Abstract). 418-430
  
• Mireille Régnier:
  Knuth-Morris-Pratt Algorithm: An Analysis. 431-444
  
• Ahmed Saoudi:
  Pushdown Automata on Infinite Trees and Omega-Kleene closure of Context-Free Tree Sets. 445-457
  
• Erik Meineche Schmidt, Michael I. Schwartzbach:
  An Imperative Type Hierarchy with Partial Products. 458-470
  
• Maciej Slusarek:
  A Coloring Algorithm for Interval Graphs. 471-480
  
• Bernhard Steffen, Jens Knoop:
  Finite Constants: Characterizations of a New Decidable Set of Constants. 481-491
  
• Bernhard Steffen:
  Optimal Data Flow Analysis via Observational Equivalence. 492-502
  
• Vladimir Stetsenko:
  One More Method For Proving Lower Bounds on the Formula Complexity of Boolean Functions. 503-510
  
• Danuta Szczepanska:
  The Hoare-Like Verification System for a Language with an Exception Handling Mechanism. 511-522
  
• Andreas Weber:
  On the Length of Values in a Finite Transducer. 523-533
  
• Pascal Weil:
  On Varieties of Languages Closed Under Products with Counter. 534-544
  
• Juraj Wiedermann:
  On the Computational Efficiency of Symmetric Neural Networks. 545-552
  
• Serge Yoccoz:
  Constructive Aspects of the Omega-Rule: Application to Proof Systems in Computer Science and Algorithmic Logic. 553-565
  
• Marek Zaionc:
  How to Define Functionals of Free Structures in Typed Lambda Calculus. 566-576
  

Late Papers

• Antoni W. Mazurkiewicz:
  Concurrency, Modularity, and Synchronization. 577-598
  
• Farid M. Ablayev:
  On Comparing Probabilistic and Deterministic Automata Complexity of Languages. 599-605