Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

FUNCTIONS REALIZED BY CONSISTENT SEQUENTIAL MACHINES

IP.com Disclosure Number: IPCOM000128163D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 49 page(s) / 88K

Publishing Venue

Software Patent Institute

Related People

Arthur R. Butz: AUTHOR [+3]

Abstract

A sequential machine is "consistent" iff when both the input and output strings of symbols are regarded as representing numerical quantities according to conventional interpretations (quantitatively more significant symbols occurring earlier than less), then the machine may be regarded as calculating are ordinary numerical function for all possible input strings. Consistent sequential machines have not been of significant interest to automata theorists but they may have applications in signal processing. The relationships holding among (L) input-output alphabets and (ili) structures of consistent sequential machines and (Lii) properties of numerical functions thus realized, are explored. In connection with (.Li), the finite state and permutation free properties are of particular interest. In connec-tion with (~iii), the properties of monotonicity, invertibility, piecewise linearity, and differentiability, are of particular interest. Synthesis methods are not significantly treated. lb

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 49

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

FUNCTIONS REALIZED BY CONSISTENT SEQUENTIAL MACHINES

Arthur R. Butz Department of Electrical Engineering and Computer Science Northwestern University

#80-01-SCT-01

January, FUNCTIONS REALIZED BY CONSISTENT SEQUENTIAL MACHINES

Arthur R. Butz Department of Electrical Engineering and Computer Science Northwestern University Evanston, Illinois 60201

Abstract

A sequential machine is "consistent" iff when both the input and output strings of symbols are regarded as representing numerical quantities according to conventional interpretations (quantitatively more significant symbols occurring earlier than less), then the machine may be regarded as calculating are ordinary numerical function for all possible input strings.

Consistent sequential machines have not been of significant interest to automata theorists but they may have applications in signal processing.

The relationships holding among (L) input-output alphabets and (ili) structures of consistent sequential machines and (Lii) properties of numerical functions thus realized, are explored. In connection with (.Li), the finite state and permutation free properties are of particular interest. In connec-tion with (~iii), the properties of monotonicity, invertibility, piecewise linearity, and differentiability, are of particular interest.

Synthesis methods are not significantly treated.

lb

I . INTRODUCTION

y) is a sequential machine in the Mealy sense. OP is the (not necessary finite) set of states. 7? is the input alphabet of integers

(Equation Omitted)

is the output alphabet of integers

(Equation Omitted)

8: d x j is the complete state transition function, where

(Equation Omitted)

Northwestern University Page 1 Dec 31, 1980

Page 2 of 49

FUNCTIONS REALIZED BY CONSISTENT SEQUENTIAL MACHINES

has the usual meaning

where X is the blank symbol.

(Equation Omitted)

is the complete output function and U, w E 7?* is interpreted as the output word T E 74 that results when 67 is started in state a and input word w is applied; thus w and T have the same number of symbols and

(Equation Omitted)

XM is the set of infinite sequences of integers in VZ; x EXM when x is an infinite cocatenation x = M I m 2 m P4 .... m I E M. If 61 is started in state a 6;.,P and an input sequence

z EXN is applied where

(Equation Omitted)

then an output sequence as x above results. Both z and x can be interpreted as representing numbers in the closed unit interval U according to the usual convention:

(Equation Omitted)

However in general it is not the case that 67 thereby calculates a function whose domain is U and range C U, because some rationals in U have two rep-resentations. In order that 67 calculate a function f: U -i-U it is necessary that numerically equivalent input sequences generate numerically equivalent output sequences. .2

It appears that only Eilenberg ([14], Ch. 13) has published results associated with such machines, which he calls consiste...