12. MFCS 1986: Bratislava, Czechoslovakia

Invited Lectures

• Farid M. Ablayev, Rusins Freivalds:
  Why Sometimes Probabilistic Algorithms Can Be More Effective. 1-14
  
• Jean Berstel, Jacques Sakarovitch:
  Recent Results in the Theory of Rational Sets. 15-28
  
• Manfred Broy:
  Partial Interpretations of Higher Order Algebraic Types (Extended Abstract). 29-43
  
• Michal Chytil:
  Kins of Context-Free Languages. 44-58
  
• Hartmut Ehrig, Werner Fey, Francesco Parisi-Presicce, Edward K. Blum:
  Algebraic Theory of Module Specification with Constraints. 59-77
  
• Peter van Emde Boas:
  A Semantical Model for Integration and Modularization of Rules. 78-92
  
• Joachim von zur Gathen:
  Parallel Arithmetic Computations: A Survey. 93-112
  
• Ken Hirose:
  An Approach to Proof Checker. 113-127
  
• John E. Hopcroft:
  The Promise of Electronic Prototyping. 128-139
  
• Oscar H. Ibarra:
  Systolic Arrays: Characterizations and Complexity. 140-153
  
• D. T. Lee:
  Geometric Location Problems and Their Complexity. 154-167
  
• J. Ian Munro:
  Developing Implicit Data Structures. 168-176
  
• Jerzy Tiuryn:
  Higher-Order Arrays and Stacks in Programming. An Application of Complexity Theory to Logics of Programs. 177-198
  

Communications

• Helmut Alt, Torben Hagerup, Kurt Mehlhorn, Franco P. Preparata:
  Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones. 199-208
  
• Egidio Astesiano, Gianna Reggio, Martin Wirsing:
  Relational Specifications and Observational Semantics. 209-217
  
• Bernd Becker:
  Efficient Testing of Optimal Time Adders (Extended Abstract). 218-229
  
• Siegfried Bublitz, Ute Schürfeld, Bernd Voigt, Ingo Wegener:
  Properties of Complexity Measures for PRAMs and WRAMs. 230-238
  
• Virgil Emil Cazanescu:
  Iterative Systems of Equations. 239-246
  
• Alexander L. Chistov:
  Polynomial Complexity of the Newton-Puiseux Algorithm. 247-255
  
• Marek Chrobak, Wojciech Rytter:
  Unique Deciperability for Partially Commutative Alphabet (Extended Abstract). 256-263
  
• Karel Culik II, Juhani Karhumäki:
  The Equivalence of Finite Valued Transducers (on HDTOL Languages) is Decidable. 264-272
  
• Krzysztof Diks:
  A Fast Parallel Algorithm for Six-Colouring of Planar Graphs (Extended Abstract). 273-282
  
• Branislav Durian:
  Quicksort Without a Stack. 283-289
  
• S. Dvorák, Branislav Durian:
  Towards an Efficient Merging. 290-298
  
• Zoltán Ésik, Pál Dömösi, Ferenc Gécseg, J. Virágh:
  Homomorphic Realizations of Automata with Compositions. 299-307
  
• Thomas M. Fischer:
  Refined Bounds on the Complexity of Sorting and Selection in D-Dimensional Space. 308-314
  
• Thomas M. Fischer, K. Wolfrum:
  On the Inherent Combinatorial Complexity of Geometric Problems in D-Dimensional Space. 315-324
  
• Philippe Flajolet:
  The Evolution of Two Stacks in Bounded Space and Random Walks in a Triangle. 325-340
  
• Hans Fleischhack:
  P-Genericity and Strong G-Genericity. 341-349
  
• Christiane Frougny:
  Fibonacci Numeration Systems and Rational Functions. 350-359
  
• B. Gammatie:
  Safe Implementation Equivalence for Asynchronous Nondeterministic Processes. 360-369
  
• Viliam Geffert:
  Grammars with Context Dependency Restricted to Synchronization. 370-378
  
• A. Goralciková, Václav Koubek:
  Some Improved Parallelisms for Graphs. 379-385
  
• Susanne Graf:
  A Complete Inference System for an Algebra or Regular Acceptance Models. 386-395
  
• Thomas Gundermann, Gerd Wechsung:
  Nondeterministic Turing Machines with Modified Acceptance. 396-404
  
• Armin Hemmerling:
  Remark on the Power of Compass (Extended Abstract). 405-413
  
• Friedhelm Hinz:
  Regular Chain Code Picture Languages of Nonlinear Descriptional Complexity. 414-421
  
• Rodney R. Howell, Louis E. Rosier:
  An Analysis of the Nonemptiness Problem for Classes of Reversal-Bounded Multicounter Machines. 422-430
  
• Juraj Hromkovic:
  A New Approach to Defining the Complexity for VLSI. 431-439
  
• Stasys Jukna:
  Lower Bounds on the Complexity of Local Circuits (Preliminary Report). 440-448
  
• Lubor Kollár:
  Optimal Sorting of Seven Element Sets. 449-457
  
• Ivan Korec:
  Undecidable Problems Concerning Generalized Pascal Triangles of Commutative Algebras. 458-466
  
• Václav Koubek, Antonín Ríha:
  Regular Augmentation of Automata and Transducers (Extended Abstract). 467-475
  
• Ivan Kramosil:
  On Some Types of Pseudo-Random Sequences. 476-483
  
• Klaus Kriegel:
  The Space Complexity of the Accessibility Problem for Undirected Graphs of Log N Bounded Genus. 484-492
  
• Antonín Kucera:
  An Alternative, Priority-Free, Solution to Post's Problem. 493-500
  
• Ludek Kucera, Alberto Marchetti-Spaccamela, Marco Protasi, Maurizio Talamo:
  Near Optimal Algorithms for Finding Minimum Steiner Trees on Random Graphs. 501-511
  
• Werner Kuich:
  Matrix Systems and Principal Cones of Algebraic Power Series. 512-517
  
• Klaus-Jörn Lange:
  Two Characterizations of the Logarithmic Alternation Hierarchy. 518-526
  
• Christoph Meinel:
  p-Projection Reducibility and the Complexity Classes L(nonuniform) and NL(nonuniform). 527-535
  
• Dominique Méry:
  A Proof System to Derive Evantually Properties Under Justice Hypothesis. 536-544
  
• M. A. Nait Abdallah:
  AL-Khowarizmi: A Formal System for Higher-Order Logic Programming. 545-553
  
• Fabienne Romian, Jacques Sakarovitch:
  One-Sided Dyck Reduction Over Two Letter Alphabet and Deterministic Context-Free Languages. 554-563
  
• Brigitte Rozoy:
  Model and Complexity of Termination for Distributed Computations. 564-572
  
• Vladislav Rutenburg:
  Complexity of Generalized Graph Coloring. 573-581
  
• Paul G. Spirakis:
  The Parallel Complexity of Deadlock Detection. 582-593
  
• Ludwig Staiger, Werner Nehrlich:
  The Centers of Context-Sensitive Languages. 594-601
  
• Jorma Tarhio, Esko Ukkonen:
  A Greedy Algorithm for Constructing Shortest Common Substrings. 602-610
  
• Heiko Vogler:
  The OI-Hierarchy is Closed under Control. 611-619
  
• Andreas Weber, Helmut Seidl:
  On the Degree of Ambiguity of Finite Automata. 620-629
  

Late Arrivals

• Zbigniew W. Ras, Maria Zemankova:
  Learning in Knowledge Based System, a Possibilistic Approach. 630-638
  
• Oded Goldreich, Silvio Micali, Avi Wigderson:
  Proofs that Release Minimum Knowledge. 639-650