Advances in Information Systems Science, Softcover reprint of the original 1st ed. 1974 Volume 5

This volume, the fifth of a continuing series on information systems science, covers four timely topics which are in the mainstream of this field. In each chapter, an attempt is made to familiarize the reader with basic background information on the advances discussed, so that this volume may be used independently or in conjunction with the previous volumes. The emphasis in this volume is focused upon data organization and access methods, software for on-line minicomputer applications, advances in micropro­ graming, and gramm ars and recognizers for formal and natural languages. In Chapter 1, P. C. Patton presents a tutorial survey of data organiza­ tion and access methods which play a central role in information system design. Research in information processing has been shifted from numerical data processing to nonnumerical information handling. In the latter case, the information is carried not only by the data but also by the structure and organization of the data base. In this chapter, the author provides the reader with a comprehensive review of various data structures, including linear lists, array structures, tree structures, and multilinked structures. He also discusses the important problem of data-base design and management. This chapter concludes with several examples of information handling systems such as a matrix interpretive system, a generalized information management system, and a criminal justice information system. The rapid reduction in cost and great increase in capability of the mini­ computer have made it an attractive machine for information systems.

1 Data Organization and Access Methods.- 1. Introduction.- 1.1. Data Structure in Contrast to Data Content.- 1.2. Memory Structure and Organization.- 1.3. Some Distinctions: Content, Structure, and Physical Storage.- 2. Linear Lists and Processes.- 2.1. Linear List Structures.- 2.2. Storage Representation of Linear List Structures.- 2.3. Computer Storage of Linked Lists.- 2.4. List Processing Languages.- 3. Array Structures.- 3.1. Orthogonal Lists.- 3.2. Data Tables.- 3.3. Matrices.- 3.4. Hypermatrices.- 4. Tree Structures.- 4.1. Trees and Their Representation.- 4.2. Characteristics of Tree Structures.- 4.3. Tree Storage and Access Methods.- 4.4. Multiply Indexed Files.- 5. Multilinked Structures.- 5.1. Ring Structured Data.- 5.2. Directed Graphs.- 5.3. Programming Systems for Multilinked Structures.- 5.4. Graphics Data Processing.- 6. Data Base Design and Management.- 6.1. File Organization.- 6.2. Storage Media.- 6.3. Software and System Facilities.- 6.4. Interrelated Data Bases.- 6.5. Security and Confidentiality.- 7. Some Information Handling Systems.- 7.1. Matrix Interpretative Systems.- 7.2. Generalized Information Management Systems.- 7.3. Criminal Justice Information Systems.- 8. Summary and Conclusions.- 8.1. Information Systems Technology Today.- 8.2. Future Application Requirements.- 8.3. The Challenge to Hardware and System Designers 89 References.- 2 Design of Software for On-Line Minicomputer Applications.- 1. Introduction.- 2. The Keys to Minicomputer Software Organization.- 2.1. Data Structure.- 2.2. Interprogram Communication.- 2.3. Memory Management.- 2.4. Control Structures.- 3. Minicomputer Applications and Their Software Requirements.- 3.1. Data Acquisition and Direct Digital Control.- 3.2. Minicomputer-Based Communication Systems.- 3.3. Discrete Manufacturing Monitoring and Control Systems.- 3.4. Conclusions.- References.- 3 A Survey of the Status of Microprogramming.- 1. Introduction.- 1.1. Basic concepts.- 1.2. Hardwired Control vs. Microprogrammed Control.- 1.3. Programming vs. Microprogramming.- 2. Evolution of Microprogramming.- 2.1. Early Efforts.- 2.2. Contemporary Microprogrammed Computers.- 3. Architectural Variations in Current Microprogrammed Systems.- 3.1. Level of Control.- 3.2. Microinstruction Formats.- 3.3. Memory Considerations.- 4. Emulation.- 4.1. Reprogramming vs. Purely Software Interpretation.- 4.2. Software Interpretation vs. Microprogrammed Emulation.- 4.3. Hardware Compatibilities between Host and Target Systems.- 4.4. Current State of the Art of Emulation.- 5. Microprogrammed Implementation of Key Operating System and Language Translation Primitives.- 5.1. Parallel and Leveled Structures of Processes.- 6. Microdiagnostics.- 6.1. Architectural Implications.- 6.2. Difference between Conventional Diagnostics and Microdiagnostics.- 6.3. Current Status.- 6.4. Maintenance and Microdiagnostics.- 7. Microprogrammed Implementation of New I/O and Memory Devices.- 7.1. Disadvantages of the Conventional Organization.- 7.2. Scheduling via a Special Microprogrammed Processor.- 7.3. Accommodation of I/O and Memory Devices.- 8. Strategies for Microprogram Optimization.- 8.1. Optimization Objectives.- 8.2. Microprogram Characteristics.- 8.3. Analysis and Representation of Microprograms.- 8.4. Techniques.- 8.5. Implementation of Optimization Strategies.- 9. Applications of Microprogramming.- 9.1. Process Control.- 9.2. User-Microprogrammable Computers.- 9.3. Reconfiguration and Bypassing of Malfunctioning Subsystems by Microprogramming.- 10. Problem Areas and Future Prospects.- 10.1. Speed.- 10.2. LSI.- 11. Conclusions.- References.- 4 Some Grammars and Recognizers for Formal and Natural Languages.- 1. Introduction.- 2. Grammars and Languages.- 2.1. Types of Grammars.- 2.2. Finite-State Grammars.- 2.3. Context-Free Grammars.- 3. Recognizers and Acceptor Automata.- 3.1. Finite-State Automata.- 3.2. Pushdown Automata.- 3.3. Turing Machines.- 3.4. Linear Bounded Automata.- 4. Transformational Grammar.- 4.1. Base Component.- 4.2. Transformational Component.- 4.3. Semantic Component.- 4.4. Phonological Component.- 4.5. Problems of an Acceptor for Transformational Grammars.- 5. Applications in Information Science.- 5.1. Programming Languages.- 5.2. Natural Languages.- 6. Summary and Conclusions.- References.