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

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. 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 This volume constitutes the proceedings of the 19th International Symposium on Mathematical Foundations in Theoretical Computer Science, held in Slovakia in August 1994. All areas of theoretical computer science are represented, with a particular emphasis on mathematical applications.