Mathematical Foundations of Computer Science 1997

Game semantics for programming languages.- Communication complexity.- Treewidth: Algorithmic techniques and results.- When are two rewrite systems more than none?.- Positive applications of lattices to cryptography.- A tile-based coordination view of asynchronous ?-calculus.- Communication complexity and sequential computation.- Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus.- Computational limitations of Stochastic Turing machines and Arthur-Merlin games with small space bounds.- Learning to perform knowledge-intensive inferences.- Resolution proofs, exponential bounds, and Kolmogorov complexity.- The expressiveness of Datalog cicuits (DAC).- The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes.- A category of transition systems and its relations with orthomodular posets.- Accepting Zeno words without making time stand still.- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams.- Specifying computations using hyper transition systems.- A shift-invariant metric on S zz inducing a non-trivial topology.- Subtyping calculus of construction (extended abstract).- Distances between languages and reflexivity of relations.- Partial characterization of synchronization languages.- Integrating the specification techniques of graph transformation and temporal logic.- On the generation of trees by hyperedge replacement.- Regulation by valences.- Simulation as a correct transformation of rewrite systems.- On the dilation of interval routing.- Relating conflict-free stable transition and event models (extended abstract).- The giant component threshold for random regular graphs with edge faults.- A topological generalization of propositional linear time temporal logic.- Multi-head finite automata: Data-independent versus data-dependent computations.- Complexity of finding short resolution proofs.- On P versus NP?co-NP for decision trees and read-once branching programs.- A characterization of abstract families of algebraic power series.- Repetitiveness of D0L-languages is decidable in polynomial time.- Minimal letter frequency in n-th power-free binary words.- Real-time generation of primes by a one-dimensional cellular automaton with 11 states.- Optimal algorithms for complete linkage clustering in d dimensions.- Invertible linear cellular automata over Zm: Algorithmic and dynamical aspects.- Two-level contextual grammars: The internal case.- Counting problems over the reals.- On the influence of the state encoding on OBDD-representations of finite state machines.- Decomposition of TrPTL formulas.- NP-hard sets have many hard instances.- Deciding verbose languages with linear advice.- Homomorphic images of sentential forms and terminating grammars (extended abstract).- Simplification orders for term graph rewriting.- Dependency-based action refinement.- A hierarchy for (1, +k)-branching programs with respect to k.- Routing with finite speeds of memory and network.- Queries and algorithms computable by polynomial time existential reflective machines.- Partial order semantics and read arcs.