Foundations of Software Technology and Theoretical Computer Science

Klappentext
This volume gives the proceedings of the Tenth Conference on Foundations of Software Technology and Theoretical Computer Science. These conferences are organized and run by the computer science research community in India, and their purpose is to provide a forum for professional interaction between members of this research community and their counterparts in different parts of the world. The volume includes four invited papers on: - reasoning about linear constraints using parametric queries, - the parallel evaluation of classes of circuits, - a theory of commonsense visual reasoning, - natural language processing, complexity theory and logic. The 26 submitted papers are organized into sections on logic, automata and formal languages, theory of programming, parallel algorithms, geometric algorithms, concurrency, distributed computing, and semantics.

Inhalt
Software Development Graphs a unifying concept for software development?.- Concurrent runtime checking of annotated Ada programs.- Recovery of noncurrent variables in source-level debugging of optimized code.- Automatic retargetable code generation: A new technique.- An implementation of OBJ2: An object-oriented language for abstract program specification.- Explicit representation of terms defined by counter examples.- A framework for intelligent backtracking in logic programs.- A generalization of Backus' FP.- Shortest-path motion.- Via assignment in single row routing.- Average-case analysis of the Modified Harmonic algorithm.- Covering minima and lattice point free convex bodies.- Binary decompositions and acyclic schemes.- Thin homogeneous sets of factors.- Irreducible polynomials over finite fields.- Basis reduction and evidence for transcendence of certain numbers.- A characterization of asynchronous message-passing.- Modular synthesis of deadlock-free control structures.- Distributed resource sharing in computer networks.- On proving communication closedness of distributed layers.- A distributed algorithm for edge-disjoint path problem.- Scheduling of hard real-time systems.- A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach.- Connectivity algorithms using rubber bands.- On simple and creative sets in NP.- Complexity of sufficient-completeness.- Sampling a population with a semi-random source.- An optimal parallel algorithm for dynamic expression evaluation and its applications.- Extension of the parallel nested dissection algorithm to path algebra problems.- On synthesizing systolic arrays from Recurrence Equations with Linear Dependencies.- An efficient parallel algorithm for term matching.