Parallel Processing for Artificial Intelligence 1 (Machine Intelligence and Pattern Recognition 14)

Parallel processing for AI problems is of great current interest because of its potential for alleviating the computational demands of AI procedures. The articles in this book consider parallel processing for problems in several areas of artificial intelligence: image processing, knowledge representation in semantic networks, production rules, mechanization of logic, constraint satisfaction, parsing of natural language, data filtering and data mining. The publication is divided into six sections. The first addresses parallel computing for processing and understanding images. The second discusses parallel processing for semantic networks, which are widely used means for representing knowledge - methods which enable efficient and flexible processing of semantic networks are expected to have high utility for building large-scale knowledge-based systems. The third section explores the automatic parallel execution of production systems, which are used extensively in building rule-based expert systems - systems containing large numbers of rules are slow to execute and can significantly benefit from automatic parallel execution. The exploitation of parallelism for the mechanization of logic is dealt with in the fourth section. While sequential control aspects pose problems for the parallelization of production systems, logic has a purely declarative interpretation which does not demand a particular evaluation strategy. In this area, therefore, very large search spaces provide significant potential for parallelism. In particular, this is true for automated theorem proving. The fifth section considers the problem of constraint satisfaction, which is a useful abstraction of a number of important problems in AI and other fields of computer science. It also discusses the technique of consistent labeling as a preprocessing step in the constraint satisfaction problem. Section VI consists of two articles, each on a different, important topic. The first discusses parallel formulation for the Tree Adjoining Grammar (TAG), which is a powerful formalism for describing natural languages. The second examines the suitability of a parallel programming paradigm called Linda, for solving problems in artificial intelligence. Each of the areas discussed in the book holds many open problems, but it is believed that parallel processing will form a key ingredient in achieving at least partial solutions. It is hoped that the contributions, sourced from experts around the world, will inspire readers to take on these challenging areas of inquiry. Parallel processing for AI problems is of great current interest because of its potential for alleviating the computational demands of AI procedures. The articles in this book consider parallel processing for problems in several areas of artificial intelligence: image processing, knowledge representation in semantic networks, production rules, mechanization of logic, constraint satisfaction, parsing of natural language, data filtering and data mining.

The publication is divided into six sections. The first addresses parallel computing for processing and understanding images. The second discusses parallel processing for semantic networks, which are widely used means for representing knowledge - methods which enable efficient and flexible processing of semantic networks are expected to have high utility for building large-scale knowledge-based systems. The third section explores the automatic parallel execution of production systems, which are used extensively in building rule-based expert systems - systems containing large numbers of rules are slow to execute and can significantly benefit from automatic parallel execution. The exploitation of parallelism for the mechanization of logic is dealt with in the fourth section. While sequential control aspects pose problems for the parallelization of production systems, logic has a purely declarative interpretation which does not demand a particular evaluation strategy. In this area, therefore, very large search spaces provide significant potential for parallelism. In particular, this is true for automated theorem proving. The fifth section considers the problem of constraint satisfaction, which is a useful abstraction of a number of important problems in AI and other fields of computer science. It also discusses the technique of consistent labeling as a preprocessing step in the constraint satisfaction problem. Section VI consists of two articles, each on a different, important topic. The first discusses parallel formulation for the Tree Adjoining Grammar (TAG), which is a powerful formalism for describing natural languages. The second examines the suitability of a parallel programming paradigm called Linda, for solving problems in artificial intelligence.

Each of the areas discussed in the book holds many open problems, but it is believed that parallel processing will form a key ingredient in achieving at least partial solutions. It is hoped that the contributions, sourced from experts around the world, will inspire readers to take on these challenging areas of inquiry. Content: Machine Intelligence and Pattern RecognitionPage ii Front MatterPage iii Copyright pagePage iv PrefacePages v-viiiLaveen N. Kanal, Vipin Kumar, Hiroaki Kitano, Christian Suttner EditorsPage xi AuthorsPages xiii-xv Chapter 1 - A Perspective on Parallel Processing in Computer Vision and Image UnderstandingPages 3-20Alok Choudhary, Sanjay Ranka Chapter 2 - On Supporting Rule-Based Image Interpretation Using a Distributed Memory MulticomputerPages 21-44Chen-Chau Chu, Joydeep Ghosh, J.K. Aggarwal Chapter 3 - Parallel Affine Image Warping*Pages 45-66George Gusciora, Jon A. Webb Chapter 4 - Image Processing On Reconfigurable Meshes With Buses*Pages 67-91Jing-Fu Jenq, Sartaj Sahni Chapter 5 - Inheritance Operations in Massively Parallel Knowledge RepresentationPages 95-113James Geller Chapter 6 - Providing Computationally Effective Knowledge Representation via Massive ParallelismPages 115-135Matthew P. Evett, William A. Andersen, James A. Hendler Chapter 7 - Speeding Up Production Systems: From Concurrent Matching to Parallel Rule Firing*Pages 139-160José Nelson Amaral, Joydeep Ghosh Chapter 8 - Guaranteeing Serializability in Parallel Production SystemsPages 161-205James G. Schmolze Chapter 9 - Parallel Automated Theorem Proving*Pages 209-257Christian B. Suttner, Johann Schumann Chapter 10 - Massive Parallelism in Inference SystemsPages 259-277Franz Kurfeß Chapter 11 - Representing Propositional Logic and Searching for Satisfiability in Connectionist NetworksPages 279-301Gadi Pinkas Chapter 12 - Parallel and Distributed Finite Constraint Satisfaction: Complexity, Algorithms and ExperimentsPages 305-334Ying Zhang, Alan K. Mackworth Chapter 13 - Parallel Algorithms and Architectures for Consistent LabelingPages 335-362Wei-Ming Lin, Viktor K. Prasanna Chapter 14 - Massively Parallel Parsing Algorithms for Natural Language*Pages 365-407Michael A. Palis, David S.L. Wei Chapter 15 - Process Trellis and FGP: Software Architectures for Data Filtering and MiningPages 409-428Michael Factor, Scott J. Fertig, David H. Gelernter