Foundations of Software Technology and Theoretical Computer Science: 11th Conference, New Delhi, India December 17–19, 1991 Proceedings

Program checking....Pages 1-9
Randomizing reductions of search problems....Pages 10-24
Time analysis, cost equivalence and program refinement....Pages 25-39
AC-equation solving....Pages 40-56
On the operational interpretation of complex types....Pages 57-70
Tense logics for local reasoning in distributed systems....Pages 71-88
Failures semantics for a simple process language with refinement....Pages 89-108
Correctness of programs over poor signatures....Pages 109-120
Complexity issues for vacillatory function identification....Pages 121-140
A purely algebraic proof of McNaughton\'s theorem on infinite words....Pages 141-151
The structure and complexity of minimal NFA\'s over a unary alphabet....Pages 152-171
Relativised cellular automata and complexity classes....Pages 172-185
Computing the order of a locally testable automaton....Pages 186-211
On the structure and complexity of infinite sets with minimal perfect hash functions....Pages 212-223
NP-hard sets and creativeness over constant time languages....Pages 224-241
Complete problems involving boolean labelled structures and projection translations....Pages 242-260
Is BP.⊕ $$\\mathcal{P}$$ a probabilistic class?....Pages 261-265
Fast stable in-place sorting with O(n) data moves....Pages 266-277
A theorem on the approximation of set cover and vertex cover....Pages 278-287
A fast algorithm for the principal partition of a graph....Pages 288-306
Uniform circuits and exclusive read PRAMs....Pages 307-318
Contracting planar graphs efficiently in parallel....Pages 319-335
Fast deterministic selection on mesh-connected processor arrays....Pages 336-346
Improved selection in totally monotone arrays....Pages 347-359
Designing secure communication protocols from trust specifications....Pages 360-368
Computing the shortest path tree in a weak visibility polygon....Pages 369-389
Usefulness of angle-sweep over line-sweep....Pages 390-419
Petri nets and transition systems (Abstract for an invited talk)....Pages 420-420