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

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