Mathematical Foundations of Computer Science 1997 Book

	Invited Papers	1
	Game Semantics for Programming Languages	3
	Communication Complexity	5
	Treewidth: Algorithmic Techniques and Results	19
	When are Two Rewrite Systems More Than None?	37
	Positive Applications of Lattices to Cryptography	44
	A Tile-Based Coordination View of Asynchronous Pi-Calculus	52
	Communication Complexity and Sequential Computation	71
	Lower Bounds for a Proof System with an Exponential Speed-Up over Constant-Depth Frege Systems and over Polynomial Calculus	85
	Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds	91
	Learning to Perform Knowledge-Intensive Inferences	108
	Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity	110
	Contributed Papers	117
	The Expressiveness of Datalog Circuits (DAC)	119
	The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes	129
	A Category of Transition Systems and Its Relations with Orthomodular Posets	139
	Accepting Zeno Words without Time Stand Still	149
	Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams	159
	Specifying Computations Using Hyper Transition Systems	169
	A Shift-Invariant Metric on S[superscript Z] Inducing a Non-trivial Topology	179
	Subtyping Calculus of Construction	189
	Distances between Languages and Reflexivity of Relations	199
	Partial Characterization of Synchronization Languages	209
	Integrating the Specification Techniques of Graph Transformation and Temporal Logic	219
	On the Generation of Trees by Hyperedge Replacement	229
	Regulation by Valences	239
	Simulation as a Correct Transformation of Rewrite Systems	249
	On the Dilation of Interval Routing	259
	Relating Conflict-Free Stable Transition and Event Models	269
	The Giant Component Threshold for Random Regular Graphs with Edge Faults	279
	A Topological Generalization of Propositional Linear Time Temporal Logic	289
	Multi-Head Finite Automata: Data-Independent versus Data-Dependent Computations	299
	Complexity of Finding Short Resolution Proofs	309
	On P versus NP [actual symbol not reproducible] co-NP for Decision Trees and Read-Once Branching Programs	319
	A Characterization of Abstract Families of Algebraic: Power Series	327
	Repetitiveness of DOL-Languages is Decidable in Polynomial Time	337
	Minimal Letter Frequency in n-th Power Free Binary Words	347
	Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States	358
	Optimal Algorithms for Complete Linkage Clustering in d Dimensions	368
	Invertible Linear Cellular Automata over Z[subscript m]: Algorithmic and Dynamical Aspects	378
	Two-Level Contextual Grammars: The Internal Case	388
	Counting Problems over the Reals	398
	On the Influence of the State Encoding on OBDD-Representations of Finite State Machines	408
	Decomposition of TrPTL Formulas	418
	NP-hard Sets Have Many Hard Instances	428
	Deciding Verbose Languages with Linear Advice	438
	Homomorphic Images of Sentential Forms and Terminating Grammars	448
	Simplification Orders for Term Graph Rewriting	458
	Dependency-Based Action Refinement	468
	A Hierarchy for (1,+k)-branching Programs with Respect to k	478
	Routing with Finite Speeds of Memory and Network	488
	Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines	498
	Partial Order Semantics and Read Arcs	508
	Author Index	519