Ebook: Advances in Computing and Information — ICCI '91: International Conference on Computing and Information Ottawa, Canada, May 27–29, 1991 Proceedings

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.

---

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.

---

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.
Content:
Front Matter....Pages -
What's wrong with formal programming methods?....Pages 1-23
Computer Science and communications protocols: Research relationships....Pages 24-32
Reaping the benefits of mass production with massively parallel computing....Pages 33-42
On the quickest path problem....Pages 43-46
Practical adaptive sorting....Pages 47-54
Lower bounds for algebraic computation trees of functions with finite domains....Pages 55-65
Approximation algorithms for the Bandwidth Minimization Problem for a large class of trees....Pages 66-77
The Interpolation-Based Bintree and its application to graphics....Pages 78-89
On the k-coloring of intervals....Pages 90-101
Folding a triangulated simple polygon: Structural and algorithmic results....Pages 102-110
A relationship between self-organizing lists and binary search trees....Pages 111-116
How costly can red-black trees be?....Pages 117-126
Balance in AVL trees....Pages 127-133
A tight lower bound for selection in sorted X+Y....Pages 134-138
Greedy triangulation approximates the optimum and can be implemented in linear time in the average case....Pages 139-148
Generating random graphs efficiently....Pages 149-160
Linear extensions with backtracking....Pages 161-168
Storing shortest paths for a polyhedron....Pages 169-180
An improved join dependency for efficient constraint checking....Pages 181-184
On the power of query-independent compilation....Pages 185-196
Parallel transitive closure computation in highly scalable multiprocessors....Pages 197-206
Methods and tools for integrating database systems and object-oriented programming systems....Pages 207-218
Incremental database design revisited....Pages 219-230
Partial document ranking by heuristic methods....Pages 231-239
Context inheritance and content inheritance in an object-oriented data model....Pages 240-251
Graphical specification of recursive queries....Pages 252-263
On designing relational database schemes for efficient query processing....Pages 264-275
The mean value approach to performance evaluation of time-stamp ordering algorithms....Pages 276-287
A backend text retrieval machine for signature-based document ranking....Pages 288-297
Partitioning and scheduling of parallel functional programs using complexity information....Pages 299-311
Subtree availability in binary tree architectures....Pages 312-322
An optimal parallel algorithm for the vertical segment visibility reporting problem....Pages 323-334
A fault-tolerant binary tree architecture....Pages 335-346
Unordered tree contraction....Pages 347-349
Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models....Pages 350-359
Parallel routing and sorting on the pancake network....Pages 360-371
Practical parallel algorithms for chordal graphs....Pages 372-382
Logarithmic time NC algorithms for comparability graphs and circle graphs....Pages 383-394
Compact hypercubes: Properties and recognition....Pages 395-402
Increasing communication bandwidth on hypercube....Pages 403-414
Programming a parallel sort using distributed procedure calls....Pages 415-417
A note on off-line permutation routing on a mesh-connected processor array....Pages 418-420
A fully-pipelined solutions constructor for dynamic programming problems....Pages 421-430
On the fault-tolerance of quasi-minimal cayley networks....Pages 431-442
Some fast parallel algorithms for parentheses matching....Pages 443-454
A simple optimal parallel algorithm to solve the lowest common ancestor problem....Pages 455-461
Extended cycle shrinking: A restructuring method for parallel compilation....Pages 462-470
Sequential and distributed algorithms for the all pairs quickest path problem....Pages 471-473
An efficient approximation algorithm for hypercube scheduling....Pages 474-483
An optimal parallel algorithm to reconstruct a binary tree from its traversals....Pages 484-495
An efficient multiprocessor architecture for image processing in VLSI....Pages 496-507
Generalized fault tolerance properties of star graphs....Pages 509-519
A formal description of the IC* model of parallel computation....Pages 520-531
An efficient algorithm for quiescence detection in a distributed system....Pages 532-534
Interval arithmetic for computing performance guarantees in client-server software....Pages 535-546
Enhanced reliability in scheduling critical tasks for hard real-time distributed systems....Pages 547-558
A design and modeling environment to develop real-time, distributed software systems....Pages 559-570
On the management of remote procedure call transactions....Pages 571-581
Simple atomic snapshots a linear complexity solution with unbounded time-stamps....Pages 582-587
A distributed scheduling algorithm for heterogeneous real-time systems....Pages 588-598
A distributed solution to the k-out of-M resources allocation problem....Pages 599-609
Efficient distributed resource scheduling for adaptive real-time operation support....Pages 610-627
Mapping of fault-tolerant permutations in omega interconnection network....Pages 628-639
Artificial neural networks for predicting silicon content in raw iron from blast furnaces....Pages 641-644
A chemical reactor selection expert system created by training an artificial neural network....Pages 645-656
A modeling technique for generating causal explanations of physical systems....Pages 657-668
Planning in conceptual networks....Pages 669-671
Empirical study of the meaning of the hedge “VERY”....Pages 672-674
Kernel knowledge versus belt knowledge in default reasoning: A logical approach....Pages 675-686
Neural network processing elements as a new generation of ”flip-flops”....Pages 687-698
A proof-theoretic framework for nonmonotonic reasoning and logic programming....Pages 699-708
On semantics, syntactics and fixpoints of general programs....Pages 709-720
A framework for variable-resolution vision....Pages 721-732
An RMS for temporal reasoning with abstraction....Pages 733-744
Back Matter....Pages -

