Advances in Computing and Information - ICCI '91

This volume contains papers presented at the Third International Conference on Computing and Information, ICCI '91, held at Carleton University in Ottawa, Canada, May 27-29, 1991. The conference was organized by the School of Computer Science at Carleton University, and was sponsored by the Natural Sciences and Engineering Research Council of Canada (NSERC) and Carleton University. ICCI '91 was an international forum for the presentation of original results in research, development, and applications in computing and information processing. The conference was aimed at both practitioners and theoreticians, and was organized into five streams: - Algorithms and complexity, - Databases and information systems, - Parallel processing and systems, - Distributed computing and systems, - Expert systems, artificial intelligence. This volume contains three invited papers, by E.C.R. Hehner, R.L. Probert, and S.J. Smith, and 71 selected papers.

What's wrong with formal programming methods?.- Computer Science and communications protocols: Research relationships.- Reaping the benefits of mass production with massively parallel computing.- On the quickest path problem.- Practical adaptive sorting.- Lower bounds for algebraic computation trees of functions with finite domains.- Approximation algorithms for the Bandwidth Minimization Problem for a large class of trees.- The Interpolation-Based Bintree and its application to graphics.- On the k-coloring of intervals.- Folding a triangulated simple polygon: Structural and algorithmic results.- A relationship between self-organizing lists and binary search trees.- How costly can red-black trees be?.- Balance in AVL trees.- A tight lower bound for selection in sorted X+Y.- Greedy triangulation approximates the optimum and can be implemented in linear time in the average case.- Generating random graphs efficiently.- Linear extensions with backtracking.- Storing shortest paths for a polyhedron.- An improved join dependency for efficient constraint checking.- On the power of query-independent compilation.- Parallel transitive closure computation in highly scalable multiprocessors.- Methods and tools for integrating database systems and object-oriented programming systems.- Incremental database design revisited.- Partial document ranking by heuristic methods.- Context inheritance and content inheritance in an object-oriented data model.- Graphical specification of recursive queries.- On designing relational database schemes for efficient query processing.- The mean value approach to performance evaluation of time-stamp ordering algorithms.- A backend text retrieval machine for signature-based document ranking.- Partitioning and scheduling of parallel functional programs using complexity information.- Subtree availability in binary tree architectures.- An optimal parallel algorithm for the vertical segment visibility reporting problem.- A fault-tolerant binary tree architecture.- Unordered tree contraction.- Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models.- Parallel routing and sorting on the pancake network.- Practical parallel algorithms for chordal graphs.- Logarithmic time NC algorithms for comparability graphs and circle graphs.- Compact hypercubes: Properties and recognition.- Increasing communication bandwidth on hypercube.- Programming a parallel sort using distributed procedure calls.- A note on off-line permutation routing on a mesh-connected processor array.- A fully-pipelined solutions constructor for dynamic programming problems.- On the fault-tolerance of quasi-minimal cayley networks.- Some fast parallel algorithms for parentheses matching.- A simple optimal parallel algorithm to solve the lowest common ancestor problem.- Extended cycle shrinking: A restructuring method for parallel compilation.- Sequential and distributed algorithms for the all pairs quickest path problem.- An efficient approximation algorithm for hypercube scheduling.- An optimal parallel algorithm to reconstruct a binary tree from its traversals.- An efficient multiprocessor architecture for image processing in VLSI.- Generalized fault tolerance properties of star graphs.- A formal description of the IC* model of parallel computation.- An efficient algorithm for quiescence detection in a distributed system.- Interval arithmetic for computing performance guarantees in client-server software.- Enhanced reliability in scheduling critical tasks for hard real-time distributed systems.- A design and modeling environment to develop real-time, distributed software systems.- On the management of remote procedure call transactions.- Simple atomic snapshots a linear complexity solution with unbounded time-stamps.- A distributed scheduling algorithm for heterogeneous real-time systems.- A distributed solution to the k-out of-M resources allocation problem.- Efficient distributed resource scheduling for adaptive real-time operation support.- Mapping of fault-tolerant permutations in omega interconnection network.- Artificial neural networks for predicting silicon content in raw iron from blast furnaces.- A chemical reactor selection expert system created by training an artificial neural network.- A modeling technique for generating causal explanations of physical systems.- Planning in conceptual networks.- Empirical study of the meaning of the hedge “VERY”.- Kernel knowledge versus belt knowledge in default reasoning: A logical approach.- Neural network processing elements as a new generation of ”flip-flops”.- A proof-theoretic framework for nonmonotonic reasoning and logic programming.- On semantics, syntactics and fixpoints of general programs.- A framework for variable-resolution vision.- An RMS for temporal reasoning with abstraction.