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
Price includes VAT/GST
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

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


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

About the Editor

Zvi Kohavi

Azaria Paz

Ratings and Reviews