---

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.
Content:
Front Matter....Pages -
What's wrong with formal programming methods?....Pages 1-23
Computer Science and communications protocols: Research relationships....Pages 24-32
Reaping the benefits of mass production with massively parallel computing....Pages 33-42
On the quickest path problem....Pages 43-46
Practical adaptive sorting....Pages 47-54
Lower bounds for algebraic computation trees of functions with finite domains....Pages 55-65
Approximation algorithms for the Bandwidth Minimization Problem for a large class of trees....Pages 66-77
The Interpolation-Based Bintree and its application to graphics....Pages 78-89
On the k-coloring of intervals....Pages 90-101
Folding a triangulated simple polygon: Structural and algorithmic results....Pages 102-110
A relationship between self-organizing lists and binary search trees....Pages 111-116
How costly can red-black trees be?....Pages 117-126
Balance in AVL trees....Pages 127-133
A tight lower bound for selection in sorted X+Y....Pages 134-138
Greedy triangulation approximates the optimum and can be implemented in linear time in the average case....Pages 139-148
Generating random graphs efficiently....Pages 149-160
Linear extensions with backtracking....Pages 161-168
Storing shortest paths for a polyhedron....Pages 169-180
An improved join dependency for efficient constraint checking....Pages 181-184
On the power of query-independent compilation....Pages 185-196
Parallel transitive closure computation in highly scalable multiprocessors....Pages 197-206
Methods and tools for integrating database systems and object-oriented programming systems....Pages 207-218
Incremental database design revisited....Pages 219-230
Partial document ranking by heuristic methods....Pages 231-239
Context inheritance and content inheritance in an object-oriented data model....Pages 240-251
Graphical specification of recursive queries....Pages 252-263
On designing relational database schemes for efficient query processing....Pages 264-275
The mean value approach to performance evaluation of time-stamp ordering algorithms....Pages 276-287
A backend text retrieval machine for signature-based document ranking....Pages 288-297
Partitioning and scheduling of parallel functional programs using complexity information....Pages 299-311
Subtree availability in binary tree architectures....Pages 312-322
An optimal parallel algorithm for the vertical segment visibility reporting problem....Pages 323-334
A fault-tolerant binary tree architecture....Pages 335-346
Unordered tree contraction....Pages 347-349
Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models....Pages 350-359
Parallel routing and sorting on the pancake network....Pages 360-371
Practical parallel algorithms for chordal graphs....Pages 372-382
Logarithmic time NC algorithms for comparability graphs and circle graphs....Pages 383-394
Compact hypercubes: Properties and recognition....Pages 395-402
Increasing communication bandwidth on hypercube....Pages 403-414
Programming a parallel sort using distributed procedure calls....Pages 415-417
A note on off-line permutation routing on a mesh-connected processor array....Pages 418-420
A fully-pipelined solutions constructor for dynamic programming problems....Pages 421-430
On the fault-tolerance of quasi-minimal cayley networks....Pages 431-442
Some fast parallel algorithms for parentheses matching....Pages 443-454
A simple optimal parallel algorithm to solve the lowest common ancestor problem....Pages 455-461
Extended cycle shrinking: A restructuring method for parallel compilation....Pages 462-470
Sequential and distributed algorithms for the all pairs quickest path problem....Pages 471-473
An efficient approximation algorithm for hypercube scheduling....Pages 474-483
An optimal parallel algorithm to reconstruct a binary tree from its traversals....Pages 484-495
An efficient multiprocessor architecture for image processing in VLSI....Pages 496-507
Generalized fault tolerance properties of star graphs....Pages 509-519
A formal description of the IC* model of parallel computation....Pages 520-531
An efficient algorithm for quiescence detection in a distributed system....Pages 532-534
Interval arithmetic for computing performance guarantees in client-server software....Pages 535-546
Enhanced reliability in scheduling critical tasks for hard real-time distributed systems....Pages 547-558
A design and modeling environment to develop real-time, distributed software systems....Pages 559-570
On the management of remote procedure call transactions....Pages 571-581
Simple atomic snapshots a linear complexity solution with unbounded time-stamps....Pages 582-587
A distributed scheduling algorithm for heterogeneous real-time systems....Pages 588-598
A distributed solution to the k-out of-M resources allocation problem....Pages 599-609
Efficient distributed resource scheduling for adaptive real-time operation support....Pages 610-627
Mapping of fault-tolerant permutations in omega interconnection network....Pages 628-639
Artificial neural networks for predicting silicon content in raw iron from blast furnaces....Pages 641-644
A chemical reactor selection expert system created by training an artificial neural network....Pages 645-656
A modeling technique for generating causal explanations of physical systems....Pages 657-668
Planning in conceptual networks....Pages 669-671
Empirical study of the meaning of the hedge “VERY”....Pages 672-674
Kernel knowledge versus belt knowledge in default reasoning: A logical approach....Pages 675-686
Neural network processing elements as a new generation of ”flip-flops”....Pages 687-698
A proof-theoretic framework for nonmonotonic reasoning and logic programming....Pages 699-708
On semantics, syntactics and fixpoints of general programs....Pages 709-720
A framework for variable-resolution vision....Pages 721-732
An RMS for temporal reasoning with abstraction....Pages 733-744
Back Matter....Pages -
....