Advances in Information Systems Science: Volume 4

by Julius T. Tou

Overview

Information systems science is advancing in various directions with rapid strides. Many diversified ideas and methodologies have been revised and extended. Numerous new techniques and approaches have been con­ ceived and developed. Some recent advances are covered in this series. The fourth volume of this series provides in-depth discussions of some newly developed theories and techniques concerning computer language-level augmentation, time-sharing systems, text editing systems, grammars and automata, and error correcting codes in computer arithmetic. In Chapter 1, V. K. Smirnov presents an authoritative review of the augmentation of machine language level. He discusses the effects of ex­ tension of computer functions upon machine language and the influence of development of software systems upon the augmentation of computer language level. Some specific ways of augmenting the machine language level are examined. The problem of information organization, storage, search, and retrieval in a computer is studied. The introduction of higher-level languages has stimulated widespread applications of computers. Formal language theory has been recognized as a topic offundamental importance in the study of information systems science. In Chapter 2, M. A. Harrison examines the phrase-structure grammars, the right linear grammars, the context-free grammars, the LR(k) grammars, and the context-sensitive grammars. The author discusses the relations between mathematical models of computers and a family of formal languages. The language theory may stimulate new ideas for the augmentation of machine language level.

Product Details

ISBN-13:	9781461590552
Publisher:	Springer US
Publication date:	01/23/2013
Edition description:	Softcover reprint of the original 1st ed. 1972
Pages:	330
Product dimensions:	6.10(w) x 9.25(h) x 0.03(d)

Table of Contents

1 Augmentation of Machine Language Level.- 1. Introduction.- 2. Software and Hardware Functions.- 3. Relation between Source and Machine Languages.- 4. Hardware Interpretation of Expressions.- 4.1. Advances in Programming and New Principles of Computer Organization.- 4.2. Use of Stack and Its Implementation.- 4.3. Direct Execution of Expressions.- 5. Memory Organization.- 5.1. Memory Addressing.- 5.2. Use of Names.- 5.3. Nonlinear Memory.- 6. Program Information Structure.- 7. Subroutine Calls.- 8. Computers with Built-in Compilers.- 9. Conclusion.- References.- 2 On the Relation between Grammars and Automata.- 1. Introduction.- 2. Phrase-Structure Grammars.- 2.1. Introduction.- 2.2. Context-Sensitive Grammars.- 2.3. Context-Free Grammars.- 2.4. Linear Context-Free Grammars.- 3. Finite Automata and Right Linear Grammars.- 4. Pushdown Automata and Context-Free Grammars.- 5. Deterministic Pushdown Automata and LR(k) Grammars….- 6. Linear Bounded Automata and Context-Sensitive Grammars. ..- 7. Turing Machines and Phrase-Structure Grammars.- References.- 3 An Introduction to Information Structures and Paging Considerations for On-Line Text Editing Systems.- 1. Introduction.- 1.1. Typical Structure of a Text Editor.- 1.2. The Classes of Editors.- 2. Basic Considerations for a Text Editor’s Information Structure.- 2.1. External Divisions (Segmentation).- 2.2. Internal Divisions (Paging).- 2.3. Storage Structure and Editing Operations.- 2.4. Garbage Collection.- 2.5. Arbitrary Access to Text and References.- 2.6. Summary of Basic Considerations.- 3. Fixed-Length Context Editors.- 4. Variable-Length-Line and “Superline” Editors.- 4.1. QED: A Superline Program Editor.- 4.2. ATS and VIPcom: Line Text Editors.- 5. Statement-Oriented Editors.- 5.1. The On-Line Text System (NLS).- 6. String-Oriented Editors.- 6.1. The Hypertext Editing System (HES).- 6.2. The File Retrieval and Editing System (FRESS).- 7. Conclusions.- References.- 4 An Introduction to the Structure of Time-Shared Computers.- 1. Introduction.- 1.1. Evolution of Computer Systems Usage.- 1.2. Time-Sharing System Components.- 1.3. Time-Sharing System Criteria.- 2. Computer Hardware.- 2.1. Introduction.- 2.2. Memories.- 2.3. Processors.- 2.4. Control Units.- 2.5. Switches.- 2.6. Terminals and Transducers.- 2.7. Hardware for Memory Mapping and Multiprogramming.- 2.8. Communication among Parts of Programs.- 2.9. Special Hardware.- 2.10. Summary.- 3. The Operating System Structure.- 3.1. Introduction.- 3.2. The Common User Programs.- 3.3. User Program Debugging Facilities.- 3.4. Console Control Program.- 3.5. The Operating System.- 3.6. Summary.- 4. The PDP-10 Time-Sharing System Structure.- 4.1. User Program Environment.- 4.2. The Operating System.- 5. The Economics of Time-Sharing.- 5.1. Time-Sharing versus Batch Applications.- 5.2. System Cost.- 5.3. System Component Costs and Benefits.- 6. Concluding Remarks.- References.- 5 Error-Correcting Codes in Computer Arithmetic.- 1. Introduction.- 1.1. Arithmetic Weight.- 1.2. Arithmetic Distance.- 1.3. Errors in Computer Arithmetic.- 2. The General Theory of AN-Codes.- 2.1. Minimum Arithmetic Distance.- 2.2. Error Correction in Integer Arithmetic.- 2.3. Arithmetic Modulo m.- 2.4. Errors in Addition Modulo m.- 2.5. Modular Weight and Modular Distance.- 2.6. Sphere-Packed or Perfect AN-Codes.- 2.7. Comment on Appropriate Values of the Modulus m = AB.- 3. Cyclic AN-Codes.- 3.1. Definition and General Theory.- 3.2. The Length Convention for Cyclic AN-Codes.- 3.3. Single-Error-Correcting AN-Codes.- 3.4. Calculation of Dmin for Cyclic AN-Codes.- 3.5. Mandelbaum-Barrows Equidistant Codes.- 3.6. Intermediate-Distance Cyclic AN-Codes.- 3.7. Analogy to Parity-Check Codes and the Chien-Hong Conjecture.- 4. Multiresidue Codes.- 4.1. Definition and Motivation.- 4.2. Relation to AN-Codes.- 4.3. Multiresidue Codes Derived from Cyclic AN-Codes.- 4.4. Syndromes in Multiresidue Codes.- 4.5. Failures in the Checkers.- 5. Further Comments on Arithmetic Codes.- 5.1. AN-Codes as Communications Codes.- 5.2. Burst Error Correction.- 5.3. Asymmetric Errors.- 6. Implementation of Arithmetic Codes.- 6.1. The Decoding Problem and Its Implementation.- 6.2. The JPL STAR Computer.- 7. Conclusions.- References.