18. MFCS 1993: Gdansk, Poland

Invited Lectures

• Krzysztof R. Apt, Sandro Etalle:
  On the Unification Free Prolog Programs. 1-19
  
• André Arnold, Anne Dicky:
  Equivalences and Preorders of Transition Systems. 20-31
  
• James McKinna, Rod M. Burstall:
  Deliverables: A Categorial Approach to Program Development in Type Theory. 32-67
  
• Volker Diekert:
  Complex and Complex-Like Traces. 68-82
  
• Matthew Hennessy:
  Symbolic Bisimulations (Abstract). 83
  
• Furio Honsell, Marina Lenisa:
  Some Results on the Full Abstraction Problem for Restricted Lambda Calculi. 84-104
  
• Robin Milner:
  Action Calculi, or Syntactic Action Structures. 105-121
  
• Andrew M. Pitts, Ian D. B. Stark:
  Observable Properties of Higher Order Functions that Dynamically Create Local Names, or What's new? 122-141
  
• Vaughan R. Pratt:
  The Second Calculus of Binary Relations. 142-155
  
• Andrzej Ehrenfeucht, Grzegorz Rozenberg:
  An Introduction to Dynamic Labled 2-Structures. 156-173
  
• Alexandru Mateescu, Arto Salomaa:
  Post Correspondence Problem: Primitivity and Interrelations with Complexity Classes. 174-184
  
• Philip Wadler:
  A Taste of Linear Logic. 185-210
  

Contributions

• Laurent Alonso, René Schott:
  On the Tree Inclusion Problem. 211-221
  
• Roberto M. Amadio:
  On the Adequacy of Per Models. 222-231
  
• Vikraman Arvind, Johannes Köbler, Martin Mundhenk:
  Hausdorff Reductions to Sparse Sets and to Sets of High Information Content. 232-241
  
• Egidio Astesiano, Gianna Reggio, Elena Zucca:
  Stores as Homomorphisms and their Transformations. 242-251
  
• J. W. de Bakker, Franck van Breugel, Arie de Bruin:
  Comparative Semantics for Linear Arrays of Communicating Processes: A Study of the UNIX Fork and Pipe Commands. 252-261
  
• Danièle Beauquier, Andreas Podelski:
  Rabin Tree Automata and Finite Monoids. 262-271
  
• Marcin Benke:
  Efficient Type Reconstruction in the Presence of Inheritance. 272-280
  
• Jean Berstel, Patrice Séébold:
  A Characterization of Sturmian Morphisms. 281-290
  
• Hans L. Bodlaender, Klaus Jansen:
  On the Complexity of Scheduling Incompatible Jobs with Unit-Times. 291-300
  
• Marcello M. Bonsangue, Joost N. Kok:
  Isomorphisms between Predicates and State Transformers. 301-310
  
• Liming Cai, Jianer Chen:
  On the Amount of Nondeterminism and the Power of Verifying (Extended Abstract). 311-320
  
• Ilaria Castellani:
  Observing Distribution in Processes. 321-331
  
• Christophe Cérin, Antoine Petit:
  Speedup of Recognizable Trace Languages. 332-341
  
• Maura Cerioli, José Meseguer:
  May I Borrow Your Logic? 342-351
  
• Shiva Chaudhuri, Torben Hagerup, Rajeev Raman:
  Approximate and Exact Deterministic Parallel Selection. 352-361
  
• Jian Chen, John Staples:
  Defining Soft Sortedness by Abstract Interpretation. 362-371
  
• Liang Chen:
  A Model for Real-Time Process Algebras (Extended Abstract). 372-381
  
• José Félix Costa, Amílcar Sernadas, Cristina Sernadas:
  Data Encapsulation and Modularity: Three Views of Inheritance. 382-391
  
• Karel Culik II, Jarkko Kari:
  Image Compression Using Weighted Finite Automata. 392-402
  
• Mariangiola Dezani-Ciancaglini, Ugo de'Liguoro, Adolfo Piperno:
  Filter Models for a Parallel and Non Deterministic Lambda-Calculus. 403-412
  
• Pietro Di Gianantonio:
  Real Number Computability and Domain Theory. 413-422
  
