Kohavi / Paz Theory of Machines and Computations

Proceedings of an International Symposium on the Theory of Machines and Computations Held at Technion in Haifa, Israel, on August 16-19, 1971
1. Auflage 2014
ISBN: 978-1-4832-7030-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 430 Seiten, Web PDF

Theory of Machines and Computations consists of papers presented at the International Symposium on the Theory of Machines and Computations, held at Technion-Israel Institute of Technology in Haifa, Israel, in August 1971. This book is organized into five main sections-computability theory, formal and stochastic languages, finite automata, fault-detection experiments, and switching theory. In these sections, this compilation specifically discusses the computationally complex and pseudo-random zero-one valued functions and rate of convergence of local iterative schemes. The simple syntactic operators on full semiAFLs, whirl decomposition of stochastic systems, and existence of a periodic analogue of a finite automaton are also elaborated. This text likewise covers the theorems on additive automata, fault location in iterative logic arrays, and tree-threshold-synthesis of ternary functions. This publication is useful to practitioners and specialists interested in the theory of machines and computations.

Autoren/Hrsg.

Kohavi, Zvi

Paz, Azaria

Inhaltsverzeichnis

1;Front Cover;1
2;Theory of Machines and Computations;4
3;Copyright Page;5
4;Table of Contents;6
5;CONTRIBUTORS;10
6;PREFACE;14
7;SECTION I: COMPUTABILITY THEORY;16
7.1;CHAPTER 1. DECIDABLE PROPERTIES OF MONADIC FUNCTIONAL SCHEMAS;18
7.1.1;I. Monadic Functional Schemas;18
7.1.2;II. Herbrand Interpretations;21
7.1.3;III. Termination and Divergence of Functional Schemas;22
7.1.4;IV. Functional Schemas in Standard Form;23
7.1.5;V. Freedom of Functional Schemas;25
7.1.6;VI. Equivalence of Free Functional Schemas;29
7.1.7;References;32
7.2;CHAPTER 2. COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS;34
7.2.1;1 Introduction;34
7.2.2;2. Space-Bounded Turing Machines;36
7.2.3;3. A Compression Theorem for Computation Space;39
7.2.4;4. Sparse Complex Functions;42
7.2.5;5. Reducibility Among Computations;44
7.2.6;6. Pseudo-Random Sequences;50
7.2.7;References;55
7.3;CHAPTER 3. COMPUTATIONAL EQUIVALENCE;58
7.4;CHAPTER 4. HORNERS RULE IS UNIQUELY OPTIMAL;60
7.4.1;I Introduction;60
7.4.2;II Definitions and a Review of the Proof of Optimality;61
7.4.3;III Establishing Uniqueness;65
7.4.4;IV Conclusion;72
7.5;CHAPTER 5. ON LINEAR ALGORITHMS;74
7.5.1;I- ALGORITHMS - DEFINITIONS;74
7.5.2;II- THE ADDITIVE DEGREE OF FREEDOM;75
7.6;CHAPTER 6. ON THE RATE OF CONVERGENCE
OF LOCAL ITERATIVE SCHEMES;82
7.6.1;Reference;85
7.7;CHAPTER 7. QUEUES, STACKS AND GRAPHS;86
7.7.1;1. Queues in Parallel;86
7.7.2;2. Stacks in Parallel-Loading Before Unloading;89
7.7.3;References;101
7.8;CHAPTER 8. CONSTRUCTION OF SORTING PLANS;102
7.8.1;1. Introduction;102
7.8.2;2. Analysis of Sorting Plans;104
7.8.3;3. Construction of Sorting Plans;106
7.8.4;4. Illustrative Examples;109
7.8.5;References;110
7.9;CHAPTER 9. IFF PROGRAMS;114
7.9.1;1. Introduction and Definitions;114
7.9.2;2. General Properties;116
7.9.3;3. Polynomial Statements;118
7.9.4;4. Program Transformations;123
7.9.5;5. Concluding Remarks;126
7.9.6;References;126
8;SECTION II: FORMAL AND STOCHASTIC LANGUAGES;128
8.1;CHAPTER 10. SOME LANGUAGES RELATED TO
PLANAR MAPS;130
8.1.1;Introduction;130
8.1.2;I Definition of the code of a planar map;130
8.1.3;II Relations verified by Lk, Sk, Ak;132
8.1.4;III Generating power series;134
8.1.5;References;136
8.2;CHAPTER 11. FORMAL LANGUAGES AND FORMAL POWER SERIES;138
8.3;CHAPTER 12. SIMPLE SYNTACTIC OPERATORS
ON FULL SEMIAFLS;140
8.4;Chapter 13. Tree Adjunct, Parenthesis, and Distributed Adjunct Grammars;142
8.4.1;1. Summary;142
8.4.2;2. Review of Tree Adjunct Grammars;142
8.4.3;3. The Parenthesis Language Decision Problem;144
8.4.4;4. String Adjunct Languages - Local and Distributed;146
8.4.5;5. Every CFL is a Distributed Adjunct Language;147
8.4.6;References;152
8.5;CHAPTER 14. STATE GRAPHS AND CONTEXT FREE LANGUAGES;158
8.5.1;1. Introduction;158
8.5.2;2. Series of Finite State Machines;158
8.5.3;3. Letichevskii's Characterization; Derivatives;159
8.5.4;4. Graphs for Context Free Languages;161
8.5.5;5. Growth Rate;162
8.5.6;6. Equivalences and Operations;163
8.5.7;7. Graphs and Pushdown Automata;163
8.5.8;8. Extensions;164
8.5.9;9. Acknowledgement;164
8.5.10;10. References;164
8.6;CHAPTER 15. DISPERSION MATRICES AND STOCHASTIC AUTOMATA MORPHISMS;168
8.6.1;1. Introduction to stochastic automata morphisms;168
8.6.2;2. Dispersion matrices;168
8.6.3;3. Transition output Automata;170
8.6.4;4. Relations between states and between automata;171
8.6.5;5. The detection of ambiguity and the interchangeability morphism;173
8.6.6;6. The search algorithm for a dominant automaton with degree (c-2);176
8.6.7;7. Conclusion;179
8.6.8;References;180
8.7;CHAPTER 16. WHIRL DECOMPOSITION OF STOCHASTIC SYSTEMS;182
8.8;CHAPTER 17. ENCODING OF PROBABILISTIC
CONTEXT-FREE LANGUAGES;184
8.8.1;Introduction;184
8.8.2;1 Preliminary Definitions;184
8.8.3;2 Codes and The Coding Automaton;186
8.8.4;3. Classes of Coding Automata;188
8.8.5;4 Comparison;199
8.8.6;References;200
9;SECTION III: FINITE AUTOMATA;202
9.1;CHAPTER 18. An n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON;204
9.1.1;Introduction;204
9.1.2;Formal description of the algorithm;205
9.1.3;Correctness of algorithm;207
9.1.4;Analysis of the running time;208
9.1.5;Experimental results and conclusions;210
9.1.6;References;211
9.2;CHAPTER 19. BOUNDS ON THE LENGTH OF SYNCHRONIZING SEQUENCES AND THE ORDER OF INFORMATION LOSSLESSNESS;212
9.2.1;The Length of Synchronizing Sequences;212
9.2.2;Information Losslessness of Finite Order;215
9.2.3;References;217
9.3;CHAPTER 20. ON THE EXISTENCE OF A PERIODIC ANALOGUE OF A FINITE AUTOMATON;222
9.4;CHAPTER 21. EVERY FINITE SEQUENTIAL MACHINE
IS LINEARLY REALIZABLE;224
9.4.1;Introduction;224
9.4.2;1. The most general definition of realization;231
9.4.3;2. Realizations using homomorphic images;233
9.4.4;3. Realizations with restricted decoding;235
9.4.5;4. Realizations with finite state splitting;236
9.4.6;5. Realizations using isomorphic images;238
9.4.7;6. Realizations using equivalences;240
9.4.8;7. Conclusions;240
9.4.9;Acknowledgement;241
9.4.10;References;241
9.5;CHAPTER 22. ON THE LIMITS OF LINEARITY;244
9.5.1;Introduction;244
9.5.2;Simulation and Realization;244
9.5.3;Linear Sequential Machines;247
9.5.4;Linear 1-realizations;248
9.5.5;Linear Simulations;250
9.5.6;Linear Homomorphic Simulation;253
9.5.7;References;255
9.6;CHAPTER 23. THEOREMS ON ADDITIVE AUTOMATA;258
9.6.1;1. Introduction;258
9.6.2;2. Reduction of Additive Automata;260
9.6.3;3. Realization over Semigroup with operators;265
9.6.4;References;268
9.7;CHAPTER 24. CONNECTIVITY AND SEPARATION IN AUTOMATA;270
9.7.1;1. Introduction;270
9.7.2;2. Preliminaries;271
9.7.3;3. Separated Subautomata and Connected Automata;272
9.7.4;4. Separation and Connectivity Related to Strong Connectedness and Retrievability;279
9.7.5;5. Blocks and Homomorphisms;281
9.7.6;6. Blocks and Isomorphisms;285
9.7.7;References;288
9.8;CHAPTER 25. ALGEBRAIC THEORY OF m-ARY SYSTEMS;290
9.8.1;1. Introduction;290
9.8.2;2. m-ary Acceptors and Regular Events;291
9.8.3;3. m-ary Automata;295
9.8.4;4. Remark on m-ary Linear Systems;298
9.8.5;5. Remark on m-ary Context-Free Languages;299
9.8.6;6. References;300
9.9;CHAPTER 26. GROUPS AND AUTOMATA;302
9.9.1;I. Automata and Prefix Codes;302
9.9.2;II. The transition monoid T(A) and the Suschkewitsch group G(A);303
9.9.3;III. The automorphism group Aut(A) and the automorphism congruences;305
9.9.4;IV. The group congruences and the maximal kernel group (A);306
9.9.5;V. The maximal group homomorphic image (A);307
9.9.6;REFERENCES;307
9.10;CHAPTER 27. AUTOMATON STRUCTURE PRESERVING
MORPHISMS WITH APPLICATIONS
TO DECOMPOSITION AND SIMULATION;310
9.10.1;Introduction;310
9.10.2;Structured Functions;311
9.10.3;Function and Structure Preserving Morphisms;314
9.10.4;Remark;317
9.10.5;Conclusions;322
9.10.6;References;322
10;SECTION IV: FAULT-DETECTION EXPERIMENTS;326
10.1;CHAPTER 28. AN ALGORITHM FOR GENERATING
A FAULT DETECTION TEST FOR
A CLASS OF SEQUENTIAL CIRCUITS;328
10.1.1;Introduction;328
10.1.2;Notation and Definitions;329
10.1.3;Sequential Test Generation;332
10.1.4;References;338
10.2;CHAPTER 29. FAULT LOCATION IN ITERATIVE LOGIC ARRAYS;342
10.2.1;Introduction;342
10.2.2;Sufficient Conditions for Fault Location;344
10.2.3;Existence of Masking Inputs;348
10.2.4;Necessary and Sufficient Conditions;349
10.2.5;Cell Realizations for Fault Locatability;353
10.2.6;Conclusion;354
10.2.7;References;354
10.3;CHAPTER 30. AN APPROACH TO DESIGNING CHECKING EXPERIMENTS BASED ON A DYNAMIC MODEL;356
10.3.1;MACHINE IDENTIFICATION AND CHECKING EXPERIMENTS;356
10.3.2;PASSIVE MACHINE IDENTIFICATION;358
10.3.3;DESIGN OF CHECKING EXPERIMENTS;361
10.3.4;CONCLUSIONS;364
10.3.5;REFERENCES;364
11;SECTION V: SWITCHING THEORY;366
11.1;CHAPTER 31. TREE-THRESHOLD-SYNTHESIS OF
TERNARY FUNCTIONS;368
11.1.1;Introduction;368
11.1.2;The Tree-Synthesis Method;369
11.1.3;T-Basis Synthesis;374
11.1.4;Electronic Implementation;376
11.1.5;References;376
11.2;CHAPTER 32. A MINIMIZATION METHOD FOR 3-VALUED LOGIC FUNCTIONS;378
11.2.1;Introduction;378
11.2.2;Proposed Method;379
11.2.3;Fundamentals, Definitions and Notation;379
11.2.4;Procedure;381
11.2.5;Optimization;384
11.2.6;Conclusions;385
11.2.7;Acknowledgement;385
11.2.8;References;387
11.3;CHAPTER 33. THE MINIMIZATION OF CONTROL VARIABLES IN ADAPTIVE SYSTEMS;392
11.3.1;Introduction;392
11.3.2;Section 1;393
11.3.3;Section 2;398
11.3.4;Conclusions;400
11.4;CHAPTER 34. ON COMPLETENESS OF A SET OF AMBIGUOUS LOGIC PRIMITIVES;402
11.4.1;Introduction;402
11.4.2;Fault-tolerant Function;403
11.4.3;Theorems;404
11.4.4;Acknowledgments;409
11.4.5;References;409
11.5;CHAPTER 35. MINIMIZING THE NUMBER OF INTERNAL STATES IN INCOMPLETELY SPECIFIED PULSE INPUT
ASYNCHRONOUS SEQUENTIAL MACHINES;410
11.5.1;1. Introduction;410
11.5.2;2. Structure of complete and incomplete primitive PA tables;411
11.5.3;3. State reduction of complete primitive PA tables;412
11.5.4;4. State reduction of incomplete primitive PA tables;413
11.5.5;References;419
11.6;CHAPTER 36. ON THE ANALYSIS OF AUTONOMOUS SEQUENTIAL NETWORKS OF ITERATIVE ADAPTIVE ELEMENTS;424
11.7;CHAPTER 37. ASSIGNMENT AND NEXT STATE EQUATIONS OF ASYNCHRONOUS SEQUENTIAL MACHINES;426
12;AUTHOR INDEX;428