Mathematical Foundations of Computer Science 1995 Book

	Scheduling Parallel Communication: The h-Relation Problem	1
	Decomposable Structures, Boolean Function Representations, and Optimization	21
	The Complexity of Interval Routing on Random Graphs	37
	Bridging Across the log(n) Space Frontier	50
	Second Order Logic and the Weak Exponential Hierarchies	66
	On the Computing Paradigm and Computational Complexity	82
	Ranked Structures in Nonmonotonic Reasoning and Belief Revision	93
	Symbolic Dynamics and Finite Automata	94
	Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic	105
	Physics and the New Computation	106
	Measure on P: Robustness of the Notion	129
	Comparing Counting Classes for Logspace, One-Way Logspace, and First-Order	139
	Automata That Take Advice	149
	Nonuniform Lower Bounds for Exponential Time Classes	159
	On a Quantitative Notion of Uniformity	169
	Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities	179
	On the Complexity of Finite Memory Policies for Markov Decision Processes	191
	Derandomization for Sparse Approximations and Independent Sets	201
	Asymptotically Efficient In-Place Merging	211
	The Complexity of the Falsifiability Problem for Pure Implicational Formulas	221
	Strong Lower Bounds on the Approximability of Some NPO PB-complete Maximization Problems	227
	Some Typical Properties of Large AND/OR Boolean Formulas	237
	The Hedge: An Efficient Storage Device for Turing Machines with One Head	247
	Graph Inference from a Walk for Trees of Bounded Degree 3 is NP-complete	257
	Honeycomb Networks	267
	Witness-Isomorphic Reductions and the Local Search Problem	277
	Multiple Product Modulo Arbitrary Numbers	288
	Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems	299
	Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages	309
	A Superpolynomial Lower Bound for (1, +k(n))-Branching Programs	319
	Deterministic Parsing for Augmented Context-Free Grammars	326
	A Periodicity Theorem on Words and Applications	337
	A New Approach to Analyse Coupled-Context-Free Languages	349
	Computational Complexity of Simultaneous Elementary Matching Problems	359
	Graph Reducibility of Term Rewriting Systems	371
	Positive Recursive Type Assignment	382
	String Recognition on Anonymous Rings	392
	The Firing Squad Synchronization Problem on Cayley Graphs	402
	Solving Cheap Graph Problems on Meshes	412
	An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes	423
	On Congruences and Partial Orders	434
	Performance Preorder: Ordering Processes with Respect to Speed	444
	Towards a Semantic Theory of CML	454
	Modular Constructions of Distributing Automata	467
	On the Proof Method for Bisimulation	479
	Towards a Calculus of Predicate Transformers	489
	An Abstract Account of Composition	499
	Syntax and Semantics of Procol	509
	Synthesizing Distinguishing Formulae for Real Time Systems	519
	From Timed Automata to Logic - and Back	529
	Incremental Model Checking for Decomposable Structures	540
	Automata for the Modal [mu]-calculus and Related Results	552
	A v-calculus with Local Views for Systems of Sequential Agents	563
	An Operator Calculus Approach to the Evolution of Dynamic Data Structures	574
	Authors Index	587