Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS’93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings

Krzysztof R. Apt, Sandro Etalle (auth.), Andrzej M. Borzyszkowski, Stefan Sokołowski (eds.)3540571825, 9783540571827

This volume contains the proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, MFCS ’93, held in Gdansk, Poland, August-September 1993. The MFCS symposia, organized annually in Poland and the former Czechoslovakia since 1972, have a long and well-established tradition. Over the years they have served as a meeting ground for specialists from all branches of theoretical computer science, in particular – algorithms and complexity, automata theory and theory of languages, – concurrent, distributed and real-time systems, – the theory of functional, logic and object-oriented programming, – lambda calculus and type theory, – semantics and logics of programs, and others. The volume contains 12 invitedlectures and 56 contributed papers selected from 133 submissions.

---

Table of contents :
On the unification free prolog programs….Pages 1-19
Equivalences and preorders of transition systems….Pages 20-31
Deliverables: a categorical approach to program development in type theory….Pages 32-67
Complex and complex-like traces….Pages 68-82
Symbolic bisimulations (abstract)….Pages 83-83
Some results on the full abstraction problem for restricted lambda calculi….Pages 84-104
Action calculi, or syntactic action structures….Pages 105-121
Observable properties of higher order functions that dynamically create local names, or: What’s new?….Pages 122-141
The second calculus of binary relations….Pages 142-155
An introduction to dynamic labeled 2-structures….Pages 156-173
Post Correspondence Problem: Primitivity and interrelations with complexity classes….Pages 174-184
A taste of linear logic….Pages 185-210
On the tree inclusion problem….Pages 211-221
On the adequacy of per models….Pages 222-231
Hausdorff reductions to sparse sets and to sets of high information content….Pages 232-241
Stores as homomorphisms and their transformations….Pages 242-251
Comparative semantics for linear arrays of communicating processes….Pages 252-261
Rabin tree automata and finite monoids….Pages 262-271
Efficient type reconstruction in the presence of inheritance….Pages 272-280
A characterization of Sturmian morphisms….Pages 281-290
On the complexity of scheduling incompatible jobs with unit-times….Pages 291-300
Isomorphisms between predicate and state transformers….Pages 301-310
On the amount of nondeterminism and the power of verifying….Pages 311-320
Observing distribution in processes….Pages 321-331
Speedup of recognizable trace languages….Pages 332-341
May I borrow your logic?….Pages 342-351
Approximate and exact deterministic parallel selection….Pages 352-361
Defining soft sortedness by abstract interpretation….Pages 362-371
A model for real-time process algebras (extended abstract)….Pages 372-381
Data encapsulation and modularity: Three views of inheritance….Pages 382-391
Image compression using Weighted Finite Automata….Pages 392-402
Filter models for a parallel and non deterministic λ-calculus….Pages 403-412
Real number computability and domain theory….Pages 413-422
Lambda substitution algebras….Pages 423-432
Global properties of 2D cellular automata: some complexity results….Pages 433-441
Completeness results for linear logic on Petri nets….Pages 442-452
An expressive logic for Basic Process Algebra….Pages 453-462
The complexity of finding replicas using equality tests….Pages 463-472
A complete axiomatization for branching bisimulation congruence of finite-state behaviours….Pages 473-484
Object Oriented application flow graphs and their semantics….Pages 485-494
Some hierarchies for the communication complexity measures of cooperating grammar systems….Pages 495-505
Efficient parallel graph algorithms based on open ear decomposition….Pages 506-516
On the communication complexity of parallel computation….Pages 517-526
A taxonomy of forgetting automata….Pages 527-536
Hybrid parallel programming and implementation of synchronised communication….Pages 537-546
Proof systems for cause based equivalences….Pages 547-556
A uniform universal CREW PRAM….Pages 557-565
Observing located concurrency….Pages 566-576
The boundary of substitution systems….Pages 577-587
New algorithms for detecting morphic images of a word….Pages 588-597
Ignoring nonessential interleavings in assertional reasoning on concurrent programs….Pages 598-607
Constant time reductions in λ-calculus….Pages 608-617
Heterogeneous unified algebras….Pages 618-628
A representation theorem for lambda abstraction algebras….Pages 629-639
On saturated calculi for a linear temporal logic….Pages 640-649
The snack powerdomain for database semantics….Pages 650-659
Verifying properties of module construction in type theory….Pages 660-670
On time-space trade-offs in dynamic graph pebbling….Pages 671-681
Deterministic behavioural models for concurrency….Pages 682-692
Real-time refinement: Semantics and application….Pages 693-702
Deciding testing equivalence for real-time processes with dense time….Pages 703-713
A calculus for higher order procedures with global variables….Pages 714-723
Variable substitution with iconic combinators….Pages 724-733
Feature constraints with first-class features….Pages 734-743
Between Min Cut and Graph Bisection….Pages 744-750
Paths and cycles in finite periodic graphs….Pages 751-760
Learning decision lists from noisy examples….Pages 761-766
Analytic tableaux for finite and infinite Post logics….Pages 767-776