Mathematical Foundations of Computer Science 1988: Proceedings of the 13th Symposium Carlsbad, Czechoslovakia, August 29 – September 2, 1988

Ronald V. Book (auth.), Michal P. Chytil, Václav Koubek, Ladislav Janiga (eds.)354050110X, 9783540501107

This volume contains 11 invited lectures and 42 communications presented at the 13th Conference on Mathematical Foundations of Computer Science, MFCS ’88, held at Carlsbad, Czechoslovakia, August 29 – September 2, 1988. Most of the papers present material from the following four fields: – complexity theory, in particular structural complexity, – concurrency and parellelism, – formal language theory, – semantics. Other areas treated in the proceedings include functional programming, inductive syntactical synthesis, unification algorithms, relational databases and incremental attribute evaluation.

---

Table of contents :
Sparse sets, tally sets, and polynomial reducibilities….Pages 1-13
Functional programming and combinatory algebras….Pages 14-26
On models and algebras for concurrent processes….Pages 27-43
String matching with constraints….Pages 44-58
Structure of complexity classes: Separations, collapses, and completeness….Pages 59-72
Inductive syntactical synthesis of programs from sample computations….Pages 73-84
3-dimensional shortest paths in the presence of polyhedral obstacles….Pages 85-92
Robust oracle machines….Pages 93-106
Recognizable sets with multiplicities in the tropical semiring….Pages 107-120
Reusable specification components….Pages 121-137
Comparing interconnection networks….Pages 138-153
Probabilistic automata complexity of languages depends on language structure and error probability….Pages 154-161
Breadth-first phrase structure grammars and queue automata….Pages 162-170
Implementing abstract data structures in hardware….Pages 171-179
Distribution of Sequential Processes….Pages 180-189
Automata and rational expressions on planar graphs….Pages 190-200
On maximal prefix sets of words….Pages 201-209
Infinite behaviour of deterministic petri nets….Pages 210-219
Testing isomorphism of outerplanar graphs in parallel….Pages 220-230
Efficient simulations between concurrent-read concurrent-write pram models….Pages 231-239
Multiple propositional dynamic logic of parallel programs….Pages 240-248
The steiner tree problem and homogeneous sets….Pages 249-261
Termination of rewriting is undecidable in the one-rvle case….Pages 262-270
Local checking of trace synchronizability….Pages 271-279
Edge separators for planar graphs and their applications….Pages 280-290
A fast parallel algorithm for eigenvalue problem of jacobi matrices….Pages 291-299
Strong and robustly strong polynomial time reducibilities to sparse sets….Pages 300-308
Context-free-like forms for the phrase-structure grammars….Pages 309-317
On the expressive strength of the finitely typed lambda — terms….Pages 318-328
Hoare calculi for higher — type control siructures and their completeness in the sense of cook….Pages 329-338
On representing CCS programs by finite petri nets….Pages 339-350
A taxonomy of fairness and temporal logic problems for petri nets….Pages 351-359
Branching programs as a tool for proving lower bounds on vlsi computations and optimal algorithms for systolic arrays….Pages 360-370
Two lower bounds for circuits over the basis (&, V, -)….Pages 371-380
Positive/Negative conditional rewriting….Pages 381-395
On the computational complexity of codes in graphs….Pages 396-404
Separating the eraser turing machine classes L e , NL e , co-NL e and P e ….Pages 405-413
Compositional proofs by partial specification of processes….Pages 414-423
Introducing negative information in relational databases….Pages 424-432
On positive occur-checks in unification….Pages 433-444
Two applications of fürer’s counter to one-tape nondeterministic TMs….Pages 445-453
Proof system for weakest prespecification and its applications….Pages 454-462
On complexity of counting….Pages 463-471
Design, proof and analysis of new efficient algorithms for incremental attribute evaluation….Pages 472-482
On efficiency of interval routing algorithms….Pages 483-491
An almost linear robinson unification algorithm….Pages 492-500
Random boolean formulas representing any boolean function with asymptotically equal probability….Pages 501-511
On the power of communication in alternating machines….Pages 512-517
Classes of cnf-formulas with backtracking trees of exponential or linear average order for exact-satisfiability….Pages 518-528
Bisections of free monoids and a new unavoidable regularity….Pages 529-537
Failures semantics and deadlocking of modular petri nets….Pages 538-541
A decomposition theorem for finite-valued transducers and an application to the equivalence problem….Pages 542-551
….Pages 552-562