This volume contains the proceedings of the Eleventh Conference on Foundations of Software Technology and Theoretical Computer Science held in New Dehli, India December 17-19, 1991. Three invited papers and 25 contributed papers selected from 78 submissions by authors from many different countries reflect the current research concerns of the theoreticalcomputer science community. The topics covered include: -Algorithms (sequential, parallel and geometric) -Automata theory -Functional programming -Learning -Logic of programs -Semantics -Structural complexity theory -Type theory.
Author(s): Manuel Blum (auth.), Somenath Biswas, Kesav V. Nori (eds.)
Series: Lecture Notes in Computer Science 560
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1991
Language: English
Pages: 425
Tags: Logics and Meanings of Programs; Computation by Abstract Devices; Programming Languages, Compilers, Interpreters; Mathematical Logic and Formal Languages; Combinatorics; Computer Graphics
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
