Theory of Machines and Computations - 1st Edition - ISBN: 9780124177505, 9781483270302

Theory of Machines and Computations

1st Edition

Proceedings of an International Symposium on the Theory of Machines and Computations Held at Technion in Haifa, Israel, on August 16–19, 1971

Editors: Zvi Kohavi Azaria Paz
eBook ISBN: 9781483270302
Imprint: Academic Press
Published Date: 1st January 1971
Page Count: 430
Sales tax will be calculated at check-out Price includes VAT/GST
20% off
30% off
20% off
20% off
30% off
20% off
20% off
30% off
20% off
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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.

Table of Contents



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


No. of pages:
© Academic Press 1971
Academic Press
eBook ISBN:

About the Editor

Zvi Kohavi

Azaria Paz

Ratings and Reviews