Parallelism and Programming in Classifier Systems deals with the computational properties of the underlying parallel machine, including computational completeness, programming and representation techniques, and efficiency of algorithms. In particular, efficient classifier system implementations of symbolic data structures and reasoning procedures are presented and analyzed in detail. The book shows how classifier systems can be used to implement a set of useful operations for the classification of knowledge in semantic networks. A subset of the KL-ONE language was chosen to demonstrate these operations. Specifically, the system performs the following tasks: (1) given the KL-ONE description of a particular semantic network, the system produces a set of production rules (classifiers) that represent the network; and (2) given the description of a new term, the system determines the proper location of the new term in the existing network. These two parts of the system are described in detail. The implementation reveals certain computational properties of classifier systems, including completeness, operations that are particularly natural and efficient, and those that are quite awkward. The book shows how high-level symbolic structures can be built up from classifier systems, and it demonstrates that the parallelism of classifier systems can be exploited to implement them efficiently. This is significant since classifier systems must construct large sophisticated models and reason about them if they are to be truly ""intelligent."" Parallel organizations are of interest to many areas of computer science, such as hardware specification, programming language design, configuration of networks of separate machines, and artificial intelligence This book concentrates on a particular type of parallel organization and a particular problem in the area of AI, but the principles that are elucidated are applicable in the wider setting of computer science. Content: Front Matter, Page iii Copyright, Page iv List of Figures, Page vii List of Appendices, Page viii Preface, Page ix Dedication, Page x 1 - Introduction, Pages 1-7 2 - Background, Pages 9-33 3 - Approach, Pages 35-39 4 - Classifier Systems, Pages 41-64 5 - Classifier System Implementation of KL-ONE, Pages 65-103 6 - Analysis of Results, Pages 105-117 7 - Conclusions, Pages 119-125 APPENDIX A - Backus Normal Form Description of Input Language, Pages 127-128 APPENDIX B - Theorems, Pages 129-131 APPENDIX C - Processing Compound Queries, Page 132 APPENDIX D - Finding Maximum and Minimum Values with the Classifier System, Pages 133-135 APPENDIX E - Binary Addition with The Classifier System, Pages 136-144 APPENDIX F - Description of Mapping from KL-ONE to the Classifier System, Pages 145-149 APPENDIX G - Overhead Classifiers for Role Value Maps, Pages 149-151 APPENDIX H - Classifier List for Role Value Map Example, Pages 151-153 APPENDIX I - Classifiers for The MSS Example, Pages 153-157 APPENDIX J - Extended MSS Example, Pages 157-205 Bibliography, Pages 207-213
