11. MFCS 1984: Praha, Czechoslovakia

Invited Lectures

• José L. Balcázar:
  Separating, Strongly Separating, and Collapsing Relativized Complexity Classes. 1-16
  
• Alexander L. Chistov, Dima Grigoriev:
  Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. 17-31
  
• Jozef Gruska:
  Systolic Automata - Power, Characterizations, Nonhomogeneity. 32-49
  
• Christoph M. Hoffmann:
  A Note on Unique Decipherability. 50-63
  
• Günter Hotz:
  Outline of an Algebraic Language Theory. 64-79
  
• Matthias Jantzen:
  Thue Systems and the Church-Rosser Property. 80-95
  
• Giuseppe Longo:
  Limits, Higher Type Computability and Type-Free Languages. 96-114
  
• Antoni W. Mazurkiewicz:
  Traces, Histories, Graphs: Instances of a Process Monoid. 115-133
  
• Dominique Perrin:
  Recent Results on Automata and Infinite Words. 134-148
  
• Franco P. Preparata:
  VLSI Algorithms and Architectures. 149-161
  
• Alexei L. Semenov:
  Decidability of Monadic Theories. 162-175
  

Communications

• J. Albert:
  On the Ehrenfeucht Conjecture on Test Sets and Its Dual Version. 176-184
  
• José L. Balcázar, Ronald V. Book, Uwe Schöning:
  Sparse Oracles, Lowness, and Highness. 185-193
  
• Joffroy Beauquier, Loÿs Thimonier:
  Computability of Probabilistic Parameters for Some Classes of Formal Languages. 194-204
  
• Franz-Josef Brandenburg:
  A Truely Morphic Characterization of Recursively Enumerable Sets. 205-213
  
• Manfred Broy:
  On the Herbrand Kleene Universe for Nondeterministic Computations. 214-222
  
• Hans-Dieter Burkhard:
  An Investigation of Controls for Concurrent Systems by Abstract Control Languages. 223-231
  
• Anton Cerný:
  On Generalized Words of Thue-Morse. 232-239
  
• Marek Chrobak:
  Nondeterminism Is Essential for Two-Way Counter Machines. 240-244
  
• Gerardo Costa, Colin Stirling:
  Weak and Strong Fairness in CCS. 245-254
  
• Robert P. Daley, Carl H. Smith:
  On the Complexity of Inductive Inference (Preliminary Report). 255-264
  
• Herbert Edelsbrunner, Emo Welzl:
  Monotone Edge Sequences in Line Arrangements and Applications (Extended Abstract). 265-272
  
• Patrice Enjalbert, Max Michel:
  Many-Sorted Temporal Logic for Multi-Processes Systems. 273-281
  
• Z. Habasinski:
  Process Logics: Two Decidability Results. 282-290
  
• Armin Hemmerling, Klaus Kriegel:
  On Searching of Special Cases of Mazes and Finite Embedded Graphs. 291-300
  
• Matthew Hennessy, Colin Stirling:
  The Power of the Future Perfect in Program Logics. 301-311
  
• Juraj Hromkovic:
  Hierarchy of Reversal and Zerotesting Bounded Multicounter Machines. 312-321
  
• Juraj Hromkovic:
  On the Power of Alternation in Finite Automata. 322-329
  
• Oscar H. Ibarra, Louis E. Rosier:
  The Equivalence Problem and Correctness Formulas for a Simple Class of Programs (Extended Abstract). 330-338
  
• Jerzy W. Jaromczyk:
  Lower Bounds for Polygon Simplicity Testing and Other Problems. 339-347
  
• Max I. Kanovic:
  A Uniform Independence of Invariant Sentences. 348-354
  
• Juhani Karhumäki, H. C. M. Kleijn:
  On the Equivalence of Compositions of Morphisms and Inverse Morphisms on Regular Languages. 355-363
  
• Wojciech Kowalczyk:
  Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning. 364-369
  
• Ludek Kucera:
  Finding a Maximum Flow in /S, T/-Planar Network in Linear Expected Time. 370-377
  
• Klaus-Jörn Lange:
  Nondeterministic Logspace Reductions. 378-388
  
• Arjen K. Lenstra:
  Factoring Multivariate Polynomials over Algebraic Number Fields. 389-396
  
• Giuseppe Longo, Eugenio Moggi:
  Gödel Numberings, Principal Morphisms, Combinatory Algebras: A Category-theoretic Characterization of Functional Completeness. 397-406
  
• Aldo de Luca, Antonio Restivo:
  Representations lf Integers and Language Theory. 407-415
  
• Jaroslav Morávek, Pavel Pudlák:
  New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. 416-424
  
• A. Sh. Nepomnjashchaja:
  Decidability of the Equivalence Problem for Synchronous Deterministic Pushdown Automata. 425-432
  
• Rocco De Nicola:
  Models and Operators for Nondeterministic Processes. 433-442
  
• B. John Oommen:
  Algorithms for String Editing which Permit Arbitrarily Complex Editing Constraints. 443-451
  
• Pekka Orponen, Uwe Schöning:
  The Structure of Polynomial Complexity Cores (Extended Abstract). 452-458
  
• Thomas Ottmann, Peter Widmayer:
  Solving Visibility Problems by Using Skeleton Structures. 459-470
  
• Axel Poigné:
  Another Look at Parameterization Using Algebras with Subsorts. 471-479
  
• Pavel Pudlák:
  A Lower Bound on Complexity of Branching Programs (Extended Abstract). 480-489
  
• Jan Reiterman, Vera Trnková:
  From Dynamic Algebras to Test Algebras. 490-497
  
• J. M. Robson:
  Combinatorial Games with Exponential Space Complete Decision Problems. 498-506
  
• Wojciech Rytter:
  Fast Recognition of Pushdown Automaton and Context-Free Languages. 507-515
  
• Peter H. Starke:
  Multiprocessor Systems and Their Concurrency. 516-525
  
• Andrzej Tarlecki:
  Free Constructions in Algebraic Institutions. 526-534
  
• Jerzy Tiuryn, Pawel Urzyczyn:
  Remarks on Comparing Expressive Power of Logics of Programs. 535-543
  
• K. Wagner:
  The Complexity of Problems Concerning Graphs with Regularities (Extended Abstract). 544-552
  
• Ingo Wegener:
  On the Complexity of Slice Functions. 553-561
  
• Stanislav Zák:
  An Exponential Lower Bound for One-Time-Only Branching Programs. 562-566
  

Invited Lecture

• Michael Sipser:
  A Topological View of Some Problems in Complexity Theory. 567-572
  

Communications

• Ryszard Danecki:
  Propositional Dynamic Logic with Strong Loop Predicate. 573-581