+612 9045 4394
Mathematical Foundations of Computer Science 1994 : 19th International Symposium, Mfcs'94, Kosice, Slovakia, August 22 - 26, 1994. Proceedings - Igor Privara

Mathematical Foundations of Computer Science 1994

19th International Symposium, Mfcs'94, Kosice, Slovakia, August 22 - 26, 1994. Proceedings

By: Igor Privara (Editor), Branislav Rovan (Editor), Peter Ruzicka (Editor)

Paperback Published: 3rd August 1994
ISBN: 9783540583387
Number Of Pages: 633

Share This Book:


or 4 easy payments of $48.19 with Learn more
Ships in 7 to 10 business days

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.

Invited Papersp. 1
Models, Languages, and Compiler Technology for High Performance Computersp. 3
On NC-Real Complexity Classes for Additive Circuits and Their Relations with NCp. 27
E-Complete Sets Do Not Have Optimal Polynomial Time Approximationsp. 38
Solving Polynomial Fixed Point Equationsp. 52
Capturing Complexity Classes with Lindstrom Quantifiersp. 68
Communication Throughput of Interconnection Networksp. 72
Intuitive Counterexamples for Constructive Fallaciesp. 87
Algebraic Methods in the Compositional Analysis of Logic Programsp. 112
Longest Common Subsequencesp. 127
Towards DNA Sequencing Chipsp. 143
On-Line Scheduling of Parallel Jobsp. 159
Stable Bistructure Models of PCFp. 177
Contributionsp. 199
A Competitive Analysis of the List Update Problem with Lookaheadp. 201
May and Must Convergency in Concurrent [lambda]-Calculusp. 211
Genericity and Measure for Exponential Timep. 221
Analysis of Bounded Disorderp. 233
On Languages Accepted with Simultaneous Complexity Bounds and Their Ranking Problemp. 245
A Proof System for Asynchronously Communicating Deterministic Processesp. 256
Embedding Complete Binary Trees into Star Networksp. 266
Inductive Counting below LOGSPACEp. 276
Decision Problems for Edge Grammarsp. 286
"The Big Sweep": On the Power of the Wavefront Approach to Voronoi Diagramsp. 296
Reliable Minimum Finding Comparator Networksp. 306
On Parallel Complexity of Maximum f-Matching and the Degree Sequence Problemp. 316
A Comparison of Two Lower Bound Methods for Communication Complexityp. 326
Efficient Solving of the Word Equations in One Variablep. 336
A [pi]-Calculus with Explicit Substitutions: the Late Semanticsp. 342
Processes and Hyperuniversesp. 352
The Combinatorial Complexity of a Finite Stringp. 364
A Fully Abstract Semantics for Termination in Petri Netsp. 373
Passive and Active Rules in Deductive Databasesp. 383
Combinatorial Results on the Complexity of Teaching and Learningp. 393
Degrees and Reducibilities of Easy Tally Setsp. 403
MSO Definable Text Languagesp. 413
Two Lower Bounds on Distributive Generation of Languagesp. 423
Rational Rewritingp. 433
On the Size of Independent Systems of Equations in Semigroupsp. 443
On a Sublinear Time Parallel Construction of Optimal Binary Search Treesp. 453
Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problemsp. 462
The Relationship Between Gossiping in Vertex Disjoint Paths Mode and Bisection Widthp. 473
A Comparison of Finite and Cellular Automatap. 484
Empty Alternationp. 494
On the Minimization Problem for [omega]-Automatap. 504
On the Complexity of Constructing Optimal Ordered Binary Decision Diagramsp. 515
Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approachp. 525
A Completeness Theorem for Nondeterministic Kleene Algebrasp. 536
How a Rainbow Colouring Function Can Simulate Wait-Free Handshakingp. 516
Critical Pairs in Term Graph Rewritingp. 556
Read-Write Causalityp. 567
Some Trace Monoids Where Both the Star Problem and the Finite Power Property Problem are Decidablep. 577
Complexity of EOL Structural Equivalencep. 587
Shorter Queues for Permutation Routing on Meshesp. 597
Full Abstraction for the Second Order Subset of an ALGOL-like Languagep. 608
The Finest Homophonic Partition and Related Code Conceptsp. 618
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540583387
ISBN-10: 3540583386
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 633
Published: 3rd August 1994
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.3
Weight (kg): 0.89