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

Thomas Cheatham (auth.), Igor Prívara, Branislav Rovan, Peter Ruzička (eds.)3540583386, 9783540583387

This volume constitutes the proceedings of the 19th International Symposium on Mathematical Foundations of Theoretical Computer Science, MFCS ’94, held in Kosice, Slovakia in August 1994.
MFCS ’94 brought together specialists in theoretical fields of computer science from various countries in order to stimulate mathematical research in theoretical computer science. Besides 12 papers based on invited talks by renowned experts, the book contains 42 research contributions selected from a total of 112 submissions. All areas of theoretical computer science are presented, some from a particular mathematical point of view.

---

Table of contents :
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