Foundations of Software Technology and Theoretical Computer Science: 19th Conference, Chennai, India, December 13-15, 1999 ProceedingsC. Pandu Rangan, V. Raman, R. Ramanujam This book constitutes the refereed proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'99, held in Chennai, India, in December 1999. The 30 revised full papers presented were carefully reviewed and selected from a total of 84 submissions. Also included are six invited contributions. The papers presented address all current issues in theoretical computer science and programming theory. |
Contents
1 | |
Dynamic Compressed Hyperoctrees with Application | 21 |
Largest EmptyRectangle among a Point Set | 34 |
Renaming Is Necessaryin Timed Regular Expressions | 47 |
P | 60 |
Fast Allocation and Deallocation with an Improved BuddySystem | 84 |
Optimal Bounds for Transformations of ωAutomata | 97 |
CTL + Is ExponentiallyM ore Succinct than CTL | 110 |
Session 6 | 245 |
On the Undecidabilityof Some Subclassical FirstOrder Logics | 258 |
Invited Talk 4 | 269 |
A High Girth Graph Construction and a Lower Bound | 283 |
Protecting Facets in Layered Manufacturing | 291 |
The Receptive Distributed πCalculus Extended Abstract | 304 |
Series and Parallel Operations on Pomsets | 316 |
Session 8 | 329 |
Invited Talk 2 | 122 |
Session 3 | 123 |
Explaining Updates by Minimal Sums | 142 |
A Foundation for Hybrid Knowledge Bases | 155 |
Session 4 | 168 |
Invited Talk 3 | 181 |
Approximation Algorithms for Routing and Call Scheduling | 201 |
A Randomized Algorithm for Flow Shop Scheduling | 213 |
Synthesizing Distributed Transition Systems from Global Specifications | 219 |
Symbolic Forward Analysis of Timed Automata | 232 |
Invited Talk 5 | 341 |
A Unifying Framework for Model Checking Labeled Kripke Structures | 369 |
Graded Modalities and Resource Bisimulation | 381 |
The Nonrecursive Power of Erroneous Computation | 394 |
Analysis of Quantum Functions PreliminaryVersion | 407 |
On Sets Growing Continuously | 420 |
Model Checking Knowledge and Time in Systems with Perfect Recall | 432 |
FSTTCS ISAAC Joint Session Talks | 446 |
Other editions - View all
Foundations of Software Technology and Theoretical Computer Science: 19th ... C. Pandu Rangan No preview available - 1999 |
Foundations of Software Technology and Theoretical Computer Science: 19th ... C. Pandu Rangan,V. Raman,R. Ramanujam No preview available - 1999 |
Common terms and phrases
algebras algorithm allocation amortized automata automaton binary binary search tree bisimulation block Büchi Büchi automata buddy system calculus called communication protocol complexity Computer Science condition consider constraint contains context corresponding CTL+ defined definition denote deterministic distribution edges equivalent exists facet failure detector finite formula function given graph H-resolution Hoare logic induction infinite input interval join-calculus Kripke structure labeled language Lemma linear LNCS logic lower bound LTOBDDs makespan MERs model checking nondeterministic nondeterministic variables OBDDs obtained operational semantics operations optimal pair paper path polynomial pomsets problem Proc proof properties Proposition protocol query Rabin Rabin automaton rebalancing rectangle recursive redex reduction relation resp result rule semantics sequence Springer-Verlag Streett Streett automaton subset superblock temporal temporal logic Theorem transition system TS-FO unary nodes vertices