Mathematical Foundations of Computer Science 1994: 19th International Symposium, MFCS'94 Košice, Slovakia, August 22–26, 1994 Proceedings

Models, languages, and compiler technology for high performance computers....Pages 1-26
On NC-real complexity classes for additive circuits and their relations with NC....Pages 27-37
E-complete sets do not have optimal polynomial time approximations....Pages 38-51
Solving polynomial fixed point equations....Pages 52-67
Capturing complexity classes with Lindström quantifiers....Pages 68-71
Communication throughput of interconnection networks....Pages 72-86
Intuitive counterexamples for constructive fallacies....Pages 87-111
Algebraic methods in the compositional analysis of logic programs....Pages 112-126
Longest common subsequences....Pages 127-142
Towards DNA sequencing chips....Pages 143-158
On-line scheduling of parallel jobs....Pages 159-176
Stable bistructure models of PCF....Pages 177-197
A Competitive analysis of the list update problem with lookahead....Pages 199-210
May and must convergency in concurrent λ-calculus....Pages 211-220
Genericity and measure for exponential time....Pages 221-232
Analysis of bounded disorder....Pages 233-244
On languages accepted with simultaneous complexity bounds and their ranking problem....Pages 245-255
A proof system for asynchronously communicating deterministic processes....Pages 256-265
Embedding complete binary trees into star networks....Pages 266-275
Inductive counting below logspace....Pages 276-285
Decision problems for edge grammars....Pages 286-295
“The big sweep”: On the power of the wavefront approach to Voronoi diagrams....Pages 296-305
Reliable minimum finding comparator networks....Pages 306-315
On parallel complexity of maximum f -matching and the degree sequence problem....Pages 316-325
A comparison of two lower bound methods for communication complexity....Pages 326-335
Efficient solving of the word equations in one variable....Pages 336-341
A π-calculus with explicit substitutions: The late semantics....Pages 342-351
Processes and hyperuniverses....Pages 352-363
The combinatorial complexity of a finite string....Pages 364-372
A fully abstract semantics for termination in Petri nets....Pages 373-382
Passive and active rules in deductive databases....Pages 383-392
Combinatorial results on the complexity of teaching and learning....Pages 393-402
Degrees and reducibilities of easy tally sets....Pages 403-412
MSO definable text languages....Pages 413-422
Two lower bounds on distributive generation of languages....Pages 423-432
Rational rewriting....Pages 433-442
On the size of independent systems of equations in semigroups....Pages 443-452
On a sublinear time parallel construction of optimal binary search trees....Pages 453-461
Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems....Pages 462-472
The relationship between gossiping in vertex-disjoint paths mode and bisection width....Pages 473-483
A comparison of finite and cellular automata....Pages 484-493
Empty alternation....Pages 494-503
On the minimization problem for ω-automata....Pages 504-514
On the complexity of constructing optimal ordered binary decision diagrams....Pages 515-524
Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach....Pages 525-535
A completeness theorem for nondeterministic Kleene algebras....Pages 536-545
How a rainbow coloring function can simulate wait-free handshaking....Pages 546-555
Critical pairs in term graph rewriting....Pages 556-566
Read-write causality....Pages 567-576
Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable....Pages 577-586
Complexity of EOL structural equivalence....Pages 587-596
Shorter queues for permutation routing on meshes....Pages 597-607
Full abstraction for the second order subset of an ALGOL-like language....Pages 608-617
The finest homophonic partition and related code concepts....Pages 618-628