• Zinovy Diskin, Ilya Beylin:
  Lambda Substitution Algebras. 423-432
  
• Bruno Durand:
  Global Properties of 2D Cellular Automata: Some Complexity Results. 433-441
  
• Uffe Engberg, Glynn Winskel:
  Completeness Results for Linear Logic on Petri Nets. 442-452
  
• Alessandro Fantechi, Stefania Gnesi, V. Perticaroli:
  An Expressive Logic for Basic Process Algebra. 453-462
  
• Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum:
  The Complexity of Finding Replicas Using Equality Tests. 463-472
  
• Rob J. van Glabbeek:
  A Complete Axiomatization for Branching Bisimulation Congruence of Finite-State Behaviours. 473-484
  
• Erik de Haas, Peter van Emde Boas:
  Object Oriented Application Flow Graphs and their Semantics. 485-494
  
• Juraj Hromkovic, Jarkko Kari, Lila Kari:
  Some Hierarchies for the Communication Complexity Measures of Cooperating Grammar Systems. 495-505
  
• Louis Ibarra, Dana S. Richards:
  Efficient Parallel Graph Algorithms Based on Open Ear Decomposition. 506-516
  
• Oscar H. Ibarra, Nicholas Q. Trân:
  On the Communication Complexity of Parallel Computation. 517-526
  
• Petr Jancar, Frantisek Mráz, Martin Plátek:
  A Taxonomy of Forgetting Automata. 527-536
  
• Jifeng He:
  Hybrid Parallel Programming and Implementation of Synchronised Communication. 537-546
  
• Astrid Kiehn:
  Proof Systems for Cause Based Equivalences. 547-556
  
• Bruno Martin:
  A Uniform Universal CREW PRAM. 557-565
  
• David Murphy:
  Observing Located Concurrency. 566-576
  
• Philippe Narbel:
  The Boundary of Substitution Systems. 577-587
  
• Jean Neraud:
  New Algorithms for Detecting Morphic Images of a Word. 588-597
  
• Pawel Paczkowski:
  Ignoring Nonessential Interleavings in Assertional Reasoning on Concurrent Programs. 598-607
  
• Michel Parigot, Paul Rozière:
  Constant Time Reductions in Lambda-Caculus. 608-617
  
• Francesco Parisi-Presicce, S. Veglioni:
  Heterogeneous Unified Algebras. 618-628
  
• Don Pigozzi, Antonino Salibra:
  A Representation Theorem for Lambda Abstraction Algebras. 629-639
  
• Regimantas Pliuskevicius:
  On Saturated Calculi for a Linear Temporal Logic. 640-649
  
• Hermann Puhlmann:
  The Snack Powerdomain for Database Semantics. 650-659
  
• Bernhard Reus, Thomas Streicher:
  Verifying Properties of Module Construction in Type Theory. 660-670
  
• Peter Ruzicka, Juraj Waczulík:
  On Time-Space Trade-Offs in Dynamic Graph Pebbling. 671-681
  
• Vladimiro Sassone, Mogens Nielsen, Glynn Winskel:
  Deterministic Behavioural Models for Concurrency. 682-692
  
• David Scholefield, Hussein S. M. Zedan, Jifeng He:
  Real-Time Refinement: Semantics and Application. 693-702
  
• Bernhard Steffen, Carsten Weise:
  Deciding Testing Equivalence for Real-Time Processes with Dense Time. 703-713
  
• Werner Stephan, Andreas Wolpers:
  A Calculus for Higher Order Procedures with Global Variables. 714-723
  
• David Stevens:
  Variable Substitution with Iconic Combinators. 724-733
  
• Ralf Treinen:
  Feature Constraints with First-Class Features. 734-743
  
• Dorothea Wagner, Frank Wagner:
  Between Min Cut and Graph Bisection. 744-750
  
• Egon Wanke:
  Paths and Cycles in Finite Periodic Graphs. 751-760
  
• Jilei Yin, Zhu Hong:
  Learning Decision Lists from Noisy Examples. 761-766
  
• Nicolas Zabel:
  Analytic Tableaux for Finite and Infinite Post Logics. 767-776