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
Editors: Zvi Kohavi, Azaria Paz
Language: English
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

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Request a sales quote

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.

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