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

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 log 2 ( 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
On counting ac 0 circuits with negative constants....Pages 409-417
A second step towards circuit complexity-theoretic analogs of Rice\'s theorem....Pages 418-426
Model checking Real-Time properties of symmetric systems....Pages 427-436
Locality of order-invariant first-order formulas....Pages 437-445
Probabilistic concurrent constraint programming: Towards a fully abstract model....Pages 446-455
Lazy functional algorithms for exact real functionals....Pages 456-464
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets....Pages 465-473
Positive turing and truth-table completeness for NEXP are incomparable....Pages 474-482
Tally NP sets and easy census functions....Pages 483-492
Average-case intractability vs. worst-case intractability....Pages 493-502
Shuffle on trajectories: The schützenberger product and related operations....Pages 503-511
Gaußian elimination and a characterization of algebraic power series....Pages 512-521
D0L-systems and surface automorphisms....Pages 522-532
About synchronization languages....Pages 533-542
When can an equational simple graph be generated by hyperedge replacement?....Pages 543-552
Spatial and temporal refinement of typed graph transformation systems....Pages 553-561
Approximating maximum independent sets in uniform hypergraphs....Pages 562-570
Representing hyper-graphs by regular languages....Pages 571-579
Improved time and space hierarchies of one-tape off-line TMs....Pages 580-588
Tarskian set constraints are in NEXPTIME....Pages 589-596
Speeding-up nondeterministic single-tape off-line computations by one alternation....Pages 597-606
Facial circuits of planar graphs and context-free languages....Pages 607-615
Optimizing OBDDs is still intractable for monotone functions....Pages 616-624
Blockwise variable orderings for shared BDDs....Pages 625-635
On the composition problem for OBDDs with multiple variable orders....Pages 636-644
Equations in transfinite strings....Pages 645-655
Minimal forbidden words and factor automata....Pages 656-664
On defect effect of bi-infinite words....Pages 665-673
On repetition-free binary words of minimal density....Pages 674-682
Embedding of hypercubes into grids....Pages 683-692
Tree decompositions of small diameter....Pages 693-701
Degree-preserving forests....Pages 702-712
A parallelization of Dijkstra\'s shortest path algorithm....Pages 713-721
Comparison between the complexity of a function and the complexity of its graph....Pages 722-731
IFS and control languages....Pages 732-739
One quantifier will do in existential monadic second-order logic over pictures....Pages 740-750
On some recognizable picture-languages....Pages 751-759
On the complexity of wavelength converters....Pages 760-770
On Boolean vs. Modular arithmetic for circuits and communication protocols....Pages 771-779
Communication complexity and lower bounds on multilective computations....Pages 780-788
A finite hierarchy of the recursively enumerable real numbers....Pages 789-797
One guess one-way cellular arrays....Pages 798-806
Topological definitions of chaos applied to cellular automata dynamics....Pages 807-815
Characterization of sensitive linear cellular automata with respect to the counting distance....Pages 816-824
Additive cellular automata over ℤ p and the bottom of (CA,≤)....Pages 825-833
....Pages 834-843