15. MFCS 1990: Banská Bystrica, Czechoslovakia

Invited Lectures

• Egon Börger:
  A Logical Operational Semantics of Full Prolog, Part II: Built-in Predicates for Database Manipulation. 1-14
  
• Jean-Pierre Jouannaud:
  Syntactic Theories. 15-25
  
• Dexter Kozen:
  On Kleene Algebras and Closed Semirings. 26-47
  
• Jan Krajícek, Pavel Pudlák, Jiri Sgall:
  Interactive Computations of Optimal Solutions. 48-60
  
• Christoph Meinel:
  Restricted Branching Programs and Their Computational Power. 61-75
  
• Friedhelm Meyer auf der Heide:
  Dynamic Hashing Strategies. 76-87
  
• Alan L. Selman:
  One-Way Functions in Complexity Theory. 88-104
  
• Jerzy Tiuryn:
  Type Inference Problems: A Survey. 105-120
  
• Jacobo Torán:
  Counting the Number of Solutions. 121-134
  
• Willem G. Vree:
  Implementation of Parallel Graph Reduction by Explicit Annotation and Program Transformation. 135-151
  

Communications

• Maris Alberts:
  Interrogative Complexity of omega-Languages' Recognition. 152-157
  
• Eric Allender, Ulrich Hertrampf:
  On the Power of Uniform Families of Constant Depth Treshold Circuits. 158-164
  
• Fabrizio d'Amore, Paolo Giulio Franciosa:
  Separating Sets of Hyperrectangles. 165-172
  
• Sanjoy K. Baruah, Rodney R. Howell, Louis E. Rosier:
  On Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor. 173-179
  
• Arie de Bruin, Erik P. de Vink:
  Retractions in Comparing Prolog Semantics (Extended Abstract). 180-186
  
• Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes:
  Using Inductive Counting to Simulate Nondeterministic Computation. 187-194
  
• Ivana Cerná:
  Some Properties of Zerotesting Bounded One-Way Multicounter Machines. 195-201
  
• Marek Chrobak, Lawrence L. Larmore:
  On Fast Algorithms for Two Servers. 202-208
  
• Mireille Clerbout, D. Gonzalez:
  Decomposition of Semi Commutations. 209-216
  
• Maxime Crochemore, Wojciech Rytter:
  Parallel Construction of Minimal Suffix and Factor Automata. 217-223
  
• Karel Culik II, Simant Dube:
  Affine Automata: A Technique to Generate Complex Images. 224-231
  
• Carsten Damm:
  The Complexity of Symmetric Functions in Parity Normal Forms. 232-238
  
• Philippe Darondeau, Pierpaolo Degano:
  Event Structures, Causal Trees, and Refinements. 239-245
  
• Pratul Dublish, S. N. Maheshwari:
  Query Languages which Express all PTIME Queries for Trees and Unicyclic Graphs. 246-253
  
• Emanuela Fachini, Andrea Maggiolo-Schettini, Davide Sangiorgi:
  Comparisons Among Classes of Y-Tree Systolic Automata. 254-260
  
• William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene:
  On Checking Versus Evaluation of Multiple Queries. 261-268
  
• Ricard Gavaldà, Leen Torenvliet, Osamu Watanabe, José L. Balcázar:
  Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract). 269-276
  
• Antonio Gavilanes-Franco:
  A First-Order Logic for Partial Recursive Functions. 277-284
  
• Viliam Geffert:
  Speed-Up Theorem Without Tape Compression. 285-291
  
• Dainis Geidmanis:
  On Possibilities of One-Way Synchronized and Alternating Automata. 292-299
  
• Andreas Goerdt:
  Unrestricted Resolution versus N-Resolution. 300-305
  
• Robert Gold, Walter Vogler:
  Quality Criteria for Partial Order Semantics of Place/Transition-Nets. 306-312
  
• Wolfgang Golubski, Wolfram-Manfred Lippe:
  Tree-Stack Automata. 313-321
  
• Michael R. Hansen, Zhou Chaochen:
  Specification & Verification of Higher Order Processes. 322-328
  
• Friedhelm Hinz:
  The Membership Problem for Context-Free Chain Code Picture Languages. 329-336
  
• Juraj Hromkovic, Claus-Dieter Jeschke, Burkhard Monien:
  Optimal Algorithms for Dissemination of Information in Some Interconnection Networks (Extended Abstract). 337-346
  
• Bengt Jonsson:
  A Hierarchy of Compositional Models of I/O-Automata (Extended Abstract). 347-354
  
• Janis Kaneps, Rusins Freivalds:
  Minimal Nontrivial Space Complexity of Probabilistic One-Way Turing Machines. 355-361
  
• Marek Karpinski, Friedhelm Meyer auf der Heide:
  On the Complexity of Genuinely Polynomial Computation. 362-368
  
• Emmanuel Kounalis:
  Pumping Lemmas for Tree Languages Generated by Rewrite Systems. 369-377
  
• Miroslaw Kowaluk, Klaus W. Wagner:
  Vector Language: Simple Description of Hard Instances (Extended Abstract). 378-384
  
• Matthias Krause:
  Separating +L From L, NL, co-NL and AL (=P) for Oblivious Turing Machines of Linear Access Time. 385-391
  
• Mirko Krivánek:
  The Use of Graphs of Elliptical Influence in Visuel Hierarchical Clustering. 392-398
  
• Klaus-Jörn Lange, Peter Rossmanith:
  Characterizing Unambiguous Augmented Pushdown Automata by Circuits. 399-406
  
• Michel Latteux, Erick Timmerman:
  Rational omega-Transductions. 407-415
  
• Christos Levcopoulos, Ola Petersson:
  Splitsort - An Adaptive Sorting Algorithm. 416-422
  
• Vincenzo Manca, Antonino Salibra:
  Equational Calculi for Many-Sorted Algebras with Empty Carrier Sets. 423-429
  
• Edward Ochmanski:
  Semi-Commutation and Deterministic Petri Nets. 430-438
  
• Michel Parigot:
  Internal Labellings in Lambda-Calculus. 439-445
  
• Ana Pasztor:
  A Sup-Preserving Completion of Ordered Partial Algebras. 446-456
  
• Marek Priotrów:
  ATIME(N) is Closed Under Counting. 457-463
  
• Regimantas Pliuskevicius:
  Investigation of Finitary Calculi for the Temporal Logics by Means of Infinitary Calculi. 464-469
  
• Axel Poigné:
  Typed Horn Logic. 470-477
  
• Ildikó Sain:
  Results on the Glory of the Past. 478-484
  
• Pham Huu Uyen:
  A Stronger Version of Parikh Theorem. 485-491
  
• Stephan Waack:
  The Parallel Complexity of Some Constructions in Combinatorial Group Theory (Abstract). 492-498
  
• Igor Walukiewicz:
  Gentzen Type Axiomatizations for PAL. 499-507
  
• Andreas Weber:
  Distance Automata Having Large Finite Distance or Finite Ambiguity. 508-515
  
• Ingo Wegener:
  Bottom-Up-Heap Sort, a New Variant of Heap Sort Beating on Average Quick Sort (if n is not very small). 516-522
  
• Ingo Wegener, Norbert Wurm, Sang-Zin Yi:
  Symmetric Functions in AC⁰A Can Be Computed in Constant Depth With Very Small Size. 523-529
  
• Manfred Wiegers:
  The k-section of Treewidth Restricted Graphs. 530-537
  
• Thomas Zeugmann:
  Computing Large Polynomial Powers Very Fast in Parallel. 538-544