This volume contains the proceedings of the 18thInternational Symposium on Mathematical Foundations ofComputer Science, MFCS '93, held in Gdansk, Poland, August-September 1993. The MFCS symposia, organized annually in Poland and theformer Czechoslovakia since 1972, have a long andwell-established tradition. Over the years they have servedas a meeting ground for specialists from all branches oftheoretical computer science, in particular- algorithms and complexity, automata theory and theory oflanguages, - concurrent, distributed and real-time systems, - the theory of functional, logic and object-orientedprogramming, - lambda calculus and type theory, - semantics and logics of programs, and others. The volume contains 12 invitedlectures and 56contributed papers selected from 133 submissions.
Inhaltsverzeichnis
On the unification free prolog programs. - Equivalences and preorders of transition systems. - Deliverables: a categorical approach to program development in type theory. - Complex and complex-like traces. - Symbolic bisimulations (abstract). - Some results on the full abstraction problem for restricted lambda calculi. - Action calculi, or syntactic action structures. - Observable properties of higher order functions that dynamically create local names, or: What's new? . - The second calculus of binary relations. - An introduction to dynamic labeled 2-structures. - Post Correspondence Problem: Primitivity and interrelations with complexity classes. - A taste of linear logic. - On the tree inclusion problem. - On the adequacy of per models. - Hausdorff reductions to sparse sets and to sets of high information content. - Stores as homomorphisms and their transformations. - Comparative semantics for linear arrays of communicating processes. - Rabin tree automata and finite monoids. - Efficient type reconstruction in the presence of inheritance. - A characterization of Sturmian morphisms. - On the complexity of scheduling incompatible jobs with unit-times. - Isomorphisms between predicate and state transformers. - On the amount of nondeterminism and the power of verifying. - Observing distribution in processes. - Speedup of recognizable trace languages. - May I borrow your logic? . - Approximate and exact deterministic parallel selection. - Defining soft sortedness by abstract interpretation. - A model for real-time process algebras (extended abstract). - Data encapsulation and modularity: Three views of inheritance. - Image compression using Weighted Finite Automata. - Filter models for a parallel and non deterministic ? -calculus. - Real number computability and domain theory. - Lambda substitutionalgebras. - Global properties of 2D cellular automata: some complexity results. - Completeness results for linear logic on Petri nets. - An expressive logic for Basic Process Algebra. - The complexity of finding replicas using equality tests. - A complete axiomatization for branching bisimulation congruence of finite-state behaviours. - Object Oriented application flow graphs and their semantics. - Some hierarchies for the communication complexity measures of cooperating grammar systems. - Efficient parallel graph algorithms based on open ear decomposition. - On the communication complexity of parallel computation. - A taxonomy of forgetting automata. - Hybrid parallel programming and implementation of synchronised communication. - Proof systems for cause based equivalences. - A uniform universal CREW PRAM. - Observing located concurrency. - The boundary of substitution systems. - New algorithms for detecting morphic images of a word. - Ignoring nonessential interleavings in assertional reasoning on concurrent programs. - Constant time reductions in ? -calculus. - Heterogeneous unified algebras. - A representation theorem for lambda abstraction algebras. - On saturated calculi for a linear temporal logic. - The snack powerdomain for database semantics. - Verifying properties of module construction in type theory. - On time-space trade-offs in dynamic graph pebbling. - Deterministic behavioural models for concurrency. - Real-time refinement: Semantics and application. - Deciding testing equivalence for real-time processes with dense time. - A calculus for higher order procedures with global variables. - Variable substitution with iconic combinators. - Feature constraints with first-class features. - Between Min Cut and Graph Bisection. - Paths and cycles in finite periodic graphs. - Learning decisionlists from noisy examples. - Analytic tableaux for finite and infinite Post logics.
