Mathematical Foundations of Computer Science 1989: Porabka-Kozubnik, Poland August 28 – September 1, 1989 Proceedings

Valery N. Agafonov (auth.), Antoni Kreczmar, Grazyna Mirkowska (eds.)3540514864, 9783540514862

The present volume contains papers selected for presentation at the 14th Symposium on Mathematical Foundations of Computer Science – MFCS ’89 held in Porabka-Kozubnik, Poland, from August 28 to September 1, 1989. Previous MFCs proceedings have also been published in the Lecture Notes in Computer Science. This volume presents investigations and results in theoretical computer science, in particular in the following areas: logics of programs, parallel and distributed computing, deductive databases, automata and formal languages, algorithms and data structures, software specification and validity, complexity and computability theory.

---

Table of contents :
From specification languages to specification knowledge bases: The PTO approach….Pages 1-17
Monadic second-order logic and context-free graph-grammars….Pages 18-34
A thesis for bounded concurrency….Pages 35-48
Space bounded computations : Review and new separation results….Pages 49-66
Concurrent nondeterministic processes: Adequacy of structure and behaviour….Pages 67-87
LEDA a library of efficient data types and algorithms….Pages 88-106
Correctness of concurrent processes….Pages 107-132
Understanding nets….Pages 133-134
On the strength of temporal proofs….Pages 135-144
Proof-theoretic characterisations of logic programming….Pages 145-154
Algebraically closed theories….Pages 155-164
Control flow versus logic: A denotational and a declarative model for Guarded Horn Clauses….Pages 165-176
Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A constructive glimpse….Pages 177-184
Parallel complexity of lexicographically first problems for tree-structured graphs….Pages 185-195
On the power of synchronization in parallel computations….Pages 196-206
Optimal parallel algorithms for the recognition and colouring outerplanar graphs….Pages 207-217
Logical characterizations of nonmonotonic TMSs….Pages 218-224
Proving correctness of constructor implementations….Pages 225-235
Equivalence notions for concurrent systems and refinement of actions….Pages 237-248
System simulation and the sensitivity of self-stabilization….Pages 249-258
Polynomial-time functions generate SAT: On P-splinters….Pages 259-269
Generalized definite tree languages….Pages 270-280
Pinwheel scheduling with two distinct numbers….Pages 281-290
Testing approximate symmetry in the plane is NP-hard….Pages 291-304
Memory and algebra….Pages 305-313
Integer relations among algebraic numbers….Pages 314-320
An iterative metric fully abstract semantics for nondeterministic dataflow (extended abstract)….Pages 321-330
Complexity of decision problems under incomplete information….Pages 331-337
On the nature of TELLUS….Pages 338-349
Switching graphs and their complexity….Pages 350-359
Pomset semantics for true concurrency with synchronization and recursion….Pages 360-369
Oracle branching programs and Logspace versus P….Pages 370-379
Generalizing singly-linked list reorganizing heuristics for doubly-linked lists….Pages 380-389
Area complexity of merging….Pages 390-396
Logically defined subsets of IN k ….Pages 397-407
An extended Herbrand theorem for first-order theories with equality interpreted in partial algebras….Pages 408-417
Characterization of recognizable trace languages by distributed automata….Pages 418-430
Knuth-Morris-Pratt algorithm: An analysis….Pages 431-444
Pushdown automata on infinite trees and omega-Kleene closure of context-free tree sets….Pages 445-457
An imperative type hierarchy with partial products….Pages 458-470
A coloring algorithm for interval graphs….Pages 471-480
Finite constants: Characterizations of a new decidable set of constants….Pages 481-491
Optimal data flow analysis via observational equivalence….Pages 492-502
One more method for proving lower bounds on the formula complexity of boolean functions….Pages 503-510
The Hoare-like verification system for a language with an exception handling mechanism….Pages 511-522
On the lengths of values in a finite transducer….Pages 523-533
On varieties of languages closed under products with counter….Pages 534-544
On the computational efficiency of symmetric neural networks….Pages 545-552
Constructive aspects of the omega-rule : Application to proof systems in computer science and algorithmic logic….Pages 553-565
How to define functionals on free structures in typed λ calculus….Pages 566-576
Concurrency, modularity, and synchronization….Pages 577-598
On comparing probabilistic and deterministic automata complexity of languages….Pages 599-605