17. MFCS 1992: Prague, Czechoslovakia

Invited Lectures

• Pankaj K. Agarwal, Jirí Matousek:
  On Range Searching with Semialgebraic Sets. 1-13
  
• Josep Díaz:
  Graph Layout Problems. 14-23
  
• Klaus-Jörn Lange, Peter Rossmanith, Wojciech Rytter:
  Parallel Recognition and Ranking of Context-Free Languages. 24-36
  
• Milena Mihail:
  On the Expansion of Combinatorial Polytopes. 37-49
  
• Pekka Orponen:
  Neural Networks and Complexity Theory. 50-61
  
• J. V. Tucker, Jeffery I. Zucker:
  Theory of Computation over Stream Algebras, and its Applications. 62-80
  
• Uzi Vishkin:
  Methods in Parallel Algorithmics (Abstract). 81
  
• Osamu Watanabe:
  On the Complexity of Small Description and Related Topics. 82-94
  
• Juraj Wiedermann:
  Weak Parallel Machines: a New Class of Physically Feasible Parallel Machine Models. 95-111
  
• Avi Wigderson:
  The Complexity of Graph Connectivity. 112-132
  

Communications

• Holger Bast, Martin Dietzfelbinger, Torben Hagerup:
  A Perfect Parallel Dictionary. 133-141
  
• Bernd Becker, Joachim Hartmann:
  Some Remarks on the Test Complexity of Iterative Logic Arrays. 142-152
  
• Hans-Jörg Burtschick, Albrecht Hoene:
  The Degree Structure of 1-L Reductions. 153-161
  
• Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc:
  Promise Problems and Access to Unambiguous Computation. 162-171
  
• Suresh Chari, Desh Ranjan, Pankaj Rohatgi:
  On the Complexity of Incremental Computation. 172-180
  
• Christian Choffrut, Massimiliano Goldwurm:
  Rational Transductions and Complexity of Counting Problems. 181-190
  
• Hubert Comon, Maribel Fernández:
  Negation Elimination in Equational Formulae. 191-199
  
• José Félix Costa, Amílcar Sernadas, Cristina Sernadas, Hans-Dieter Ehrich:
  Object Interaction. 200-208
  
• Pierre-Louis Curien, Thérèse Hardin, Alejandro Ríos:
  Strong Normalization of Substitutions. 209-217
  
• Robert P. Daley, Bala Kalyanasundaram:
  Probabilistic and Pluralistic Learners with Mind Changes. 218-226
  
• Carsten Damm, Markus Holzer, Klaus-Jörn Lange:
  Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers. 227-235
  
• Denis Derencourt, Juhani Karhumäki, Michel Latteux, Alain Terlutte:
  On Computational Power of Weighted Finite Automata. 236-245
  
• Rainer Feldmann, Peter Mysliwietz:
  The Shuffle Exchange Network has a Hamiltonian Path. 246-254
  
• Paul Gastin, Antoine Petit:
  Poset Properties of Complex Traces. 255-263
  
• Andreas Goerdt:
  A Threshold for Unsatisfiability. 264-274
  
• Robert Gold:
  Dataflow Semantics for Petri Nets. 275-283
  
• Irène Guessarian, Marcos Veloso Peixoto:
  About Boundedness for some DATALOG and DATALOG_neg Programs. 284-297
  
• Torben Hagerup, Ola Petersson:
  Merging and Sorting Strings in Parallel. 298-306
  
• Petr Jancar, Frantisek Mráz, Martin Plátek:
  Characterization of Context-Free Languages by Erasing Automata. 307-314
  
• Lila Kari:
  Insertion and Deletion of Words: Determinism and Reversibility. 315-326
  
• Frantisek Kascak:
  Small Universal One-State Linear Operator Algorithm. 327-335
  
• Cosimo Laneve, Ugo Montanari:
  Mobility in the CC-Paradigm. 336-345
  
• Klaus-Jörn Lange, Peter Rossmanith:
  The Emptiness Problem for Intersections of Regular Languages. 346-354
  
• Hing Leung:
  On Finite Automata with Limited Nondeterminism. 355-363
  
• Igor Litovsky, Yves Métivier, Eric Sopena:
  Definitions and Comparisons of Local Computations on Graphs. 364-373
  
• Bruno Martin:
  Efficient Unidimensional Universal Cellular Automaton. 374-382
  
• Osamu Maruyama, Satoru Miyano:
  Inferring a Tree from Walks. 383-391
  
• Elvira Mayordomo:
  Almost Every Set in Exponential Time is P-Bi-Immune. 392-400
  
• David Murphy, Axel Poigné:
  A Functorial Semantics for Observed Concurrency. 401-411
  
• Edward Ochmanski:
  Modelling Concurrency with Semi-Commutations. 412-420
  
• John Pedersen:
  Decision Problems for Cellular Automata and Their Semigroups. 421-429
  
• G. Michele Pinna, Axel Poigné:
  On the Nature of Events. 430-441
  
• W. Preilowski, Elias Dahlhaus, Gerd Wechsung:
  New Parallel Algorithms for Convex Hull and Triangulation in 3-Dimensional Space. 442-450
  
• Teodor C. Przymusinski:
  Two Simple Characterizations of Well-Founded Semantics. 451-462
  
• S. Ramesh:
  Fully Abstract Semantics for Higher Order Communicating Systems. 463-471
  
• Nicolas Reimen:
  Superposable Trellis Automata. 472-482
  
• Thomas Roos, Gerhard Albers:
  Maintaining Proximity in Higher Dimensional Spaces. 483-493
  
• Andrew Szilard, Sheng Yu, Kaizhong Zhang, Jeffrey Shallit:
  Characterizing Regular Languages with Polynomial Densities. 494-503
  
• Dongming Wang:
  A Strategy for Speeding-up the Computation of Characteristic Sets. 504-510
  
• Celia Wrathall, Volker Diekert, Friedrich Otto:
  One-Rule Trace-Rewriting Systems and Confluence. 511-521