Ebook: Mathematical Foundations of Computer Science 1998: 23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998 Proceedings

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..

---

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..

---

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..
Content:
Front Matter....Pages -
Hypergraph traversal revisited: Cost measures and dynamic algorithms....Pages 1-16
Defining the Java Virtual Machine as platform for provably correct Java compilation....Pages 17-35
Towards a theory of recursive structures....Pages 36-53
Modularization and abstraction: The keys to practical formal verification....Pages 54-71
On the role of time and space in neural computation....Pages 72-83
From algorithms to working programs: On the use of program checking in LEDA....Pages 84-93
Computationally-sound checkers....Pages 94-116
Reasoning about the past....Pages 117-128
Satisfiability — Algorithms and logic....Pages 129-141
The joys of bisimulation....Pages 142-151
Towards algorithmic explanation of mind evolution and functioning....Pages 152-166
Combinatorial hardness proofs for polynomial evaluation....Pages 167-175
Minimum propositional proof length is NP-hard to linearly approximate....Pages 176-184
Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms....Pages 185-193
Locally explicit construction of r?dl's asymptotically good packings....Pages 194-202
Proof theory of fuzzy logics: Urquhart's C and related logics....Pages 203-212
Nonstochastic languages as projections of 2-tape quasideterministic languages....Pages 213-219
Flow logic for Imperative Objects....Pages 220-228
Expressive completeness of Temporal Logic of action....Pages 229-238
Reducing AC-termination to termination....Pages 239-247
On one-pass term rewriting....Pages 248-256
On the word, subsumption, and complement problem for recurrent term schematizations....Pages 257-266
Encoding the hydra battle as a rewrite system....Pages 267-276
Computing ?-free NFA from regular expressions in O(n log2(N)) time....Pages 277-285
Iterated length-preserving rational transductions....Pages 286-295
The head hierarchy for oblivious finite automata with polynomial advice collapses....Pages 296-304
The equivalence problem for deterministic pushdown transducers into abelian groups....Pages 305-315
The semi-full closure of Pure Type Systems....Pages 316-325
Predicative polymorphic subtyping....Pages 326-335
A computational interpretation of the ??-calculus....Pages 336-345
Polymorphic subtyping without distributivity....Pages 346-355
A (non-elementary) modular decision procedure for LTrL....Pages 356-365
Complete abstract interpretations made constructive....Pages 366-377
Timed bisimulation and open maps....Pages 378-387
Deadlocking states in context-free process algebra....Pages 388-398
A superpolynomial lower bound for a circuit computing the clique function with at most (1/6) log log n negation gates....Pages 399-408
A second step towards circuit complexity-theoretic analogs of Rice's theorem....Pages 409-417
Model checking Real-Time properties of symmetric systems....Pages 418-426
Locality of order-invariant first-order formulas....Pages 427-436
Probabilistic concurrent constraint programming: Towards a fully abstract model....Pages 437-445
Lazy functional algorithms for exact real functionals....Pages 446-455
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets....Pages 456-464
Positive turing and truth-table completeness for NEXP are incomparable....Pages 465-473
Tally NP sets and easy census functions....Pages 474-482
Average-case intractability vs. worst-case intractability....Pages 483-492
Shuffle on trajectories: The sch?tzenberger product and related operations....Pages 493-502
Gau?ian elimination and a characterization of algebraic power series....Pages 503-511
D0L-systems and surface automorphisms....Pages 512-521
About synchronization languages....Pages 522-532
When can an equational simple graph be generated by hyperedge replacement?....Pages 533-542
Spatial and temporal refinement of typed graph transformation systems....Pages 543-552
Approximating maximum independent sets in uniform hypergraphs....Pages 553-561
Representing hyper-graphs by regular languages....Pages 562-570
Improved time and space hierarchies of one-tape off-line TMs....Pages 571-579
Tarskian set constraints are in NEXPTIME....Pages 580-588
Speeding-up nondeterministic single-tape off-line computations by one alternation....Pages 589-596
Facial circuits of planar graphs and context-free languages....Pages 597-606
Optimizing OBDDs is still intractable for monotone functions....Pages 607-615
Blockwise variable orderings for shared BDDs....Pages 616-624
On the composition problem for OBDDs with multiple variable orders....Pages 625-635
Equations in transfinite strings....Pages 636-644
Minimal forbidden words and factor automata....Pages 645-655
On defect effect of bi-infinite words....Pages 656-664
On repetition-free binary words of minimal density....Pages 665-673
Embedding of hypercubes into grids....Pages 674-682
Tree decompositions of small diameter....Pages 683-692
Degree-preserving forests....Pages 693-701
A parallelization of Dijkstra's shortest path algorithm....Pages 702-712
Comparison between the complexity of a function and the complexity of its graph....Pages 713-721
IFS and control languages....Pages 722-731
One quantifier will do in existential monadic second-order logic over pictures....Pages 732-739
On some recognizable picture-languages....Pages 740-750
On the complexity of wavelength converters....Pages 751-759
On Boolean vs. Modular arithmetic for circuits and communication protocols....Pages 760-770
Communication complexity and lower bounds on multilective computations....Pages 771-779
A finite hierarchy of the recursively enumerable real numbers....Pages 780-788
One guess one-way cellular arrays....Pages 789-797
Topological definitions of chaos applied to cellular automata dynamics....Pages 798-806
Characterization of sensitive linear cellular automata with respect to the counting distance....Pages 807-815
Additive cellular automata over ?p and the bottom of (CA,?)....Pages 816-824
Back Matter....Pages 825-833
....Pages 834-843