Mathematical Foundations of Computer Science 1990: Banská Bystrica, Czechoslovakia August 27–31, 1990 Proceedings

Egon Börger (auth.), Branislav Rovan (eds.)3540529535, 9783540529538

This volume contains papers selected for presentation at the 15th Symposium on Mathematical Foundations of Computer Science, MFCS ’90, held at Banská Bystrica, Czechoslovakia, August 27-31, 1990. Previous MFCS proceedings have also been published in the Lecture Notes in Computer Science. This symposium is the 15th in a series of international meetings which have taken place in Czechoslovakia and Poland. The aim of these symposia is to bring together specialists in theoretical fields of computer science from various countries and to stimulate mathematical research in theoretical computer science. These proceedings consist of 10 invited papers and 52 communications selected by the international Program Committee. The papers present the latest results in key areas of computer science by authors from Europe, USA, Japan and China.

---

Table of contents :
A logical operational semantics of full Prolog….Pages 1-14
Syntactic theories….Pages 15-25
On kleene algebras and closed semirings….Pages 26-47
Interactive computations of optimal solutions….Pages 48-60
Restricted branching programs and their computational power….Pages 61-75
Dynamic hashing strategies….Pages 76-87
One-way functions in complexity theory….Pages 88-104
Type inference problems: A survey….Pages 105-120
Counting the number of solutions….Pages 121-134
Implementation of parallel graph reduction by explicit annotation and program transformation….Pages 135-151
Interrogative complexity of ω-languages’ recognition….Pages 152-157
On the power of uniform families of constant depth threshold circuits….Pages 158-164
Separating sets of hyperrectangles….Pages 165-172
On preemptive scheduling of periodic, real-time tasks on one processor….Pages 173-179
Retractions in comparing prolog semantics (extended abstract)….Pages 180-186
Using inductive counting to simulate nondeterministic computation….Pages 187-194
Some properties of zerotesting bounded one-way multicounter machines….Pages 195-201
On fast algorithms for two servers….Pages 202-208
Decomposition of semi commutations….Pages 209-216
Parallel construction of minimal suffix and factor automata….Pages 217-223
Affine automata: A technique to generate complex images….Pages 224-231
The complexity of symmetric functions in parity normal forms….Pages 232-238
Event structures, causal trees, and refinements….Pages 239-245
Query languages which express all PTIME queries for trees and unicyclic graphs….Pages 246-253
Comparisons among classes of Y-tree systolic automata….Pages 254-260
On checking versus evaluation of multiple queries….Pages 261-268
Generalized kolmogorov complexity in relativized separations….Pages 269-276
A first-order logic for partial recursive functions….Pages 277-284
Speed-up theorem without tape compression….Pages 285-291
On possibilities of one-way synchronized and alternating automata….Pages 292-299
Unrestricted resolution versus N-resolution….Pages 300-305
Quality criteria for partial order semantics of place/transition-nets….Pages 306-312
Tree-stack automata….Pages 313-321
Specification & verification of higher order processes….Pages 322-328
The membership problem for context-free chain code picture languages….Pages 329-336
Optimal algorithms for dissemination of information in some interconnection networks….Pages 337-346
A hierarchy of compositional models of I/O-automata (Extended Abstract)….Pages 347-354
Minimal nontrivial space complexity of probabilistic one- way turing machines….Pages 355-361
On the complexity of genuinely polynomial computation….Pages 362-368
Pumping lemmrs for tree languages generated by rewrite systems….Pages 369-377
Vector language: Simple description of hard instances….Pages 378-384
Separating ⊕L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time….Pages 385-391
The use of graphs of elliptical influence in visual hierarchical clustering….Pages 392-398
Characterizing unambiguous augmented pushdown automata by circuits….Pages 399-406
Rational ω-transductions….Pages 407-415
Splitsort—an adaptive sorting algorithm….Pages 416-422
Equational calculi for many-sorted algebras with empty carrier sets….Pages 423-429
Semi-commutation and deterministic petri nets….Pages 430-438
Internal labellings in lambda-calculus….Pages 439-445
A sup-preserving completion of ordered partial algebras….Pages 446-456
ATIME(n) is closed under Counting….Pages 457-463
Investigation of finitary calculi for the temporal logics by means of infinitary calculi….Pages 464-469
Typed horn logic (extended abstract)….Pages 470-477
Results on the glory of the past….Pages 478-484
A stronger version of parikh theorem….Pages 485-491
The parallel complexity of some constructions in combinatorial group theory (abstract)….Pages 492-498
Gentzen type axiomatization for PAL….Pages 499-507
Distance automata having large finite distance or finite ambiguity….Pages 508-515
Bottom-up-heap sort, a new variant of heap sort beating on average quick sort (if n is not very small)….Pages 516-522
Symmetric functions in AC 0 can be computed in constant depth with very small size….Pages 523-529
The k -section of treewidth restricted graphs….Pages 530-537
Computing large polynomial powers very fast in parallel….Pages 538-544