13. MFCS 1988: Carlsbad, Czechoslovakia

Invited Lectures

• Ronald V. Book:
  Sparse Sets, Tally Sets, and Polynomial Reducibilities. 1-13
  
• Corrado Böhm:
  Functional Programming and Combinatory Algebras. 14-26
  
• Ludmila Cherkasova:
  On Models and Algebras for Concurrent Processes. 27-43
  
• Maxime Crochemore:
  String Matching with Constraints. 44-58
  
• Lane A. Hemachandra:
  Structure of Complexity Classes: Separations, Collapses, and Completeness. 59-72
  
• Efim B. Kinber:
  Inductive Syntactical Synthesis of Programs from Sample Computations. 73-84
  
• John H. Reif, James A. Storer:
  3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles. 85-92
  
• Uwe Schöning:
  Robust Orale Machines. 93-106
  
• Imre Simon:
  Recognizable Sets with Multiplicities in the Tropical Semiring. 107-120
  
• Martin Wirsing, Rolf Hennicker, Ruth Breu:
  Reusable Specification Components. 121-137
  
• Burkhard Monien, Ivan Hal Sudborough:
  Comparing Interconnection Networks. 138-153
  

Communications

• Farid M. Ablayev:
  Probabilistic Automata Complexity of Languages Depends on Language Structure and Error Probability. 154-161
  
• E. Allevi, Alessandra Cherubini, Stefano Crespi-Reghizzi:
  Breadth-First Phrase Structure Grammars and Queue Automata. 162-170
  
• Frank Bauernöppel, Hermann Jung:
  Implementing Abstract Data Structures in Hardware. 171-179
  
• Joffroy Beauquier, Antoine Petit:
  Distribution of Sequential Processes. 180-189
  
• Francis Bossut, Max Dauchet, Bruno Warin:
  Automata and Rational Expressions on Planar Graphs. 190-200
  
• Véronique Bruyère:
  On Maximal Prefix Sets of Words. 201-209
  
• Heino Carstensen:
  Infinite Behaviour if Deterministic Petri Nets. 210-219
  
• Bogdan S. Chlebus, Krzysztof Diks, Tomasz Radzik:
  Testing Isomorphism of Outerplanar Graphs in Parallel. 220-230
  
• Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik:
  Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models. 231-239
  
• Ryszard Danecki:
  Multiple Propositional Dynamic Logic of Parallel Programs (Extended Abstract). 240-248
  
• Alessandro D'Atri, Marina Moscarini, Antonio Sassano:
  The Steiner Tree Problem and Homogeneous Sets. 249-261
  
• Max Dauchet:
  Termination of Rewriting is Undecidable in the One-Rule Case. 262-270
  
• Volker Diekert, Walter Vogler:
  Local Checking of Trace Synchroniziability. 271-279
  
• Krzysztof Diks, Hristo Djidjev, Ondrej Sýkora, Imrich Vrto:
  Edge Separators for Planar Graphs and Their Applications. 280-290
  
• Michael A. Frumkin:
  A Fast Parallel Algorithm for Eigenvalue Problem of Jacobi Matrices. 291-299
  
• Ricard Gavaldà, José L. Balcázar:
  Strong and Robustly Strong Polynomial Time Reducibilities to Sparse Sets. 300-308
  
• Viliam Geffert:
  Context-Free-Like Forms for the Phrase-Structure Grammars. 309-317
  
• Andreas Goerdt:
  On the Expressive Strength of the Finitely Typed Lambda-Terms. 318-328
  
• Andreas Goerdt:
  Hoare Calculi for Higher-Type Control Structures and Their Completeness in the Sense of Cook. 329-338
  
• Ursula Goltz:
  On Representing CCS Programs by Finite Petri Nets. 339-350
  
• Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen:
  A Taxonomy of Fairness and Temporal Logic Problems for Petri Nets. 351-359
  
• Juraj Hromkovic, Juraj Procházka:
  Branching Programs as a Tool for Proving Lower Bounds on VLSI Computations and Optimal Algorithms for Systolic Arrays. 360-370
  
• Stasys Jukna:
  Two Lower Bounds for Circuits over the Basis (&, V, -). 371-380
  
• Stéphane Kaplan:
  Positive/Negative Conditional Rewriting. 381-395
  
• Jan Kratochvíl, Mirko Krivánek:
  On the Computational Complexity of Codes in Graphs. 396-404
  
• Matthias Krause, Christoph Meinel, Stephan Waack:
  Separating the Eraser Turing Machine Classes L_e, NL_e, co-NL_e and P_e. 405-413
  
• Kim Guldstrand Larsen, Bent Thomsen:
  Compositional Proofs by Partial Specification of Processes. 414-423
  
• Dominique Laurent, Nicolas Spyratos:
  Introducing Negative Information in Relational Databases. 424-432
  
• Philippe le Chenadec:
  On Positive Occur-Checks in Unification. 433-444
  
• Krzysztof Lorys, Maciej Liskiewicz:
  Two Applications of Fürer's Counter to One-Tape Nondeterministic TMs. 445-453
  
• Satoru Miyano:
  Delta₂^p-Complete Lexicographically First Maximal Subgraph Problems. 454-462
• Ewa Orlowska:
  Proof System for Weakest Prespecification and its Applications. 463-471
  
• Marek Piotrów:
  On Complexity of Counting. 472-482
  
• Qi Lu, Jiahua Qian:
  Design, Proof and Analysis of New Efficient Algorithms for Incremental Attribute Evaluation. 483-491
  
• Peter Ruzicka:
  On Efficiency of Interval Routing Algorithms. 492-500
  
• Peter Ruzicka, Igor Prívara:
  An Almost Linear Robinson Unification ALgorithm. 501-511
  
• Petr Savický:
  Random Boolean Formulas Representing any Boolean Function with Asymptotically Equal Probability (Extended Abstract). 512-517
  
• Anna Slobodová:
  On the Power of Communication in Alternating Machines. 518-528
  
• Ewald Speckenmeyer:
  Classes of CNF-Formulas with Backtracking Trees of Exponential or Linear Average Order for Exact-Satisfiability. 529-538
  
• Stefano Varricchio:
  Bisections of Free Monoids and a New Unavoidable Regularity. 539-541
  
• Walter Vogler:
  Failures Semantics and Deadlocking of Modular Petri Nets. 542-551
  
• Andreas Weber:
  A Decomposition Theorem for Finite-Valued Tranducers and an Application to the Equivalence Problem. 552-562