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
- 1st Edition - January 1, 1971
- Imprint: Academic Press
- Editors: Zvi Kohavi, Azaria Paz
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 4 1 7 8 - 4
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 7 0 3 0 - 2
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… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteTheory 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.
Contributors
Preface
Section I. Computability Theory
Decidable Properties of Monadic Functional Schemas
Computationally Complex and Pseudo-Random Zero-One Valued Functions
Computational Equivalence (Abstract)
Horners Rule Is Uniquely Optimal
On Linear Algorithms
On the Rate of Convergence of Local Iterative Schemes
Queues, Stacks, and Graphs
Construction of Sorting Plans
IFF Programs
Section II. Formal And Stochastic Languages
1. Formal Languages
Some Languages Related to Planar Maps
Formal Languages and Formal Power Series (Abstract)
Simple Syntactic Operators on Full Semiafls (Abstract)
Tree Adjunct, Parenthesis, and Distributed Adjunct Grammars
State Graphs and Context Free Languages
2. Stochastic Automata and Languages
Dispersion Matrices and Stochastic Automata Morphisms
Whirl Decomposition of Stochastic Systems (Abstract)
Encoding of Probabilistic Context-Free Languages
Section III. Finite Automata
1. Algorithms and Bounds
An n log n Algorithm for Minimizing States in a Finite Automaton
Bounds on the Length of Synchronizing Sequences and the Order of Information Losslessness
On the Existence of a Periodic Analogue of a Finite Automaton (Abstract)
2. Linear Machines
Every Finite Sequential Machine Is Linearly Realizable
On the Limits of Linearity
Theorems on Additive Automata
3. Algebraic Theory of Automata
Connectivity and Separation in Automata
Algebraic Theory of m-ARY Systems
Groups and Automata
Automaton Structure Preserving Morphisms with Applications to Decomposition and Simulation
Section IV. Fault-Detection Experiments
An Algorithm for Generating a Fault Detection Test for a Class of Sequential Circuits
Fault Location in Iterative Logic Arrays
An Approach to Designing Checking Experiments Based on a Dynamic Model
Section V. Switching Theory
1. Combinational Circuits
Tree-Threshold-Synthesis of Ternary Functions
A Minimization Method for 3-Valued Logic Functions
The Minimization of Control Variables in Adaptive Systems
On Completeness of a Set of Ambiguous Logic Primitives
2. Sequential Circuits
Minimizing the Number of Internal States in Incompletely Specified Pulse Input Asynchronous Sequential Machines
On the Analysis of Autonomous Sequential Networks of Iterative Adaptive Elements (Abstract)
Assignment and Next State Equations of Asynchronous Sequential Machines (Abstract)
Author Index
- Edition: 1
- Published: January 1, 1971
- No. of pages (eBook): 430
- Imprint: Academic Press
- Language: English
- Paperback ISBN: 9781483241784
- eBook ISBN: 9781483270302
Read Theory of Machines and Computations on ScienceDirect