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

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