Ebook: Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium à trbské Pleso, Czechoslovakia August 31 – September 4, 1981

---

Content:
Front Matter....Pages -
The complexity of manipulating hierarchically defined sets of rectangles....Pages 1-15
The transformational machine: Theme and variations....Pages 16-32
Probabilistic two-way machines....Pages 33-45
A survey of some recent results on computational complexity in weak theories of arithmetic....Pages 46-60
A survey on oracle techniques....Pages 61-77
Time and space bounded complexity classes and bandwidth constrained problems....Pages 78-93
Representations of graphs by means of products and their complexity....Pages 94-102
Parsing strategies: A concise survey....Pages 103-120
The art of dynamizing....Pages 121-131
Fast parallel computation of polynomials using few processors....Pages 132-139
Generalizations of Petri nets....Pages 140-155
Partial match retrieval in implicit data structures....Pages 156-161
A characterization of Floyd-provable programs....Pages 162-171
Semantics of CSP via translation into CCS....Pages 172-182
More about the "geography" of context-free languages....Pages 183-192
On the power of algebraic specifications....Pages 193-204
An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages....Pages 205-215
On the complexity of word problems in certain Thue systems....Pages 216-223
On the transformation of derivation graphs to derivation trees....Pages 224-233
Pushdown automata with restricted use of storage symbols....Pages 234-241
Structured nets....Pages 242-251
Retraceability, repleteness and busy beaver sets....Pages 252-261
Combining T and level-N....Pages 262-270
On realization and implementation....Pages 271-280
Multiplicative complexity of a bilinear form over a commutative ring....Pages 281-286
Making dynamic logic first-order....Pages 287-295
Partial interpretations of program schemata....Pages 296-303
Closure properties of the family of languages recognized by one-way two-head deterministic finite state automata....Pages 304-313
Another hierarchy defined by multihead finite automata....Pages 314-320
An extension of Rabin's complete proof concept....Pages 321-326
How to find invariants for coloured Petri nets....Pages 327-338
Relationships between probabilistic and deterministic tape complexity....Pages 339-346
Grammatical levels of the position restricted grammars....Pages 347-359
A general framework for comparing sequential and parallel rewriting....Pages 360-368
A bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit....Pages 369-378
Codings of nonnegative integers....Pages 379-388
The maximum k-flow in a network....Pages 389-397
On the constructive description of graph languages accepted by finite automata....Pages 398-409
Weighted multidimensional B-trees used as nearly optimal dynamic dictionaries....Pages 410-417
Maximum flow in planar networks....Pages 418-422
Probabilistic combinatorial optimization....Pages 423-432
Time-processor trade-offs for universal parallel computers....Pages 433-441
Negative results on the size of deterministic right parsers....Pages 442-451
Key-equivalence of functional dependency statements systems....Pages 452-462
On representation of dynamic algebras with reversion....Pages 463-472
A framework for studying grammars....Pages 473-482
On existence of complete predicate calculus in metamathematics without exponentiation....Pages 483-490
On structural similarity of context-free grammars....Pages 491-498
Axioms for the term-wise correctness of programs....Pages 499-507
Complexity and entropy....Pages 508-514
Axiomatic semantics of indirect addressing....Pages 515-523
Testing of join dependency preserving by a modified chase method....Pages 524-533
A starvation-free solution of the dining philosophers' problem by use of interaction systems....Pages 534-543
Admissible representations of effective cpo's....Pages 544-553
Preserving total order in constant expected time....Pages 554-562
Constructive category theory (No. 1)....Pages 563-577
Two pebbles don't suffice....Pages 578-589

---

Content:
Front Matter....Pages -
The complexity of manipulating hierarchically defined sets of rectangles....Pages 1-15
The transformational machine: Theme and variations....Pages 16-32
Probabilistic two-way machines....Pages 33-45
A survey of some recent results on computational complexity in weak theories of arithmetic....Pages 46-60
A survey on oracle techniques....Pages 61-77
Time and space bounded complexity classes and bandwidth constrained problems....Pages 78-93
Representations of graphs by means of products and their complexity....Pages 94-102
Parsing strategies: A concise survey....Pages 103-120
The art of dynamizing....Pages 121-131
Fast parallel computation of polynomials using few processors....Pages 132-139
Generalizations of Petri nets....Pages 140-155
Partial match retrieval in implicit data structures....Pages 156-161
A characterization of Floyd-provable programs....Pages 162-171
Semantics of CSP via translation into CCS....Pages 172-182
More about the "geography" of context-free languages....Pages 183-192
On the power of algebraic specifications....Pages 193-204
An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages....Pages 205-215
On the complexity of word problems in certain Thue systems....Pages 216-223
On the transformation of derivation graphs to derivation trees....Pages 224-233
Pushdown automata with restricted use of storage symbols....Pages 234-241
Structured nets....Pages 242-251
Retraceability, repleteness and busy beaver sets....Pages 252-261
Combining T and level-N....Pages 262-270
On realization and implementation....Pages 271-280
Multiplicative complexity of a bilinear form over a commutative ring....Pages 281-286
Making dynamic logic first-order....Pages 287-295
Partial interpretations of program schemata....Pages 296-303
Closure properties of the family of languages recognized by one-way two-head deterministic finite state automata....Pages 304-313
Another hierarchy defined by multihead finite automata....Pages 314-320
An extension of Rabin's complete proof concept....Pages 321-326
How to find invariants for coloured Petri nets....Pages 327-338
Relationships between probabilistic and deterministic tape complexity....Pages 339-346
Grammatical levels of the position restricted grammars....Pages 347-359
A general framework for comparing sequential and parallel rewriting....Pages 360-368
A bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit....Pages 369-378
Codings of nonnegative integers....Pages 379-388
The maximum k-flow in a network....Pages 389-397
On the constructive description of graph languages accepted by finite automata....Pages 398-409
Weighted multidimensional B-trees used as nearly optimal dynamic dictionaries....Pages 410-417
Maximum flow in planar networks....Pages 418-422
Probabilistic combinatorial optimization....Pages 423-432
Time-processor trade-offs for universal parallel computers....Pages 433-441
Negative results on the size of deterministic right parsers....Pages 442-451
Key-equivalence of functional dependency statements systems....Pages 452-462
On representation of dynamic algebras with reversion....Pages 463-472
A framework for studying grammars....Pages 473-482
On existence of complete predicate calculus in metamathematics without exponentiation....Pages 483-490
On structural similarity of context-free grammars....Pages 491-498
Axioms for the term-wise correctness of programs....Pages 499-507
Complexity and entropy....Pages 508-514
Axiomatic semantics of indirect addressing....Pages 515-523
Testing of join dependency preserving by a modified chase method....Pages 524-533
A starvation-free solution of the dining philosophers' problem by use of interaction systems....Pages 534-543
Admissible representations of effective cpo's....Pages 544-553
Preserving total order in constant expected time....Pages 554-562
Constructive category theory (No. 1)....Pages 563-577
Two pebbles don't suffice....Pages 578-589
....