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

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