This book constitutes the refereed proceedings of the 17th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'97. The 18 revised full papers presented were selected from a total of 68 submissions. Also included are five invited papers by Ed Clarke, Deepak Kapur, Madhu Sudan, Vijaya Ramachandran, and Moshe Vardi. Among the topics addressed are concurrency, Petri nets, graph computations, program verification, model checking, recursion theory, rewriting, and error-correcting codes.
Author(s): Vijaya Ramachandran (auth.), S. Ramesh, G Sivakumar (eds.)
Series: Lecture Notes in Computer Science 1346
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1997
Language: English
Pages: 351
Tags: Theory of Computation; Programming Languages, Compilers, Interpreters; Discrete Mathematics in Computer Science; Programming Techniques; Artificial Intelligence (incl. Robotics)
QSM: A general purpose shared-memory model for parallel computation....Pages 1-5
Approximating geometric domains through topological triangulations....Pages 6-21
Solving some discrepancy problems in NC....Pages 22-36
Graph editing to bipartite interval graphs: Exact and asymptotic bounds....Pages 37-53
Model checking....Pages 54-56
Recursion versus iteration at higher-orders....Pages 57-73
Compilation and equivalence of imperative objects....Pages 74-87
On the expressive power of rewriting....Pages 88-102
Mechanizing verification of arithmetic circuits: SRT division....Pages 103-122
On the complexity of parallel implementation of logic programs....Pages 123-137
An abductive semantics for disjunctive logic programs and its proof procedure....Pages 138-152
Assumption-commitment in automata....Pages 153-168
Compositional design of multitolerant repetitive byzantine agreement....Pages 169-183
Algorithmic issues in coding theory....Pages 184-199
Sharper results on the expressive power of generalized quantifiers....Pages 200-219
Improved lowness results for solvable black-box group problems....Pages 220-234
On resource-bounded measure and pseudorandomness....Pages 235-249
Verification of open systems....Pages 250-266
Hoare-Style compositional proof systems for reactive shared variable concurrency....Pages 267-283
A simple characterization of stuttering bisimulation....Pages 284-296
General refinement for high level petri nets....Pages 297-311
Polynomial-Time Many-One reductions for Petri nets....Pages 312-326
Computing reachability properties hidden in finite net unfoldings....Pages 327-341
