+612 9045 4394
Mathematical Foundations of Computer Science, 1998 : 23rd International Symposium, MFCS `98, Brnmo, Czech Republic August 24-28, 1998 :  23rd International Symposium, MFCS `98, Brnmo, Czech Republic August 24-28, 1998 - Lubos Brim

Mathematical Foundations of Computer Science, 1998 : 23rd International Symposium, MFCS `98, Brnmo, Czech Republic August 24-28, 1998

23rd International Symposium, MFCS `98, Brnmo, Czech Republic August 24-28, 1998

By: Lubos Brim (Editor), Jozef Gruska (Editor), Jiri Zlatuska (Editor)


Published: September 1998
Ships: 15 business days
15 business days
or 4 easy payments of $49.56 with Learn more

This book constitutes the refereed proceedings of the 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS'98, held in Brno, Czech Republic, in August 1998.The 71 revised full papers presented were carefully reviewed and selected from a total of 168 submissions. Also included are 11 full invited surveys by prominent leaders in the area. The papers are organized in topical sections on problem complexity; logic, semantics, and automata; rewriting; automata and transducers; typing; concurrency, semantics, and logic; circuit complexity; programming; structural complexity; formal languages; graphs; Turing complexity and logic; binary decision diagrams, etc..

Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithmsp. 1
Defining the Java Virtual Machine as Platform for Provably Correct Java Compilationp. 17
Towards a Theory of Recursive Structuresp. 36
Modularization and Abstraction: The Keys to Practical Formal Verificationp. 54
On the Role of Time and Space in Neural Computationp. 72
From Algorithms to Working Programs: On the Use of Program Checking in LEDAp. 84
Computationally-Sound Checkersp. 94
Reasoning About the Pastp. 117
Satisfiability Algorithms and Logicp. 129
The Joys of Bisimulationp. 142
Towards Algorithmic Explanation of Mind Evolution and Functioningp. 152
Combinatorial Hardness Proofs for Polynomial Evaluationp. 167
Minimum Propositional Proof Length is NP-Hard to Linearly Approximatep. 176
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atomsp. 185
Locally Explicit Construction of Rodl's Asymptotically Good Packingsp. 194
Proof Theory of Fuzzy Logics: Urquhart's C and Related Logicsp. 203
Nonstochastic Languages as Projections of 2-Tape Quasideterministic Languagesp. 213
Flow Logic for Imperative Objectsp. 220
Expressive Completeness of Temporal Logic of Actionp. 229
Reducing AC-Termination to Terminationp. 239
On One-Pass Term Rewritingp. 248
On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizationsp. 257
Encoding the Hydra Battle as a Rewrite Systemp. 267
Computing [epsilon]-Free NFA from Regular Expressions in O(n log[superscript 2](n)) Timep. 277
Iterated Length-Preserving Rational Transductionsp. 286
The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapsesp. 296
The Equivalence Problem for Deterministic Pushdown Transducers into Abelian Groupsp. 305
The Semi-Full Closure of Pure Type Systemsp. 316
Predicative Polymorphic Subtypingp. 326
A Computational Interpretation of the [lambda][mu]-Calculusp. 336
Polymorphic Subtyping Without Distributivityp. 346
A (Non-elementary) Modular Decision Procedure for LTrLp. 356
Complete Abstract Interpretations Made Constructivep. 366
Timed Bisimulation and Open Mapsp. 378
Deadlocking States in Context-Free Process Algebrap. 388
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most (1/6) log log n Negation Gatesp. 399
On Counting AC[superscript 0] Circuits with Negative Constantsp. 409
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theoremp. 418
Model Checking Real-Time Properties of Symmetric Systemsp. 427
Locality of Order-Invariant First-Order Formulasp. 437
Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Modelp. 446
Lazy Functional Algorithms for Exact Real Functionalsp. 456
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Setsp. 465
Positive Turing and Truth-Table Completeness for NEXP Are Incomparablep. 474
Tally NP Sets and Easy Census Functionsp. 483
Average-Case Intractability vs. Worst-Case Intractabilityp. 493
Shuffle on Trajectories: The Schutzenberger Product and Related Operationsp. 503
Gaussian Elimination and a Characterization of Algebraic Power Seriesp. 512
DOL-Systems and Surface Automorphismsp. 522
About Synchronization Languagesp. 533
When Can an Equational Simple Graph Be Generated by Hyperedge Replacement?p. 543
Spatial and Temporal Refinement of Typed Graph Transformation Systemsp. 553
Approximating Maximum Independent Sets in Uniform Hypergraphsp. 562
Representing Hyper-Graphs by Regular Languagesp. 571
Improved Time and Space Hierarchies of One-Tape Off-Line TMsp. 580
Tarskian Set Constraints Are in NEXPTIMEp. 589
[actual symbol not reproducible]*-Equational Theory of Context Unification is II[actual symbol not reproducible]-Hardp. 597
Speeding-Up Nondeterministic Single-Tape Off-Line Computations by One Alternationp. 607
Facial Circuits of Planar Graphs and Context-Free Languagesp. 616
Optimizing OBDDs Is Still Intractable for Monotone Functionsp. 625
Blockwise Variable Orderings for Shared BDDsp. 636
On the Composition Problem for OBDDs with Multiple Variable Ordersp. 645
Equations in Transfinite Stringsp. 656
Minimal Forbidden Words and Factor Automatap. 665
On Defect Effect of Bi-Infinite Wordsp. 674
On Repetition-Free Binary Words of Minimal Densityp. 683
Embedding of Hypercubes into Gridsp. 693
Tree Decompositions of Small Diameterp. 702
Degree-Preserving Forestsp. 713
A Parallelization of Dijkstra's Shortest Path Algorithmp. 722
Comparison Between the Complexity of a Function and the Complexity of Its Graphp. 732
IFS and Control Languagesp. 740
One Quantifier Will Do in Existential Monadic Second-Order Logic over Picturesp. 751
On Some Recognizable Picture-Languagesp. 760
On the Complexity of Wavelength Convertersp. 771
On Boolean vs. Modular Arithmetic for Circuits and Communication Protocolsp. 780
Communication Complexity and Lower Bounds on Multilective Computationsp. 789
A Finite Hierarchy of the Recursively Enumerable Real Numbersp. 798
One Guess One-Way Cellular Arraysp. 807
Topological Definitions of Chaos Applied to Cellular Automata Dynamicsp. 816
Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distancep. 825
Additive Cellular Automata over Z[subscript p] and the Bottom of (CA,[actual symbol not reproducible])p. 834
Author Indexp. 845
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540648277
ISBN-10: 3540648275
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 854
Published: September 1998
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 4.39
Weight (kg): 1.2