10. MFCS 1981: Strbske Pleso, Czechoslovakia

Invited Lectures

• Jon Louis Bentley, Thomas Ottmann:
  The Complexity of Manipulating Hierarchically Defined Sets of Rectangles. 1-15
  
• Andrei P. Ershov:
  The Transformational Machine: Theme and Variations. 16-32
  
• Rusins Freivalds:
  Probabilistic Two-Way Machines. 33-45
  
• Deborah Joseph, Paul Young:
  A Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmetic. 46-60
  
• Bernhard Korte, Rainer Schrader:
  A Survey on Oracle Techniques. 61-77
  
• Burkhard Monien, Ivan Hal Sudborough:
  Time and Space Bounded Complexity Classes and Bandwidth Constrained Problems (A Survey). 78-93
  
• Jaroslav Nesetril:
  Representations of Graphs by Means of Products and Their Complexity. 94-102
  
• Anton Nijholt:
  Parsing Strategies: A Concise Survey (Preliminary Report). 103-120
  
• Jan van Leeuwen, Mark H. Overmars:
  The Art of Dynamizing. 121-131
  
• Leslie G. Valiant, Sven Skyum:
  Fast Parallel Computation of Polynomials Using Few Processes. 132-139
  
• Rüdiger Valk:
  Generalizations of Petri Nets. 140-155
  

Communications

• Helmut Alt, Kurt Mehlhorn, J. Ian Munro:
  Partial Match Retrieval in Implicit Data Structures. 156-161
  
• Hajnal Andréka, István Németi, Ildikó Sain:
  A Characterization of Floyd-Provable Programs. 162-171
  
• Egidio Astesiano, Elena Zucca:
  Semantics of CSP via Translation into CCS. 172-182
  
• Joffroy Beauquier, Jean Berstel:
  More about the ``Geography'' of Context-Free Languages. 183-192
  
• Jan A. Bergstra, Manfred Broy, J. V. Tucker, Martin Wirsing:
  On the Power of Algebraic Specifications. 193-204
  
• Alberto Bertoni, M. Brambilla, Giancarlo Mauri, Nicoletta Sabadini:
  An Application of the Theory of Free Partially Commutative Monoids: Asymptotic Densities of Trace Languages. 205-215
  
• Ronald V. Book, Matthias Jantzen, Burkhard Monien, Colm Ó'Dúnlaing, Celia Wrathall:
  On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report). 216-223
  
• Franz-Josef Brandenburg:
  On the Tranformation of Derivation Graphs to Derivation Trees (Preliminary Report). 224-233
  
• Andreas Brandstädt:
  Pushdown Automata with Restricted Use of Storage Symbols. 234-241
  
• Ludmila Cherkasova, Vadim E. Kotov:
  Structured Nets. 242-251
  
• Robert P. Daley:
  Retraceability, Repleteness and Busy Beaver Sets. 252-261
  
• Werner Damm, Irène Guessarian:
  Combining T and level-N. 262-270
  
• Hans-Dieter Ehrich:
  On Realization and Implementation. 271-280
  
• Dima Grigoriev:
  Multiplicative Complexity of a Bilinear Form over a Commutative Ring. 281-286
  
• Petr Hájek:
  Making Dynamic Logic First-Order. 287-295
  
• J. Horejs:
  Partial Interpretations of Program Schemata. 296-303
  
• Juraj Hromkovic:
  Closure Properties of the Family of Languages Recognized by One-Way Two-Head Deterministic Finite State Automata. 304-313
  
• Ladislav Janiga:
  Another Hierarchy Defined by Multihead Finite Automata. 314-320
  
• Jerzy W. Jaromczyk:
  An Extension of Rabin's Complete Proof Concept. 321-326
  
• Kurt Jensen:
  How to Find Invariants for Coloured Petri Nets. 327-338
  
• H. Jung:
  Relationships between Probabilistic and Deterministic Tape Complexity. 339-346
  
• Alica Kelemenová:
  Grammatical Levels of the Position Restricted Grammars. 347-359
  
• H. C. M. Kleijn, Grzegorz Rozenberg:
  A General Framework for Comparing Sequential and Parallel Rewriting. 360-368
  
• Walter Knödel:
  A Bin Packing Algorithm with Complexity O(n log n) and Performance 1 in the Stochastic Limit. 369-378
  
• Ivan Korec:
  Codings of Nonnegative Integers. 379-388
  
• Václav Koubek, Antonín Ríha:
  The Maximum k-Flow in a Network. 389-397
  
• Hans-Jörg Kreowski, Grzegorz Rozenberg:
  On the Constructive Description of Graph Languages Accepted by Finite Automata. 398-409
  
• Hans-Peter Kriegel, Vijay K. Vaishnavi:
  Weighted Multidimensional B-trees Used as Nearly Optimal Dynamic Dictionaries. 410-417
  
• Ludek Kucera:
  Maximum Flow in Planar Networks. 418-422
  
• Karl J. Lieberherr:
  Probabilistic Combinatorial Optimization. 423-432
  
• Friedhelm Meyer auf der Heide:
  Time-Processor Trade-offs for Universal Parallel Computers. 433-441
  
• Jan Pittl:
  Negative Results on the Size of Deterministic Right Parsers. 442-451
  
• Jaroslav Pokorný:
  Key-Equivalence of Functional Dependency Statements Systems. 452-462
  
• Jan Reiterman, Vera Trnková:
  On Representations of Dynamic Algebras with Reversion. 463-472
  
• Branislav Rovan:
  A Framework for Studying Grammars. 473-482
  
• Vladimir Yu. Sazonov:
  On Existence of Complete Predicate Calculus in Metamathematics without Exponentiation. 483-490
  
• Eljas Soisalon-Soininen, Derick Wood:
  On Structural Similarity of Context-Free Grammars. 491-498
  
• Stefan Sokolowski:
  Axioms for the Term-Wise Correctness of Programs. 499-507
  
• Ludwig Staiger:
  Complexity and Entropy. 508-514
  
• Juraj Steiner:
  Axiomatic Semantics of Indirect Addressing. 515-523
  
• Katsumi Tanaka, Yahiko Kambayashi:
  Testing of Join Dependency Preserving by a Modified Chase Method. 524-533
  
• Horst Wedde:
  A Starvation-Free Solution of the Dining Philosopher's Problem by Use of Interaction Systems. 534-543
  
• Klaus Weihrauch, Gisela Schäfer:
  Admissible Representations of Effective CPO's. 544-553
  
• Juraj Wiedermann:
  Preserving Total Order in Constant Expected Time. 554-562
  
• Akira Kanda:
  Constructive Category Theory (No. 1). 563-577
  

Invited Lecture

• Lothar Budach:
  Two Pebbles Don't Suffice. 578-589