Mathematical Foundations of Computer Science 1998

Hypergraph traversal revisited: Cost measures and dynamic algorithms.- Defining the Java Virtual Machine as platform for provably correct Java compilation.- Towards a theory of recursive structures.- Modularization and abstraction: The keys to practical formal verification.- On the role of time and space in neural computation.- From algorithms to working programs: On the use of program checking in LEDA.- Computationally-sound checkers.- Reasoning about the past.- Satisfiability — Algorithms and logic.- The joys of bisimulation.- Towards algorithmic explanation of mind evolution and functioning.- Combinatorial hardness proofs for polynomial evaluation.- Minimum propositional proof length is NP-hard to linearly approximate.- Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms.- Locally explicit construction of r?dl's asymptotically good packings.- Proof theory of fuzzy logics: Urquhart's C and related logics.- Nonstochastic languages as projections of 2-tape quasideterministic languages.- Flow logic for Imperative Objects.- Expressive completeness of Temporal Logic of action.- Reducing AC-termination to termination.- On one-pass term rewriting.- On the word, subsumption, and complement problem for recurrent term schematizations.- Encoding the hydra battle as a rewrite system.- Computing ?-free NFA from regular expressions in O(n log2(N)) time.- Iterated length-preserving rational transductions.- The head hierarchy for oblivious finite automata with polynomial advice collapses.- The equivalence problem for deterministic pushdown transducers into abelian groups.- The semi-full closure of Pure Type Systems.- Predicative polymorphic subtyping.- A computational interpretation of the ??-calculus.- Polymorphic subtyping without distributivity.- A (non-elementary) modular decision procedure for LTrL.- Complete abstract interpretations made constructive.- Timed bisimulation and open maps.- Deadlocking states in context-free process algebra.- A superpolynomial lower bound for a circuit computing the clique function with at most (1/6) log log n negation gates.- On counting ac 0 circuits with negative constants.- A second step towards circuit complexity-theoretic analogs of Rice's theorem.- Model checking Real-Time properties of symmetric systems.- Locality of order-invariant first-order formulas.- Probabilistic concurrent constraint programming: Towards a fully abstract model.- Lazy functional algorithms for exact real functionals.- Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets.- Positive turing and truth-table completeness for NEXP are incomparable.- Tally NP sets and easy census functions.- Average-case intractability vs. worst-case intractability.- Shuffle on trajectories: The schützenberger product and related operations.- Gaußian elimination and a characterization of algebraic power series.- D0L-systems and surface automorphisms.- About synchronization languages.- When can an equational simple graph be generated by hyperedge replacement?.- Spatial and temporal refinement of typed graph transformation systems.- Approximating maximum independent sets in uniform hypergraphs.- Representing hyper-graphs by regular languages.- Improved time and space hierarchies of one-tape off-line TMs.- Tarskian set constraints are in NEXPTIME.- ??*-Equational theory of context unification is ? 1 0 -hard.- Speeding-up nondeterministic single-tape off-line computations by one alternation.- Facial circuits of planar graphs and context-free languages.- Optimizing OBDDs is still intractable for monotone functions.- Blockwise variable orderings for shared BDDs.- On the composition problem for OBDDs with multiple variable orders.- Equations in transfinite strings.- Minimal forbidden words and factor automata.- On defect effect of bi-infinite words.- On repetition-free binary words of minimal density.- Embedding of hypercubes into grids.- Tree decompositions of small diameter.- Degree-preserving forests.- A parallelization of Dijkstra's shortest path algorithm.- Comparison between the complexity of a function and the complexity of its graph.- IFS and control languages.- One quantifier will do in existential monadic second-order logic over pictures.- On some recognizable picture-languages.- On the complexity of wavelength converters.- On Boolean vs. Modular arithmetic for circuits and communication protocols.- Communication complexity and lower bounds on multilective computations.- A finite hierarchy of the recursively enumerable real numbers.- One guess one-way cellular arrays.- Topological definitions of chaos applied to cellular automata dynamics.- Characterization of sensitive linear cellular automata with respect to the counting distance.- Additive cellular automata over ?p and the bottom of (CA,?).