STABILETY AND CUT
POENTS 0F PROBABILISUC AUWMATA

Thesis for the Degree of Ph. D.
MECHIGAN STATE. UNIVERSHY
GERALD M. FLACHS
1967

llfllfll/lI/ll/II/l/I/fl/II/l/lI/fl/fi/lll ///I/ mm V w A R Y L?-

1293 10159 6637 fichiqan State .
University 1‘. ~

If
vth' ‘w .

LQWW'W‘ '

This is to certify that the

thesis entitled

STABILITY AND CUT POINTS
OF
PR OBABILISTIC AUTOMATA

presented by

Gerald M. Flachs

has been accepted towards fulfillment
of the requirements for

Ph. D. degree in E. E.

4, AMA JAW—

0 Major professor

 

Date jgivfivwg‘P/V 201 (€97

0-169

ABSTRACT
STABILITY AND CUT POINTS OF PROBABILISTIC AUTOMATA
by Gerald M. Flachs

The concept of probabilistic automata has recently been the
object of much study by automata theorists. The behavior of a
probabilistic automaton is essentially characterized by products
of matrices selected from a given finite set of stochastic symbol
matrices. It is important in many applications that these matrix
products be stable with respect to small perturbations of the
entries in the symbol matrices. This thesis concerns three
different types of stability problems that arise when one considers
the effect of these small perturbations upon the behavior of the
probabilistic automaton. These are: l) strict stability, denoted
"s-stability"; Z) tape acceptance stability, denoted "a-stability";
3) zero stability, denoted ”O-stability".

Strict stability is concerned with the asymptotic behavior
of long products of stochastic matrices whose entries are subjected
to small perturbations. Necessary and sufficient conditions are
given for an arbitrary probabilistic automaton to be strictly stable.
An effective algorithm is given for deciding whether or not an
arbitrary automaton is strictly stable.

Tape acceptance stability is concerned with the tape accep-
tance behavior when the entries in the symbol matrices are subjected

to small perturbations. Sufficient conditions are given for a-stability

GERALD M. FLAC HS

in terms of s-stability. Also, sufficient conditions are given for
a-stability that do not require s-stability. This result is essentially
a regional stability result that gives the size of perturbations allowed
without causing a-instability.

Zero stability, subject of the major contributions of this
thesis, is concerned with the strict stability problem when the
perturbations are not allowed to change the zero entry configurations
of the symbol matrices. Zero stability results are given in terms
of the cyclic structure of probabilistic automata. The fundamental
properties of the cyclic structure are developed and refined in
order to obtain some O-stability results. Zero stability results
are also given in terms of the algebraic structure of probabilistic
automata, which is developed along definite algebraic lines. An
important class of probabilistic automata, called ”zero-reset"
automata, and including group automata, is shown to be 0-stab1e.

Finally, isolated cut-point problems are discussed using
two different approaches. In a set theoretic approach, a set of
response intervals is defined which contain the response points.

In a topological approach, a pseudo-closure operator is defined
that encloses the points which are not isolated cut points. Several
tests are given for solving these problems for a large class of

aut omata .

STABILITY AND CUT POINTS OF PROBABILISTIC AUTOMATA

BY

{\
0.x

Gerald M. Flachs

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOC TOR OF PHILOSOPHY
Department of Electrical Engineering

1967

ACKNOWLEDGEMENTS

The author is pleased to acknowledge the advice and guidance
given throughout his doctoral program by Dr. J. S. Frame. He
also wishes to thank Dr. W. L.Kilmer for calling attention to
several problems discussed in this thesis and for his many thought
provoking discussions. He is also grateful for the financial
assistance rendered by the National Science Foundation. Finally,
the author wishes to acknowledge the help and understanding given

far beyond the call of duty by his wife, Mary.

ii

TABLE OF CONTENTS

Page
ABSTRACT
ACKNOWLEDGEMENTS ............ . ...... ii
I. INTRODUCTION. . . . ............. . . . .
l. l. The Probabilistic Automaton Concept ...... 2
II. GENERAL STABILITY PROBLEM ...... . . . . . 6
2. 1. Stability Concepts . . . ..... . ........ 6
Z. 2. Stochastic Matrices and Their Products ..... 10
2.3. Strict Stability. . . . . . . . . . . . . . . . . . . 22
Z. 4. Acceptance Stability ............... 26
III. ZERO STABILITY PROBLEM .............. 30
3.1 Cyclic Structure of NQD Automata ........ 35
3. 2. Some Properties of the Cyclic Structure ..... 38
3. 3 Algorithm for Locating Prime Cyclic Tapes . . . 39
3.4 Quasi-Actual Cyclic Conditions. . . . . . . . . . 43
3. 5 Zero Stability Theorem .............. 47
3. 6 Algebraic Structure of NQD Automata ...... 53
IV. ISOLATED CUT POINT PROBLEM ........... 66
4.1. Set Theoretic Approach ........ . ..... 66
4. 2. Topological Approach ............... 74
V6 CONCLUSIONS. 0 o o o o o o o o o o oooooooooo 84
REFERENCES ........ . ............. 87

iii

I. INTR ODUC TION

The concept of a probabilistic automaton has received a
great deal of attention due to its evident relationship with the
reliability of deterministic automata (Rabin [l 3] , 1963). More
recently, the study of neural nets and decision computers has
led to an even greater interest in the behavior of probabilistic
automata (Kilmer and McCulloch [.10] , 1964). Essentially, the
behavior of a probabilistic automaton is characterized by
properties of products of stochastic matrices selected from a
finite set of symbol matrices, and subjected to special start
and st0p conditions.

It is especially important in decision making, that the
behavior of the automaton be stable with respect to small
fluctuations in the entries of the symbol matrices. That is to
say, the behavior of the automaton should not change erratically
under small perturbations of the entries in the symbol matrices.
Chapter 2 and 3 pertain to this stability problem. Chapter 2
establishes the fundamental properties of stochastic matrices
and their products, while reviewing the known stability results.
The "strict" stability problem is solved, which allows any entry
in the symbol matrices to be perturbed. Chapter 3 is concerned
with the restricted zero stability problem, in which the zero
configurations in the symbol matrices are not allowed to be
perturbed. Zero stability results are given in terms of the cyclic

and algebraic structure of probabilistic automata.

Tape acceptance stability and equivalence of deterministic
and probabilistic automata depend on the existence of an isolated
cut point (Rabin [l3] , 1963). Chapter 4 focuses on the existence of
isolated cut points and on tests which decide whether or not a given
cut point is isolated. A bounded algorithm is given which decides

these problems for a large class of automata.

1.1. The Probabilistic Automaton Concept

Rabin, in 1963, gave the first neat definition of a probabilistic
automaton as a generalization of the usual deterministic automaton.
His formulation was essentially as follows. Let Xn be the set

of all (1 x n) stochastic vectors.

Definition 1.1.1.: A probabilistic automaton is a system

 

P = P (S, ”1, no, OF) defined over a finite alphabet Z = {01, 0'2, . . . , 0'02}
where 02 denotes the order of the set 2? and
S = {31, $2, .. ., Sn} is a finite set of states.
no is a (l x n) stochastic row vector called the initial
distribution. Rabin, in 1963, used a single start
state instead of an initial distribution. The former
has been used in the most recent works of A. Paz,
C. Page, and others.
M = {M(<ri) : (Ti 6 Z} is a finite set of n x n stochastic
matrices M(o-i) that define, for each symbol O'i in
the given set E , a mapping from a distribution 11' 6 n

to a distribution Tr M(0'.) E j . Thus ”Z is a set of
1 n

mappings from n x E to n . Frequently M(o-i)

will be called a symbol matrix.
0 is a (n x 1) column output vector with ones
corresponding to the designated final states

F C S and zeros elsewhere.

We denote by 2"< the set of all finite sequences of elements
l from 2 . We call these elements of 2* tapes, and we denote

2N and 2N to be the set of tapes in 2’:< whose lengths are N

and no larger than N respectively. The length q of the tape
x = cri 0i . . . 0'i 6 2’:< is denoted by lg(x) . We also write
1 2. q
= 0'. 0'. . . . 0'. to denote the subtape of x that consists
1 1 1
k h k+l p th
the kt symbol through the p symbol.

The function 7%: Kn x 2 -* jn’ defined for symbols

0-, e 2 , admits a natural extension to m2 X 2* _’ z! ’
1 n 11

xi
of

defined for tapes x = oil O'iz . . . oiq by the matrix product
It M(x) = wM(0'il) M(O'iz) . . . M(O'iq) . Here the null tape A
(lg(A) = 0) is represented by the identity matrix M(A) = I,
and the mapping TT I = TT .

The behavior of probabilistic automata can be viewed as
a stimulus-response relation for a mathematical machine. This
point of view is particularly important in the application of
probabilistic automata to animal and antefactual decision behavior.
The response of a probabilistic automaton )0 to a sequence of
stimuli, x = O'i 0'. . . . cri , is defined by

112 k

rp(x) = no M(O'i) M(O'i) ... M(O'i) O

1 2 k F

4

The response rp(x) of p to a tape x is the probability of
entering into a final state upon the application of tape x to
when )0 is started with the initial distribution no. We shall
often refer to rp(x) as a "response point". Thus we see that
the response of a probabilistic automaton is characterized by
products of stochastic matrices selected from the symbol matrices
together with special start and stop conditions, nO and CF
respectively.

The tape acceptance behavior of a probabilistic automaton

is defined in terms of a cut point 0 i X _<_ l . For a given cut

point X , the system ([0, X) is said to accept the set of tapes

NAM.
T()09 A) : {X:XEE*9 rp(x)> A}

and reject the rest, all with respect to the cut point X . A cut
point X is said to be isolated if, for every x 6 2* and some

Y) 0, either rp(x)> X +y or rp(x)< x -y,

Definition 1.1. 2.: A cut point 0 E X i 1 is called isolated iff for

 

some fixed y > o, Irp(x) - xl > y for all xe 2*. We shall
often refer to a y -isolated cut point to signify that we have a
particular fixed y in mind.

Rabin showed that probabilistic automata with isolated cut
points accept only those sets of tapes that are definable by finite
state deterministic automata. Thus probabilistic automata with
isolated cut points have the same tape discrimination power as

finite state deterministic automata. A probabilistic automaton,

however, may have vastly fewer states than any corresponding

deterministic automaton accepting the same set of tapes.

II. GENERAL STABILITY PROBLEM

This chapter launches our attack on the stability problem
and cffers a review of the known stability results. We discuss
three different types of stability that are of interest in probabilistic
automata theory. The first type, defined without reference to a
cut point, is strictly concerned with the asymptotic behavior of
long products of stochastic matrices. The second type, defined
in terms of a cut point, is concerned with the tape acceptance
behavior of probabilistic automata. The third type, called zero
stability and discussed in chapter three, concerns the asymptotic
behavior of long products of stochastic matrices whose entries
are subjected to perturbations which do not alter any matrix
zero configuration. We shall define these stability concepts

precisely below.

2.1. Stability Concepts

The stability concepts introduced here pertain to the Rabin
probabilistic automaton P(S, 7”, no, OF) defined in Section 1.1.
Stability problems arise when one considers the behavior of a
probabilistic automaton under small perturbations of the entries
in its symbol matrices M(o'i), 0'16 2 . Only those perturbations
which have the perturbed symbol matrices stochastic are allowed.
We shall denote the perturbation of [0(8, m, no, OF) by

FMS, M', no, OF). That is, P' is a system p'(S, ”I", no, OF)

in which the entries of each symbol matrix M'(0'i), 0'16 )3 ,

are formed by perturbing the entries of M(O’i), 0'16 2 , by
arbitrary small quantities that leave the row sums one.
Let I Bl denote the absolute value of the

maximum entry in B .

Definition 2.1. l. : An automaton [0(5, m, no, OF) is strictly

 

stable (denoted s-stable) iff given any 6 > 0 there exists

6(6) > 0 such that the inequalities
- l <
[M(O'i) M(o-i)l a v 6162
imply

lM(x)-M'(x)l <6 V X62*

Definition 2.. l. 2. : An automaton p(S,)I)( , no, OF) with cut point

 

X is tape -acceptance stable (denoted a-stable) iff there exists a

6 > 0 such that the inequalities
- t <
[M(O'i) M (oi)! 5 3.: oi e 2
imply

Tho. X) = TW'. M.

In other words, a probabilistic automaton with cut point
X is a-stable if its accepted tape set is not changed by sufficiently

small perturbations of its symbol matrices.

Definition 2.1. 3.: An automaton p(S, m, no, OF) is zero
stable (denoted o-stable)iff given any 6 > 0 there exists a

6(6) > 0 such that the two conditions

1) lei) -M'(0'i)) < 6 , 1.: 0-162: ,

2) no perturbation is allowed to change the
zero entry configuration in any M(cri), 0'1 6 2 ,

imply the inequalities
IM(x)-M'(x)l < e VX62*.

The following simple example illustrates these concepts

by showing the difference between o-stability and s-stability.

Example 2.1.1.: We consider an automaton that is, l) o-stable,

 

2) not s-stable, and 3) for O < X < 1/2 not a-stable. Define
P(S, m, 31' $2) with cut point 0 < X < 1/2 over the single
symbol alphabet 2 = {O} . Let the state set be S = {51, $2} ,

and let

 

 

1) First note that [013 o-stable, since )0 = l0 when
no zero entries are altered.

2) Next, we shall prove that p is s-unstable. We show
that a perturbation for which 0 < 6 < 1 will introduce a significant
change in the asymptotic behavior of Mk(0). Consider the perturbed

system P' with transition matrix

81 S.2
F. ..
51 1-6 6
M'(0) =
s. 6 1-6
2 L. .1

 

 

3k
where O < 6 < 1. For the tape x = 0k 6 2 , the perturbed matrix

productis

M'(x) = M'(O )2

 

 

The matrix M'(O) can be written in terms of its constituent matrices

 

 

 

 

as
M'(O) 2 U1 + (1 - 2.6)UZ
where
_1_ _1._ F}. .1.—
2 2 2 " 2
U1 = and U2 =
1_ I. I. 1
Z Z '2 Z
. Z 2 . .
Since U = U , U = U and U U = O, we see by induction that
l 1 2 Z 1 Z
M’(Ok) = U1+(1 - 2 mkuz.

Now (1 - 2 6)k - O as k increases: thus, given any positive

A

6 there exists a finite integer K(6,6) (any integer

l.
2
K 3 6/6(1-26) will do) such that

K.

K. , !
lino )-NPW n K]

IUZI-[1-<1-26>
(2.1.1)

z l[1-(1-25)K] >e

Hence it follows that 7p is s-unstable.
3) Finally, for any cut point X, 0 < X < :— we have

T(P, X) = <1) . The set T()0',X) is not null, however, since

10

given any 6 > 0 there exists by equation (2.1.1) a finite integer
K(6,X) such that rp ,(OK) > X and rr’omK) = 0 < X . Hence

P

P is a-unstable.

Z. 2. Stochastic Matrices and Their Products
In this section, we summarize some fundamental results

concerning stochastic matrices and their products.

Definition 2. 2.1.: The (n x 1) column vector with all 1 entries

 

is denoted Is and called the "summing vector.”

Definition 2.. 2. 2.: A square matrix A is a stochastic matrix iff

 

 

it has nonnegative entries and unit row sums.

o The nonnegative (positive) entry condition is written
A _>_ 0 (A > O).

o The unit row sum condition is written A IS = IS

Lemma 2. 2.1.: If A and B are two (n x n) stochastic matrices)

 

then the product C = AB is again a stochastic matrix.

Proof: The nonnegative conditions A_>_O and B_>_O imply

n
C : > >
m. k21a1,kbk,j _o, C_O.

The unit row sum conditions AIS 2 IS and BIS : IS imply

C°I =A(BI)=AI :1
S S S 5

Lemma 2. 2. 2.: The eigenvalues XI of a (n- x n) stochastic matrix

A satisfy (Xi) _<_ 1.

11

Proof: If X is any eigenvalue of A with corresponding eigenvector
x then Ax : Xx . Let xi be the component of the largest modulus

of x. Now consider the modulus of the 1th row of Xx : Ax,

n n
IXx.) = | 2: a. .x.l < .2: a. .lx.l = Ix.|,
1 =1 1,3 J —J=l 1.1 1

which implies [XI _<_ 1.

Lemma 2. 2.3.: Any (11 x n) stochastic matrix A has at least one

 

unit eigenvalue with corresponding eigenvector IS .

This result is an immediate consequence of the unit row

sum condition, A IS : IS

Definition 2. 2. 3.: An (n x n) stochastic matrix A is scrambling

iff A AT > O . Equivalently, a stochastic matrix A is scrambling

 

iff every pair of rows (i, r) of A has a corresponding column j

suchthat a. .> 0 and a .> O.
1] I'J

9 i

Let H CH denote the maximum difference

IC..-C .I foralli,r,j.
1,3 1‘,J

Theorem 2. 2.1.: (Equivalent to a theorem of Paz [12]). If A and

 

B are (n x n) stochastic scrambling matrices, then H A H _<_ (1 - amin) H B”

where amin is the minimal nonzero entry in A .

Proof: For an arbitrary fixed leet i and r be the integers that
represent the particular two rows of A that generate the jth column

norm H (A B) j” . Then we have

3

”(A 3).,3” = Ik:21 (a ,k bk,j - ar,k bkull
r.
z I 13191.1( ‘ ar,k) bk,j|

Let K and K be the sets of indices k such that ai,k Z ar,k and
ai,k < ar,k respectively. Define

2+:k§K(ai.k-ar.k) 30 and 2':-k€2R_(a1,k-ar,k)20
The unit row sum condition implies that

2+ = 2"

The quantity 2+ satisfies the condition

2+ : REK (ai,k - ar,k".:1 - kEK a‘r,k -k€z-Kai,k-<- l- 3'min

since the scrambling condition insures that at least one term within

the sums must be positive. Finally, we conclude that

II(A' B). .H ~ b .+ z (a.

" kK i,k “131319; )b

l
m M
m
l

k,j|

keK "k - ar'k
_<_ ligani ‘“ agribinax -kzg-K—-(ar,k ‘ 511,19 bininl
E 2+“ HE” E (1‘ 3mm?" NB”

This completes the proof.
The stronger inequality HA ° BH 5 ”All - ”B“ might be

conjectured, but is not satisfied by the two matrices

l3

 

(’1 1 1 " F _
2— 71’ o 1 o o o
o i % .3; 1 0 0 o
A = , B :
1 1 1 3 1
z ‘2’ z 0 z z 0 0
1 1 1 3 1
_0 z ‘2: z_ _‘21' '21: 0 0g

 

 

 

Lemma 2. 2. 4.: If A is an (n x n) stochastic matrix and B is any

 

(nxn) matrix, then |AB - 8| E ”B“ .

Proof: We let [3 be an (n x 1) column vector defined as [3T 2

(61, 62, . . . ,fin) and show that |AB - (3| 5 “B” . Let i denote a
row which yields |AB - [3| , the largest absolute value among the

entries of AB - [3 . Then we see that

n n n
lAfl -f3l = |k§1a1,k5k’51|=|k§1ai.kBk-pik2=31aitkl
n \ n
: lkEl (6k ' gifa’i’kl: kEI IBk - fill ailk
n
:1pr 2 k = “B”

k=l 1.
Since the column vector [3 can be chosen at will, we conclude that

IAB - Bl 5 ”BH-

Lemma 2. 2. 5.: A (n x n) scrambling stochastic matrix A has

 

exactly one eigenvalue with unit modulus: X1 — l .

Proof: Since A is scrambling, we know by Theorem 2. 2. 1 that
m . .
“A H < (1 - a . ) where a . is the smallest nonzero entry in
— mm min
A. Thus lim ”Am“ :2 0 and hence U = lim Am is a stochastic
m"00 l m—wo

idempotent matrix with identical rows. Consequently, the only

l4

nonzero eigenvalue of U1 is X1 = l. The eigenvalues of Am are
Xin(i = 1, Z, . . . ,n) where Xi are the eigenvalues of A. Thus, A

has precisely one eigenvalue with unit modulus.
This result can be strengthened by introducing a more liberal
scrambling condition.
Wolfowitz [l 6] proved that if A is scrambling,
0 so are AB and BA, fcr stochastic matrices

A, B.

Definition 2. 2. 4.: A (n x n) stochastic matrix is said to be eventually

 

scrambling (denoted e-scrambling) iff there exists an integer e such

e . . ,
that A is a scrambling matrix.

Theorem 2. 2. 2.: A (n x n) stochastic matrix A is e-scrambling

 

iff A has precisely one eigenvalue, X1 = 1, with unit modulus.

Proof: a) If A is e-scrambling, then by Theorem 2. 2.1, it follows
that 11mm ”Am” = O . Arguments Similar to those used in Lemma
ma

2. 2. 5 prove that A has precisely one unit modulus eigenvalue,

b)- If A has only one unit modulus eigenvalue, X1 = 1, then

[Xi I < l for i = 2, 3, . . . , :2. This implies that the stochastic

. 0 m ' .9 ll
idempotent U1 =- 11m A has only one unit eigenvalue and (n - 1)
III—"30

zero eigenvalues. Thus U1 has rank 1. We observe that any

stochastic matrix with two non-identical rows has rank at least two.
T . . T .
Consequently, U = I - u has identical rows 11 and 11m “Am“ = 0 .
1 S m->oo
This implies that A is e-scrambling, since there exists a bound B

(namely 11) such that if Am is scrambling for any m > B, then

 

15

AB is also scrambling.

Definition 2. 2. 5.: A square matrix A, labeled by states, is said to
be reducible iff there exists a relabeling of the states so that the

rearranged matrix Ar has the form

where Pr is a square matrix. Otherwise A is called irreducible.

Definition 2. 2. 6.: A square matrix A is said to be partially
v-decomposable iff there exists a relabeling of the states so that

the rearranged matrix Ar has the block form

  

 

 

 

 

 

 

_Swi S(1) 5(2) s<v1_
5(0) T o”) 0(2) . . . QM
5(1)
S<2)
A :
r
51v) PM
._ .J
where P“) (i=1, 2, ..., v) are square matrices. If the set

S10) is null, then the matrix A is said to be v-decomposable.

 

Theorem 2. 2. 3. : (Perron-Frober.ius) I If A is any nonnegative
irreducible square matrix, then:
1) there exists a real positive eigenvalue XI of A such

that, if X is any other eigenvalue of A then

16

”I 5. X1 ;
2) minimal row sum < X1 < maximal row sum, where neither

equality holds unless the row sums of A are equal;

3) there exists a real positive eigenvector X1 > 0 such that

A X1 = X1 X1 ;
4) X1 increases when any entry in A increases; and
5) X1 is a simple root.

This result was also proved by G.Ibbrew and I. N. Herstein [ 6 ]
using Brouwer's fixed point theorem. However, their proof does not

give a constructive method for determining X1 .

Proof: We shall first prove parts 1), 2), 3), and 4) by showing that

 

there exists a sequence of diagonal similarity transformations whose
limit transforms A into a matrix with equal positive row sums.
The approach taken gives a constructure procedure for determining

X The essential features of the approach can be clarified by means

1 .
of a simple example.

Example: Consider the nonnegative irreducible matrix A:

F3 4 o- 777
A = o o 5 , AIS = 5
3 4 4 11
L. _ L J

 

 

 

 

We shall apply successive diagonal similarity transformations
that modify the rows with maximal or minimal row sum, so as to
increase the minimal row sum and/or decrease the maximal row

sum. First, since the third row has the maximum row sum 11 ,

17

we transform A by a diagonal matrix D1 = diag {1, 1, d1} and

obtain
F3 4 o -
_ -1 _
Al—Dl ADl— o o 5d1
3/d1 4/d1 4

 

 

We now choose (11 > O to satisfy the inequalities

5<5d1<11 ,or l<d1<1l/5

5<4+7/d1<11, or 1<d1<7

so as to obtain a smaller maximum row sum. We choose d1 = 2,

whence
(Row Sum)
V 3 4 o R (7‘;
A1 = o o 10 (10)
3 Z Z 4 '7. 5‘
L/ _J 1 ,

 

 

Next, we transform A1 by a diagonal matrix

D = diag {1, d7, 1} and. obtain

2
r- _
3 46.2 o
-1
A2 = D2 A1 DZ :. o 0 10/d2
_3/2 2d, 4 _J

 

 

We now choose (17 > O to satis-y the inequalities
‘—

7<3+4d2<10 o

7 < 10/d2 < 10 1< d2 < 10/4

’1

1<d,<7/4

O
r

7<5.5+2d,<10 or 3/4<d2<9/4

18

so as to obtain a smaller maximum row sum. With the judicious choice

(12 = 5/4, we get a similar matrix A with equal row sums.

 

 

2
”'3 5 0' (8;
A2 = 0 o 8 (8)
L3/2 5/2 4— (8)

Consequently, A has a positive real eigenvalue X1 = 8 . Clearly, the
matrix (1/8)AZ is stochastic. If X is any other eigenvalue of A2
with eigenvector Y then AZ Y = X Y . Dividing by X1 = 8 we get
(1/8)Az Y = (X/8) Y. By Lemma 2. 2. 2, the modulus of any eigenvalue
of a stochastic matrix cannot exceed one. Consequently, [X I: 8 for
any eigenvalue X of A.

We now return to the proof of the theorem at hand. First, we
establish a sequence of diagonal similarity transformations,
D? A. D. = 4..

1 (i=0,l,...) where AozA, so that

{133 ”Ai 15H -’ O . We shall alternately operate on the maximal and
minimal rcw sums. Thus for i even (2'. odd) we will operate on
the maximal (minimal) row sums. Denote the rows with maximal,

. . . . . + o — .
intermediate and minimal row sums n K K and K res ectivel .
9 9

Define the dia~cna1 matrices D, 2 dis. 1 d
5 .

for i even as

 

Q‘A
H
I I
0..
\l
H
r.
1 *1
La
m
'X
.1.

othe rwi s e , and

0..
(_a. f”\ La.
1' "
v
H
H

for i odd as

 

o < dii)
J

dii)
J

19

if

jeK'

othe rwi se .

Now to prove that at eac'. step di > O can be chosen so that

lim ”A. I H =
1 s

I‘M!)

O , we note that at each step the matrix D'ilA.1 Di = Ai+

can be relabeled so that the relabeled matrix Ai

 

 

for i even:
K+
A? = K0
1+1
Kf
for i odd:
K+
.r o
A1+1 ' K
K-

 

K+
A11
d1A21
_d1A31
K+
A11
A21
. I s.
‘1/ di’ A31
L.

 

1

has the form

 

K0 K‘
(i/diA (1/d)A T
1"12 1 13
A22 A23 and,
A32 A33 a
K0 K“
A1.2 diAl3
A22. diA23
/ 1.
(l/di’ A32. A33

 

The irreducible condition implies for even i that di > O can be chosen

so that;

l) at least one of the maximal row sums will be decreased,

2) at least one of the row sums in KO U K- will be increased.

Similarily, for i odd we can snocse d > 0 so that; l) at least one

of the minimal row sums will be increased,

1

2.) at least one or the

row sums in K+ U K0 will be decreased. Consequently, as the

 

in:

20

process is repeated, all the row sums will tend toward a common

positive row sum X The quantity X lies between the minimal

1' l

and maximal row sums, but is equal to either only when both are

equal.
Consider a sequence of diagonal similarity transformations
such that
. -l
III-1.1;: "(D0 D1 D2... Dn) A(Do Dl DZ'” Dn)Is”
= ”D’l ADI H = o
s

This simply states that the row sums of Q = D.1 A D have equal

values X1. Thus, this matrix Q similar to A satisfies
Q I8 = XI I8 , so X1 is an eigenvalue of A. Now (l/Xl) Q is
a stochastic matrix. If X is any other eigenvalue of Q with

eigenvector Y then Q Y = X Y . Dividing by X we get

1
(l/Xl) Q Y = (x/xl) Y. By Lemma 2.2. 2, the modulus of any
eigenvalue of a stochastic matrix can not exceed one. Consequently,
|X| 5X1 for any eigenvalue X of A.

To prove that there exists a positive eigenvector corresponding

1

to X , we note that D- A D Is = XI I!3 where D > 0 . Consequently

1

X1 = D I8 > 0 is a positive eigenvector of A corresponding to X1.
To prove that Xl increases when any element in A is

increased, one needs only to observe that a row sum of D"1 A D

increases when any entry in A increases. This completes the

proof of parts 1), 2), 3), and 4).

To prove that X1 is a simple root of D(X) = det [IX - A] note

by [7-].that D'(X) = tr({B(X)) where B(X) denotes the adjoint of (IX - A).

21

Let Ci be the (n - 1) x (n - 1) submatrix obtained from A by deleting
the ith row and column. Then we know from the adjoint definition

that

D'(X) = tr (130)) =

M Mr:

det (X I - Ci)

By 4) it is clear that det (XI - Ci) > O for X _>_ X Consequently,

1.

D' (X) > O for X Z X which proves X is a simple root of

1 1
det (I X — A). This completes the proof of the theorem.

The next theorem shows the relationship between the number

of unit eigenvalues and the structure of a stochastic matrix.

Theorem 2.2.4.: A (nxn) stochastic matrix A has v unit eigen-

 

values iff A is partially v-decomposable.

Proof: a) (Sufficiency) We prove that if A has v unit eigenvalues
then A is partially v—decomposable. First, we perform a suitable
relabeling of the states such that A has the block upper triangular

form

P
All A12 ' ° ° Aln

A22 . . . 2n

 

 

L ‘ Anna

 

 

where the square matrices Aii are irreducible. Clearly any
eigenvalue of A must be an eigenvalue of some Aii and vice-versa.
Conclusion 4 of Theorem 2. 2. 3 proves that, if Aii has a unit

modulus eigenvalue, then All = O for j = i + l, . . . , n, since the

22

eigenvalues of any stochastic matrices have. modulus no larger than
one. Consequently, Aii is a stochastic irreducible matrix with
only one unit eigenvalue. Thus, if A has v—unit eigenvalues, then
A is partially v-decomposable.
b) The proof of necessity follows trivially from Lemma 2. 2. 3.
This result can be extended to nonnegative square matrices
with row sums no larger than one. Such matrices we shall call

substochastic.

Theorem 2.2.5.: A (nxn) substochastic matrix A has v unit

 

eigenvalues iii A is partially v-decomposable.
The proof follows immediately from Theorem 2. 2. 4, by
observing that a substochastic matrix A can be imbedded into a

A
stochastic matrix A by adjoining one additional state as shown below:

r I
I d1
|
'dZI
A | .‘
I i
I f
Id i
n;
_______ I—_-.T
o o ' 1 l
... l ...:

 

where the d's are chosen to produce unit row sums.

2. 3. Strict Stability
The results obtained in this section are sufficient to solve

the strict stability problem for an arbitrary probabilistic automaton.

)1

lr—1

IF]

(I)

[*0

23

We shall prove that the quasi-definite condition is both necessary and
sufficient for strict stability. An efficient algorithm will be given in
Chapter 3 to decide whether or not a given probabilistic automaton is
quasi-definite. First the quasi-definite condition is defined as a

non-trivial generalization of Rabin's actual automaton.

Definition 2. 3.1.: A probabilistic automaton 70(8, )h, no, OF) is

 

called Miff the symbol matrices M(iri) , (Ti 6 2 contain no
zero entries.

Rabin proved that all actual probabilistic automata have the
property that given any 6 > 0 there exists an integer N(e) such
that the inequality lg(x) Z N, x 6 2* , implies “M(x)“ < e .

This result follows immediately from Theorem 2. 2. 1, since the
actual condition clearly implies that all the symbol matrices are
scrambling. A class of automata that includes these actual automata

will be called quasi-definite automata, following A. Paz.

Definition 2. 3. 2.: A probabilistic automaton F(S,/}l , no, 01:.)

 

is called quasi-definite iff given 6 > O , there exists an integer N(€)

 

such that the inequality lg(x) _>_ N, x e 2* , implies ”M(x) n < e .

Theorem 2. 3.1.: A probabilistic automaton [0(8, ”1, no, OF) is

 

s-stable iff it is quasi-definite.

Proof: 3.) (Sufficiency) We shall prove, for any tape x e 2* , that
[M(x) - M'(x)| < e if the perturbations of the symbol matrices are
made sufficiently small. If I0 is quasi-definite, there exists an

integer N(€) such that 1g(x)_>_N, x e 2* implies ”M(x)” < 6/4 .

24

We now consider any tape x e 2* . If lg(x) E N, then we clearly can
choose our perturbations sufficiently small that lg(x) E N implies

|M(x) - M'(x)| < 6/8 < e . If lg(x) > N, then we partition x so that
x = y z
where lg(z) = N. Now consider
|M(x) - M'ixil = |M(y)M<z> - M'<y)M'(z>|
from which we get
|M(X‘2 - M'(X)| = I(M(y) M(z) - M(z))
- (M'(Y§=M'(Z) - M'(Z)) + M(Z) - M'(Z))I
by adding and subtracting terms. The triangle inequality yields
|M<x> - M'<x>| 5 |M<y>M<z) - M(z)| + IM'<y)M'<z) - mm
+ [M(z) - M'(z)|
Applying Lemma 2. 2. 4, we get

|M(x) - M'(x)| _<_ ”M(z) + ||M'(z)|| + (M(z) - M'(z)|

 

 

We note that
llM'(Z)|| E IIM'izlll t Z |M(Z) - M'izll

by observing the entry in M(z) which produces ”M(z) || . Hence, we

conclude that there exist sufficiently small perturbations to imply
|M(x) — M'(x)| 5 e/4 + s/z + s/8 = 7/8 6 < e

for all x 6 23* . This completes the sufficiency portion of the proof.

25

b) (Necessity) We now show that if ’0 is not quasi-definite,
then [0 is s-unstable. If P is not quasi-definite, there exists a
fixed y > O and an unbounded sequence of tapes {Xi} where
lg(xi) 2' i such that for all i, “M(xi) H > y . Clearly we can
perturb )0 with arbitrarily small nonzero quantities so that the
perturbed system P' is quasi-definite. This implies that for
e > 0 there exists an integer N(€) such that the condition
lg(x) 3N, x e 2* implies ||M'(x)|| < e . Hence .1333 ||M'(xi)“ = o ,
and consequently 11—?ch |M(Xi) - M'(xi)| Z y/Z , so P is s-unstable.
Paz introduced a necessary and sufficient condition for
quasi-definite automata by his H -condition, decidable by a bounded

4

experiment.

Definition 2. 3. 3.: A probabilistic automaton is said to satisfy the

 

H4-condition iff there exists an integer k such that lg(x) _>_k, x e 2* ,

implies that M(x) is scrambling.

 

Theorem 2. 3. 2.:: A probabilistic automaton is quasi-definite iff it

 

satisfies the H4-condition.

m: a) (Necessity) If a probabilistic automaton is quasi-definite
then for e > 0 there exists an integer N(e) such that “M(x)“ < e
for all x e 23* with lg(x) _>_ N. This simply means that the rows of
M(x) become nearly identical whenever lg(x) Z N, which in turn
clearly implies the scrambling condition.

b) (Sufficiency) If a probabilistic automaton satisfies the
H4—condition, then there exists an integer N such that lg(x) _>_ N

implies M(x) is scrambling. Define y > O to be the minimal

26

nonzero entry in {M(y)| y 6 EN} . Now select the minimal integer
B such that (1 - y)B < e . Let x be any tape in 23* with

1g(x)2_ BN . Partition x into "prime" scrambling tapes zi such
that the matrices M(zi) are scrambling and no zi has a scrambling

subtape;

3...zn, (nZB).

The H4-condition insures that lg(zi) E N . Now apply Theorem 2. 2. l

on the subtapes 21 to get

“M(x)” 5(1-v)n 5 <1 -.>B < e

Paz proved [12] that the H4-condition can be decided with a
bounded experiment. This result will be obtained easily from the
cyclic structure developed in the next chapter. Also, at that time,

an efficient algorithm will be given to decide the quasi-definite

condition.

2. 4. Acceptance Stability

We shall give here some sufficient conditions for tape
acceptance stability expressed in terms of an isolated cut point.
A cut point X is y-isolated if the response of tape x satisfies
|rp(x) - X | _>_ y > O for all x e 22* . The a-stability differs
from s-stability by the fact that a-stability will tolerate the
instability of the response points as long as they do not cross
the cut point, but will not tolerate the crossing of the cut point by

a response point.

27

Theorem 2. 4.1.: If an automaton [0 is s-stable and X is an isolated

 

cut point, then the system (p, X) is a-stable.

P_r_o_o£: Let X be a y-isolated cut point, i. e. , |rp(x) - X | _>_ y for all

x e 2* . By Theorem 2. 3. l, for e >. O we can choose the perturbations
sufficiently small so that [M(x) - M'(x)| < e = v/n where n is the
number of states in p . Let x be any tape in 2* and consider the

change in the acceptance resulting from these perturbations:

I170 M(x) OF - 170 M'(x) 0

|rp(x) - rp'<x)| F|

lTrO(M(x) - M'(x))0 5 ne = y.

F I

This proves that x e T(p,X) “* x e T()0', X) since no response
point can cross the y-isolated cut point X .
Our next result is a regional stability theorem that does not
require the automaton to be strictly stable in order to be a-stable.
That is to say, we will tolerate instability of response points as long
as they do not cross the cut point. Let us consider a probabilistic
automaton P (8,}?1, no, 01:.) defined over the alphabet 2 ={1, 2, . . . , o2} and
S = {1, 2, . . . , b5} where F C S represents the set of designated
final states, and O the column vector with entries 1 for the final

F

states and O elsewhere. Define the response intervals, Ri’ as

R.= 2 Ai, 2 vi 0 0,1 2.4.1
,[jeFJjeFJ][] ()

for each is 2 where

A; = min {M(i)k’j}
and

i __ .

Vj " mix { M(1)k, j}

28

Theorem 2. 4. 2.: A probabilistic automaton K(S, m, 110,0!) with

 

cut point X is a-stable if X { 'UZ Ri for perturbations less than
16

5.

6 : rnin {IX -Ril} /OF
16

Proof: Let x be any tape in 23°< written in factored form x = y k
where k e 2 is the last symbol of tape x. Consider the unperturbed

and perturbed responses of the automaton to the tape x,

rp(x) = no M(y) M(k) OF (unperturbed)
and

rp'(x) : Tro M’(y) M'(k) OF (perturbed) .

Let p =[p1 p‘2 pm] and q = [q1 q2 qn] be two stochastic
row vectors. Now if 6 is the maximum perturbation allowed, i. e. ,
[M(i) - M'(i)) _<_ 6 for all i E 2 , then we have

2 Ai‘:[plp2...p]M(k)oF:2 VI.‘

jeF J n jeF J
and

k 0 k 0
z A-6- F<[q q ...q]M'(k)0 <2V.+6- F
j€FJ — 1 2 I1 F—jEF

Consequently, if the cut point X ,E’ U R then no response point will

162
cross the cut point for perturbations less than

i

ézm'n X-R.} OF
162 {I ll /

We now give a simple example to illustrate how this result can
be used to yield a-stability results when the automaton is not quasi-

definite.

29

Example: Consider an automaton (0 with cut point X = 1/2
defined over the alphabet z: = { 1, 2} and state set s = {1, 2, 3, 4}
where so = l is the initial state and F = {1, 4} are the designated

final states. The given transition matrices are

1 2 3 4 1 2 3
1 "o 1 o o— 1 :7 o o
2 ,15— ; o o 2 0 lg o
M(l) = M(Z) = 1 1
3 O O l 0 3 '1—6' 0 l—O-
4 1
4 _o o 5 i 4 _ o o o

 

 

 

_ _Z_ _ :1.
R1 - [09 5 l 9 R2 - [ 5 a l ] 0
Now X :12 f [0, %] U [g, l ] . Thus, the theorem implies )0
is a-stable for all perturbations less than 6 = -l— .

0

v- oils: oils: O‘IU‘I .1;
l

l_

 

III. ZERO STABILITY PROBLEM

The o-stability problem comes up when one considers the
stability of probabilistic automata subjected to small perturbations
of the nonzero entries of the symbol matrices. The o-stability
problem arises only in nonquasi-definite automata, henceforth
denoted NQD automata, since quasi-definite automata are s-stable
even under perturbations of zero entries (Theorem 2. 3.1). Rabin
conjectured that all NQD automata were o-stable, but H. Kesten
produced a neat counter example. A slight modification of this

example is given below to initiate our study of the problem.

Kesten's Counter Example
Define the NQD probabilistic automaton K(S, 7V , 81’ 82)

over the alphabet 2 = {0, l} and on the state set S = {$1, 82’

 

 

 

s3, 34} by the transition matrices,
s1 82 s3 s4 s1 82 s3 s4
s1 r—p l-p 0 0 s1 (_0 0 l —
s2 0 1 0 0 s2 1 0 0 0
M(O) : s o o q l-q ' M“) : 1 o o o
3 3
s4 _0 0 0 l _- 34 L0 0 1 0—
By induction on n, it is clear that
F n n _
p l-p 0 0
n n 0 I 0 0
M(O ) = M (0) = n n
0 0 q l-q
O 0 0 l
L—- .—

 

 

30

 

31

and
l-pn 0 pH 0.-1
n n 1 0 0 0
M(01)=M(0)M(l): n n
q 0 l-q 0
O 0 1 CU

 

 

is
T k

H-pn 0 pn 0

l 0 O 0

M(x) = n n

q 0 l-q 0

0 0 1 0
L... .—

 

 

Since the states 51 and 5 form a recurrent set with respect to tape

3

x = (Onl)k, we consider them separately and determine their limiting

behavior as k-'00 . The matrix corresponding to states 51 and s3

is denoted by A and is given by

S1 52
n n
51 l-p p
A:
n l- n
52 q C]

The behavior of the limit Q = LimcJo Ak can easily be determined by

expanding A in terms of its constituent matrices as

n n
A=Ul+(l-p -q)UZ

where on = qn/(pn + qn) and

32

C:
II
C
II
H
I
C‘,

Since U: = U1, we have U1 U2 = 0 and U; = U2 . By induction

k
Ak=U1+(1-pn-qn) UZ

Thus lim Akz UI for O < p, q< 1. Consequently, if we choose

k—.<D

p = q in the unperturbed system then we have

 

 

F1. 1:
2 2
lim A =
...... 1. 1.
_2 21 .

Now let us perturb the nonzero entry q to be q = p - 6 where the
quantity 6 > 0 can be made arbitrarily small. In this case, the

perturbed limiting behavior is given by

lim A'k =
k-ooo a' 1 -o.'
n n

where a; = (p - 6)n/(pr1 + (p - 6)n) . Now the quantity (1; can be

made arbitrarily small by choosing n sufficiently large. Consequently,
given any 6 > 0 and for any 0 < e < %- , there exist integers K

and N such that for tape x = (0N1)K€ 2* we have

|M<x> -M'(x>l = (lg-agw 6

Hence, the NQD automaton K is indeed o-unstable.

33

The basic idea in this example can be seen by referring to

the state diagram of K shown below:

 

 

 

 

depletion depletion
state state

l-p l-q
storage storage
state state

 

where_ and — denote 0 and 1 (transitions respectively.
The transition matrix for tape x = 0 is 2-decomposable so
that there are two disjoint subsets of states 8(1) = {31, $2} and
8(2) = {S3, 84} contained in S that are recurrent with respect to
tape x = 0 . Tapes whose transition matrices possess two or more
disjoint recurrent subsets are called cycling tapes. The cycling
tape x = Or1 is used in the counter example to reduce the probability
of being in states 31 and 33 to arbitrarily small quantities pn

and q11 respectively. Then, the dump tape y =1 interchanges the

probability of being in states 31 and s3 , and dumps all the probability

in $2 and 34 back into 51 and s3 . Now if p = q there is no net
transfer of probability between subsets 5(1) and 5(2) . If q = p - 6,
6 > 0, however, there is a net transfer of probability from 5(1) to

34

5(2) . It is quite clear that if the process is repeated enough times

for a given 6 > 0 and with a sufficiently large n, essentially all

the probability gets transferred to 5(2) . This causes the o-instability.
The tape x = (on1)2k which revealed the o-instability can be

partitioned into ”scrambling" subtapes z = (Onl)z with scrambling

matrix M(z) as follows:

x: 2]": 9)“1)‘Z (0“1)‘Z (0"1)2 (0“1)2
This leads us to the important question; what mathematical condition
is sufficient to block the quasi-definiteness used in Theorem 2. 3. l to
prove stability? Clearly, we can write x = y 2k and apply the same

arguments used in the proof of Theorem 2. 3. l to obtain

|M(x) - M'(x)| 5 “M(zk)“ + u M'(zk) 1| + [M(zk) - M'(zk)| .

n1) is

. . . n
However, the minimal nonzero entry an in M(z) = M(O 1 0
not bounded away from zero as n increases. Hence, we cannot use

Theorem 2. 2. l on the subtapes z to select an integer K to insure

that

“M(zK)” E (l -an)K§ e for O< e<l

For, assume that one such bound K is found. Clearly, one can
choose n sufficiently large for 0 < p, q < 1 so that

(1 — an)K > e , which leads to a contradiction. Thus, we see that
the behavior of the minimal nonzero entry attained prior to the
scrambling condition plays a fundamental role in zero-stability

analysis.

35

3.1. Cyclic Structure of NQD Automata
Let G) be a NQD automaton defined over the alphabet

2 = {01, 0'2, ..., 0'02} andonthe state set S: {31, 32’ ..., s } .

n

We now generalize certain notions of a single Markov matrix to apply

to our finite family of such matrices. We denote a subset of S by

5(1)

where i is an integer.

 

We say that a state SJ is accessible from state Si by tape
x e 2* , and write x( Si) -' ‘Sj , if the (i, j) entry in the transition
matrix M(x) is nonzero. More generally, we write x(S(i)) = 53:)
to denote the set of states in S that are accessible from the states
in S(i)C S by tape x . If for a tape x , x(S(i)) = sS’c S”), then
5(1) is mapped by x i_nt_o_ S”) , and we denote this by x(S(i)) -* SO) .
An 23%. mapping is denoted by "-*-'" .
(1)

Definition 3.1.1.: A set of states S C S is said to be recurrent with

 

respect to the tape x iff 8:)C 5(1) .

Definition 3.1. 2.: A tape x e 2”< is said to be a cycling tape iff there

 

 

exist two or more disjoint subsets of states in S that are recurrent

with respect to x. Each recurrent subset is called a cyclic class.

 

Definition 3.1. 3.: A tape x 6 2* is said to satisfy the cyclic condition

 

 

C(x; 3(1) , 8(2), . . . , 8(0) iff x is a cycling tape of the cyclic classes

t .
8(1), 5(2), ., S“). If, in addition, U 5(1) 2 S, then the cyclic

i=1
condition is said to be completely t-decomposable (denoted by

Clix; 3(1), 5(2), 3“)”.

Clearly, if a tape x e 2* satisfies the cyclic condition

 

C(x; 3(1), 5(2), . . . , S(t)) then the transition matrix M(x) is partially

36

t-decomposable. Consequently, Theorem 2. 2. 4 implies that the matrix
M(x) has precisely t unit eigenvalues. Thus, we see the close
relationship between the cyclic structure and the number of unit
eigenvalues. It is important to note at this point that C(x; 8(1),
8(2), . . ., S(t)) implies only that x(S(i)) -* 5(1) for i = l, 2, . . ., t;
and it does not imply that x(S(i)) -’ S“) where S“) is the complement
of 8(1) in S . The transition matrix corresponding to a cycling

tape x that satisfies C(x; 5(1), 5(2), ..., S(t)) has the form

Sm

I-I —

5(0) T(o) Tm Tm Tm

S(1) PM)
5(2) Pm
M(x) =
(t) (t)
S P
L

upon suitably relabeling the states.

 

 

 

 

 

Definition 3.1. 4.: A cycling tape x = 0'. 0'. . . . 0'. is said to be
11 12 1d
a prime gycling tape if no proper subtape of x of the form

 

0'. 0', 0'. , I: j_<_ k_<_ d, isacyclingtape.
lj 13+1 1k

Definition 3.1. 5.: A tape x is said to satisfy the prime cyclic
S,(1) 5(2),

 

. . . , S(t)) iff x is a prime cycling tape

of the cyclic classes 5(1), 8(2), . . ., S“) .

c onditi on C P(x;

The notion of a prime cycling tape is intimately related to

the s-stability problem as we point out in the next theorem.

37

 

Theorem 3.1.1.: A probabilistic automaton G) is s-stable iff 2*

contains no prime cycling tapes.

23:29}; (a) If C? is sustable, then 2* contains no cycling tapes.
For, if we assume that there exists a prime cycling tape x, then
there exists a fixed y > 0 such that 11in; H M(xk)(l :Y . Consequently,
s-instability is evident by observing that the symbol matrices of 63
can be perturbed so that 63' is quasi-definite, whence
lim H M'(xk)” = 0.
k—eoo
(b) If 67 is s-unstable then C) is a NQD automaton by
Theorem 2. 3.1. Thus, for any integer k there exists a tape
x = 0'. 0'. . . . 0’. with lg(x) : m > k for which the matrix

11 12 1rn
M(x) is not scrambling. Consequently, there exists two states
51 and sj in S such that

0' 0"

s. 31 5(1) 2 5(2) 3.3 I.“ SUD)
1
s “:1, T0) “'12 Tm “:3, “12.4 T(m)

where S(r)f1 Th) 2 Cb (r : l, 2, ..., m).

_ Since there are only a bounded number B (see Lemma 3. 2. 2) of such
distinct allocations of the state set S, it follows that any non-
scrambling tape x with length lg(x) > B must contain a prime

cycling tape.

38

3.2. Some Properties of the Cyclic Structure
In this section we develop some fundamental properties of

the cyclic structure of NQD automata. We now prove some lemmas.

 

Lemma 3.2.1.: If x = (r. 0'. 0'. satisfies C(x; 8(1),
11 12 1d
8(2), ..., S(t)) then for each initial segment x1; = 0'. 0'. 0'.

(kid) of x, andforall 1:1, jgt (i/tj)

Proof: Assume, on the contrary, that there exists two structures

2)

8(1) and S”) of C(x; 8‘”, S( , S(t)) such that

5‘? 0 sq: = Vyé ¢ . Then

x1 X1

xk+1
in violation of the defining requirement of disjoint cyclic classes

of the cyclic condition.

Lemma 3. 2. 2.: If a tape x = 0'. 0. . . . 0'. satisfies a prime
11 12 1d
\
cyclic condition Cp(x; 5(1), 8(2’) then lg(x) : d _<_ 3n - 2n+1 + l ,

 

where n is the number of states in S.

Proof: By Lemma 3.2.1, all initial segments xk of x must be

1
(1) (2) _ . . .
such that S k H S k — <1> . The successwe pairs of images
x x
l l
Suk) and 5(2k) are disjoint as illustrated below:
X1 x1

O'i 6i 0'i 0'i
1 l 3 d
(1) _. (1) _. (1) _. _, (1)
S S 1 S 2 S d
x1 x1 x1
0'i 0'i (Ti (Ti
(2) _,l (7-) _,Z (7-) _,3 _,d (2)
S S l S 2 S (1
x1 x1 x1
where 5(12 0 S(:) = 4) for k =1, 2, . .. , d. It is important to
x x
l 1
note that Suk) U 5(1) may not be the whole state set. All that is
x x
l 1
required is that 5‘12 and S(:) be nonnull and disjoint. The maximum
x x
1 1

number of such nonrepetitive, nonnull allocations of n objects can
be computed as follows: The number of allocations of subsets of

n objects into two sets A and B, so neither A nor B is empty,
is equal to the number (3n) of assignments of n objects to A, B
or neither, minus the number (Zn) in which A is empty, minus the
number (Zn) in which B is empty, plus the (l) assignment for

which both A and B are empty. The total is d = 3n - 2 - 2m + 1 .

3. 3. Algorithm for Locating Prime Cyclic Tapes

A bounded algorithm is given here for locating all prime
cycling tapes in 2* . The algorithm can also be used to decide
the quasi-definite condition since, by Theorem 3. 1. l, the quasi-
definite condition is satisfied if and only if there do not exist any
prime cycling tapes. The basic idea involved which stems from
Lemmas 3. 2. l and 3. 2. 2, consists of forming a transition tree of
the possible disjoint transitions. More precisely, if x = 0'i (Ti . . . 0'i

(11 (2) 1 2 d

S S ).

then we

satisfies the prime cyclic condition Cp(x;

have the following sequence of transitions

40

0". 0'- (Ti 0'-

11 1 3 JLd
5(1) —~ 5‘11) 3. 5‘12) _. —~ sud) C 5”)
X1 X1 X1
0'. 0". 0'. 0'.
8(2) 3,1 5(2) :2 5(2) :3, :1 5(2) C S(2)
xi xi x?

Lemma 3. 2.1 implies that

suk) fl 5):) = e for 1: kin.

Thus, one only needs to consider the possible sequences of disjoint
transitions in order to locate the prime cycling tapes in 2* .

Let us consider the probabilistic automaton 6) defined
over the alphabet 2 : {0'

02, . . ., 002 } and state set

1’
S = { l, 2, 3, . .., n} by the transition matrices M(O’i) , 0'1 6 2 .

The algorithm involves constructing a transition tree of the possible

state transitions. With each tape x e 2* , we associate an ”access

(i)

X

vector” Vx whose 1th component V is the set of states accessible
from state i by tape x . We now construct a transition tree whose
vertices are the access vectors and whose directed edges are labeled
by the symbols 0'i e 2 , that map the access vector Vx into the
access vector Vx0'. . The root vertex of the transition tree is the

1
access vector V4) = l 2 . . . n corresponding to the null

 

 

 

 

 

 

 

tape 4) . The transitions emanating from a given vertex are ordered

by the symbols 0'2.l from right to left as 01, 0'2, . . . , 0.02 .
(i)

X

Next, any component V and its successors are crossed out

if Viz) has a nonnull intersection with all other components in Vx.

That is to say; we retain only those components VS) of Vx that

41

could generate a cyclic structure.

Each branch in the tree is terminated when either 1) all
components of the last vertex are crossed out, or 2) there exist
two disjoint sets of components that are recurrent from a
preceding vertex. The first termination, called a scrambling
termination, implies that the scrambling condition has been
reached. The second termination, called a cyclic termination,
implies that the tape generating the recurrent classes is a prime
cycling tape. This algorithm terminates in a bounded number of
steps, since the transition tree so defined is bounded by Lemma
3. 2. 2.

The following examples clarify the essential features

encountered in constructing the transition tree.

Example 3. 3.1.: Consider the automaton 63 defined over the

 

alphabet 2 ={0'1, 0'2} on the state set S = {1, 2, 3, 4} by the

transition matrice s .

1 2 3 4 1 2 3 4
"’ 1 3 “ ' 1 5
l O :4- Z O l O 0 3' z)-
2 0 1— i 0 2 1— 1— 0 0
M _ 4 4 2 2
(“1) " 1 2 M("2) : 1 3
3 — 0 0 - 3 - - 0 0
3 3 4 4
1 2 1 1
4 _3— 0 0 3: 4 L0 0 3 f-

 

 

 

The transition tree for the example at hand is given below:

 

42

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

vc ic Scrambling

3 1 l 3 V l V U

4 2 2 4 “261‘72 “2 101
‘ 0'

. U . .
Scrambling \2 / 1 ‘ _C.Y1_1£_ Scramhhng
l l 1 V0- 0 l 2 2 1 V U 1 l 3 3 V 0- l 1 1 1 V0-

2 2 4 3 3 4 “2 1 2 2 4 4 “1 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

We observe that branch x = 0'10'Z possesses two disjoint

recurrent subsets, 5(1) = {1, 2} and 5(2) 2 {3, 4} with respect

to tape x = 0'10'Z . That is to say, 55:1)0' - 8(1) and 5:2)0 -> 5(2).
1 2 1 2

Thus, the tape x = 0'102 is a prime cycling tape. Also, branch

x = 0'20'10'2 again points out that the tape x = (7102 is a prime

cycling tape. Since all other branches terminate by the scrambling

condition, the tape x = 010'2 is the only prime cycling tape in 2’:< .

Example 3. 3. 2.: Consider the automaton 6) defined over the
alphabet 2 = {01, 0'2 } and on the state set S = {1, 2, 3, 4} by

the transition matrices,

0 p1 1 -p1 0 0 l 0 0

pl 0 l-pl 0 0 0 p2 1 -p2
M("1) = 1-p10 0 pl ’ M(“2) = 0 0 o 1

l-p1 0 p1 0 p2 l—pZ 0 0

where 0< p1, p2< 1.

43

The transition tree for this example is given below:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l X X X X 1 X X 1 X X

\"Z /"l \‘r2 /"l
3 1 1 3 1
4 2 3 4 x 2 X x x
OR I (II 0'2 1 _"
3 1 2 1
2 4 4 2 3 4
\0'2 01
1 2 3 4

 

 

 

 

 

 

Since all branches in the transition tree are terminated by
the scrambling condition, there do not exist any prime cycling tapes
in 2’5< . It follows by Theorem 3.1.1, that the given probabilistic

automaton is indeed s-stable.

3. 4. Quasi-Actual Cyclic Conditions

In this section, the cyclic structure is refined so that we
can obtain some o-stability results for NQD automata by methods
similar to those used in Theorem 2. 3.1. First, we recall that if
a tape xe 2’:< satisfies C(x; 5(1), 5(2), ..., 8*”), then the

transition matrix M(x) is a partially tudecomposable matrix,

i. e. , M(x) has the form

 

 

5(0)
5(0) T(o)
5(1)
S(2)
M(x) = . (3.4.1)
Sm

 

 

 

 

 

44

upon suitably relabeling the states.

Definition 3. 4.1.: A partially tudecomposable matrix (3. 4.1) is

 

said to be block actual if T(O) 2: 0 and 13(1) > 0 for i=1, 2, ...,t.

 

Similarly, a t -decomposable matrix is said to be block actual iff

 

P(1)> 0 for i: l,2,...,t.

Definition 3. 4. 2.: A partially t-decomposable matrix (3. 4.1) is
(0)

 

said to be block qpasi-actual iff T : 0 and the only zero entries

 

. i .
in P( ) occur in columns of zeros.

Definition 3.4. 3.: A cyclic condition C(x; 5(1), 5‘2), . . . , S(t))

 

is said to be actual iff the partially t-decomposable matrix M(x)

is block actual.

Definition 3.4. 4.: A cyclic condition C(x; 5(1), 5(2), . . . , S(t))

 

is said to be quasi-actual iff the partially t-decomposable matrix

 

M(x) is block quasi-actual.

Definition 3. 4. 5.: An unbounded product (T of stochastic matrices

 

Pi is said to be nonlimiting iff there exists a fixed a > 0, such

 

that for each positive integer k, the minimal nonzero entry in

k
Tl- Pi is greater than (1 .
i=1

Let A be an (n x n) stochastic matrix and B be a (n x n)
matrix whose only zero entries occur in columns of zeros. Then

for any nonzero entry ci j in C : AB

- n
. . . b . mm 2: a. = b

min . . . .
where b 18 the m1n1mal nonzero entry in B . We now have the

45

following lemma.

 

Lemma 3.4.1.: If each X1 in the tape x=xl x2143 xk...

satisfies a quasi-actual prime cyclic condition C , . . . ,
then the matrix product M(x) = M(xl) M(xz) M(x3) . . . M(Xk) . . . is
nonlimiting.

This result: follows from the above inequality by observing
that for any positive integer k ,
’ :3.) ‘

1

 

 

 

 

 

 

 

F0 T<1>,P(1> T02) , Pm . . TS),P(t)_

 

 

 

 

 

 

 

1 !
where Put) : P‘r) P(r) P‘r) for r = 1,2, ...,t. Throughout
j x. x. x.
xi 1 1+1 3
this paper, we shall refer to an automaton represented by such a

matrix product as a "direct sum" of disjoint automata.

 

46

Lemma 3. 4. 2.: If each prime cycling tape in 2* satisfies some

 

actual prime cyclic condition that is completely t-decomposable,
then each cycling tape in 2’:< satisfies some quasi -actual cyclic

condition with exactly two cyclic classes.

Proof: Consider any cycling tape x e 2* that satisifies the cyclic

8(1), 8(2)) . If the tape x is not a prime cycling

condition C(x;
tape, then x can be partitioned to display a prime cycling tape

xl as follows:
x : y1 x1 21

where y1 or z could be vacuous. Since x1 is aprime cycling

142)) ,

l

tape, it satisfies some actual cyclic condition Cg(xl; TU),
that is completely decomposable. Consequently, we have for some

permutation R of the integers l and 2 the following mappings:

y x 2
5(0) 4 s 4 s —1~ 5(1)U 3(2)
y x 2
5(1) _1 T<R<1>> 1 Tutu» _1 S(1)
5(2)’: T(R(Z)i X1, Tum» :1 S(.2)

5(0)

where contains the non-enterable transient states. Since

CIIDJ(X1; Tu), T(Z)) is actual, for any states 5 6 5(1) and t 6 S(2)

we have
z
Y1X1‘S) T<R<1>> _1,T<ZR<1)) , V 363(1)
1
and
. , z
Y1 x1“) T1R(2)._._1, T(ZR(2)> , u ,6 S(2)
1

Hence, the quasi-actuality condition is preserved.

47

3. 5. Zero-Stability Theorem
In this section we use the cyclic structure to obtain a

o-stability result for NQD automata, by methods similar to those
used in Theorem 2. 3.1. The result extends the Rabin stability
problem to NQD automata. We shall omit some of the e and 6
details, given in Theorem 2. 3.1, that serve only to obscure the
initial understanding of the proof.

A tape x e 2’:< is said to be respectively o-stable,

s nonlimiting, or scrambling iff the matrix M(x)

is o~-stab1e, nonlimiting, or scrambling.

Theorem 3. 5.1.: A probabilistic automaton 63 is o-stable if

 

each prime cycling tape in 2* satisfies some completely 2-decomposab1e

prime cyclic condition that is actual.

Proof: Let x be any tape in 2* . First, we shall prove that if
x E 2* is not a scrambling tape, then x is o-stable and nonlimiting.
Secondly, we shall use this fact to prove that all scrambling tapes

in 2* are o-stable under the conditions of the theorem.

An ordered collection of disjoint nonempty subsets

5(1) 5(2)

’ 9...,

Sfi‘t) of the state set S, written

 

. -' It".
(8(1), 512), . . . , 8“") , is called an t-ordered cyclic
structure.
Case 1: If x e 2* is not scrambling, then we can partition x into
x = yox1 yl x2 y2"'XByB (3.5.1)

n.
1

where xi 2 .TT XEJ) denotes a concatenation of cycling tapes
F1

x?) e 2*, that satisfy a cyclic condition C(XEJ); SE1), 5:”). The

48

different possible 2—ordered cyclic structures are indexed by i,
and the tapes that preserve these ordered cyclic structures by j.
The tapes yi are "transition" tapes that do not contain any cycling
subtapes. Clearly, the finite state assumption gives a bound

n n+1

B = 3 - 2 + 1 (see Lemma 3. 2. 2) on the number of distinct

2-ordered cyclic structures, where n is the number of states in
S .

For a suitable ordering of the ordered cyclic structures, the
concatenated form of x in (3. 5.1) is obtained by first segmenting

off all cycling tapes x(1J) as

so that the tape yO contains no cycling subtapes, and no initial

satisfies C('; S“) S( j) . Next we segment off

i ’ 1
all cycling tapes x?) as

segment of z1

Y : y0X1Y1X222

so that the tape y1 contains no cycling subtapes and no initial

‘- 1" \.
segment of 22 satisfies C(‘g 8:1), 8‘22”). Continuing this process,

we obtain the concatenated form of x shown in (3. 5.1). In general,

the cycling tapes x?) in (3. 5.1) are not prime cycling tapes.

Definition 3.4.4.: A tape x e 2* is said to generate k ordered

(1')

cyclic pairs iff k is the minimum integer such that each X1 in

 

the concatenated form (3. 5.1) of x,

x = yoxly1 xzyz... xmym, where mfik,

49

generates (k - 1) or fewer ordered cyclic structures. For k = 0
we mean that x contains no cycling subtapes.

We now prove that any nonscrambling tape x e 2* is
o-stable and nonlimiting, using induction on the number of distinct
ordered cyclic structures generated by x. First, we showthat ‘if
x 6 2* generates only one ordered cyclic structure, then x is

o-stable and nonlimiting. We partition x into

M
X = Yb’fi.yl ‘ X1: Tl Xy)’
i=1
where each x?) satisfies Cg(x(lJ); S(11), S(12)). It follows from

Lemma 3. 2. 2 that the lengths 1g (yo), lg (yl), and lg (x(lJ)) are

+
no greater than 3n - 2n 1 +

1 . We observe that the matrix product
M(xl) is o-stable, since it can be viewed as a direct sum of two
disjoint quasi-definite automata (Theorem 2. 3.1). Lemma 3. 4.1
implies that the matrix product M(Xl) is nonlimiting. Since the
lengths lg (yo) and lg (yl) are no larger than 3n - 211+l + l ,
the tape x is o-stable and nonlimiting.

To complete the induction proof, we assume that any non-
scrambling tape xe 2* that generates k or fewer ordered
cyclic structures is o-stable and nonlimiting. Consider any non-

scrambling tape x e 2’;< that generates k + 1 distinct ordered

cyclic structures, and partition it into

Y ; Unfik+n.(r52)

xzyoxl'ylxzyz...x m

m

m

Each cycling tape xi in (3. 5. 2) generates k or fewer ordered

cyclic structures. Hence, by induction, we know that the matrix

50

products M(xEfl) in (3. 5. Z) are o-stable and nonlimiting. That
is, given any 61 > 0 there exists a 6(61) > 0, such that the

inequalities

|M(0'i)-M'(0"i)l < 6 v 0162

imply (3. 5.3)

mug”) - my”): < 61

for all xij) in (3. 5. 2). Lemma 3. 4. 2 implies that each cycling
tape x?) 6 2* satisfies a quasi-actual cyclic condition with two
cyclic classes. Note that Lemma 3. 4. 2 requires each prime cyclic
tape to satisfy an actual prime cyclic condition that is completely
Z-decomposable. Then, Lemma 3. 4.1 implies that each matrix
product M(xi) in (3. 5. 2) is nonlimiting. Now each matrix product
M(xi) in (3. 5. 2) is o-stable by Theorem 2. 3.1, since each can be
viewed as a direct sum of two disjoint quasi-definite automata.

n+1

Since the length of each yi in (3. 5. Z) is bounded by 3n - 2 + 1

(Lemma 3. 2. 2), it follows that the matrix product M(x) is o-stable
and nonlimiting. That is, given any 6 > 0 there is a 61 > O and

a corresponding 6(61) > O in (3. 5. 3), such that the inequalities

|M(o'i) - M'(Ui) < 5 3.: oi e 2
imply that
[M(x) - M'(x)l < e .

Since the induction is bounded (k _<_ B) , we conclude that any non-

scrambling tape x e 2* is indeed o-stable and nonlimiting.

51

Next, we prove that if x 6 2* is a scrambling tape, then

x is o-stable.

Case 2: If x is a scrambling tape, then it can be partitioned into
"prime" scrambling tapes yi that contain no scrambling subtapes,

as follows:

where wn = yn y . . . y2 y1 . Now, if the length of y1 is no

n-l

larger than 3n - Zn+1 + l , then clearly we can choose our

perturbations of the symbol matrices sufficiently small so that

M(yi) is o-stable and nonlimiting. On the other hand, if the length

of yi is greater than 3n - 211+l + l , then we can delete one symbol
and consider {>1 defined as
A
y1 : (Ti Yi '

Since 9i is not scrambling, Case 1 implies that M(yi) is o-stable
and nonlimiting. Consequently, the matrix M(yi) = M(O'i) M(fii)
is o-stable and nonlimiting. Hence, the perturbations of the

symbol matrices can be chosen sufficiently small so that
|M<yi) - M'W' < 61 v vie x (3.5.4)

for any given 6 > O.

1

Consider the matrix norm

IM(x) - M(x)! = lM<u) M(wn) - M'(u) M'(wn)l

By adding and subtracting terms, we get

52
|M(x) - M(x)! = l(M<u> M(wn) - M(wnn - (M'm M'(wn) -M'(wn))
+ (M(wn> - M'(wn))l .

The triangle inequality yields

lM<x> - mm! 5 Wm M(wn) - M(wnH + IM'(u>M'(wn) - M(wn)!
+ |M<wn) - M'<wn)l

Applying Lemma 2. 2. 4, we obtain

IM<x) - M(x)! : H M(wn)” + II M'(Wn>” + IM<wn) - M'<wn)l

Let Y and y' be the minimal nonzero entries in {M(yi)| yi6 x}
and {M'(yi)| yie x} respectively. Since each matrix string M(yi)
is nonlimiting, there exists a fixed a such that y, y' _>_a > O .

By Theorem 2. 2.1, we choose an integer N sufficiently large so

5(1-e)N5£.

5 (1 .. e)N_<_ €- and ”M'(w 3

Since N is a finite integer, we can choose 61 > 0 in (3. 5. 4)

that ll M(w N) H

sufficiently small so that I M(wn) - M'(wn)l < .3S . This completes

the proof that given any 6 > 0 there exists a 6(6) > 0 such that

the inequalities

[M(O'i) — M'(Ui)| < 6 u 0'16 2:
imply the inequalities

IM(x)-M'(x)l < e u xez

if the zero entries are not perturbed.

53

3. 6. Algebraic Structure of NQD Automata

In this section, we obtain some o-stability results for NQD
automata in terms of their algebraic structure. The algebraic
systems called semigroups, monoids and groups satisfy,

respectively, the first two, three, and four of the following axioms:

Let a, b, c represent any elements in a set A ; then
Al) Closure Law : ab 6 A
A2) Associative Law : (ab)c = a(bc)
A3) IdentityLaw : 3e16d,3Va614,ael=ela*-:a
A4) Inverse Law : V a 6 A)3 a.1 6.4 3 aa-1 = a-la = e1

The set of all (n x n) stochastic matrices forms a semigroup.
But, although the inverse A.1 of an invertible stochastic matrix A

has unit row sums, since

some entries in A_1 will be negative unless A is a permutation

matrix. Hence A"1 need not be stochastic. For example,

 

 

 

 

(— —l — ‘1
l l
'2' z 2 ‘1
A 2 implies A.1 : .
_O l_ _O 1_J

Thus, one needs an identity element that is more general than the
ordinary unit matrix in order to have a potentially fruitful stochastic

computing structure.

54

The general structure of a group of stochastic matrices has
been examined by M. Rosenblatt [15] , 1965. We shall adopt some
of his notation and characterize the structure of certain NQD automata.

This will enable us to obtain a o-stability theorem.

Definition 3. 6.1.: A (n x n) stochastic matrix U with identical
rows is called a primitive idempotent matrix. It has the form
U = Is u where u is an arbitrary row vector of U .

Since a general idempotent stochastic matrix plays the
important role of an identity element in the algebraic structure of
probabilistic automata, it is important to determine precisely its

structure.

Theorem 3. 6.1.: If P is a stochastic idempotent matrix labeled
by states, then there is a partitioning of the state set S into disjoint

sets of 8(0), 8(1), ..., S“) so that P has the form

 

 

 

 

5(0) 5(1) 5(2) . . . S(t)
5(0) — 0 Q(1)U(1) Q(Z)U(Z) . . . Q(t)U(t)-‘
5(1) 1' UH)
5(2) U(2)
p = (3.6.1)
S(t) U(t)

 

 

where Uh) (i = l, 2, ..., t) are positive primitive idempotent
matrices. The Q“) (i: l, 2, ..., t) are 05(0) by 08(1) matrices

that can be chosen as

55

1 2 3 Os“)

_ _

1 (1‘11) 0 o o

2 (1‘21) 0 o o

(i)
. 3 0. 0 O . . . 0

05(0) a(i) o o 0
05(0)

 

 

—J

where 0_<_ a§1)_‘fl and _2 agl) =1 for j: l, 2, .. 08(0) .

1:1 . ’
Proof: We recall from matrix theory that P can be transformed

into Jordan form A by a suitable similarity transformation,
S P S = A
. 2
Since P = P, we have

s”1 PZS=S'1PS=AZ=A

whence it follows that the eigenvalues of P are either 1 or 0.
Theorem 2. 2. 5 implies that P is partially t-decomposable. That
is to say, there is a partitioning of the state set S such that P

has the block form

5(0) 5(1) S(2) Sm

 

 
   

 

5(0) "Tm Tu) Tm Tm"
S(11) Pm
S(2) Pm
P :
Sm Pm

 

 

 

 

 

 

56

Note that, if P had a 0 column under 5(1) for i > 0, then this
column could be included in 5(0) by a relabeling of states. Thus,
each P“) can be made a positive idempotent matrix that has
precisely one unit eigenvalue. Consequently, each P“) has rank
1 . The stochastic condition then implies that each P“) has identical
rows. Hence, each P“) is a positive primitive idempotent.

The eigenvalues of T(O) are all zero, since T(O) is nil-

m

potent, i. e. , there exists an integer m such that (T(o)) = 0 .

Since T(O) is also idempotent, it follows that T(O) : (T(o))m = 0 .

The idempotency of P requires each T“) to satisfy
r“) = T(1)P(1) . (3.6.3)

Each positive primitive idempotent 13(1) has the factorization

Pm

(i) (i)
Is p

where ph) denotes

is a positive stochastic row vector. If 1:”
3
(1)

03(1) x O8(1)) unit matrix I , then

the first row of the (
I(1) I(1)

1,. 3 21,50

(i)_ (i) (i)_ (i) (i) (i) (i) (i)
T —T P _T 18(11’..Is)p

- (i) (i) (i) (i) _ (i) (i)
- (T IS ) Il, . P — Q P
where 0(1) is defined in (3. 6. 2).

It is convenient to employ the concept of o-equivalence of

two matrices.

57

A is o-equivalent to B (denoted A ,3, B) iff
o A and B are (n xn) matrices having the same
zero configuration.
In general, a probabilistic automaton 6) whose set of
. . . Z __ .4. .

tran31tion matrices — {M(x) I x 6 2 } forms a mon01d need
not be o-stable. In fact, if one designates the identity element U
as the ordinary unit matrix, one can construct an example similar
to Kesten's, that is also o-unstable. However, if we enrich the
"monoid" automaton with the additional property that each element
P 6 J has a corresponding "reset element" Pr 6 .4 such that
P Pr r92 U then we can obtain o-stability. We call such a system

a reset monoid. The ”reset property" gives the automaton the

 

ability to reset itself back into the idempotent cyclic structure.
It is important to notice that the "reset property" does not assume
P Pr = U . However, the following deve10pment proves that the
reset monoid conditions do imply that P Pr = U . That is to say,
a monoid set J of (n x n) stochastic matrices is a group if
each element P 6 A has a corresponding reset element Pr 6 J
such that P Pr R, U .
We begin by considering a "zero-reset" probabilistic automaton
(P whose set of transition matrices A = {M(x) I x 6 2*} contains

a block actual partially t-decomposable matrix U such that,
PU/ep V P64 I (3.6.4)

and such that for each P 6 ,4 there is a corresponding "reset

element" Pr6 ,4 satisfying

PP ,Q,U. (3.6.5)

58

By definition, there is a partitioning of the state set so that the

matrix U has the form

 

 

 

 

 

S(o) S<1) S(2) Sm
Sto) '0 Tm T<2) Ttt)‘
S(1) 3(1)
8(2)
U : (3.6.6)
Sm L Bu)‘

 

 

(1)> 0, i.e., all entries in B“)

where each B are greater than

zero. Let P be any matrix in J and partition the rows and

columns as in U,

 

 

5(0) S(1) S<2) Sm
S(o) ”Pm. 0) p(0.1) P(0. 2) Pm. t)"
5(1) pa. 0) p(1,1) P(1.2) P(1.t)
S(2) P(2. 0) p(2.1) P<2. 2) P(2.1:)
P = . (3.6.7)
Sm P(1:,0) p(t.1) Pu, 2) Pu. t)
... _J
One readily observes from (3. 6. 4) that P(i’ O) = O for i = O, 1, 2,
. . . , t . Then (3. 6. 4) implies

In order that P Pr r32 U , it is necessary by Lemma 3. 2.1 that

59

the matrices P and Pr generate the following mappings:

1“

S(1) Tm S(1)

_12
1'
5(2) 2 T(2) _12 S(2)

(to

1‘
SM 3 Tm _I:

Sm

where the sets Th) (i = l, 2, ..., t) are pairwise disjoint.

each element P 6 ,3 must be such that P U R, P . Hence

S(1) 12,141)

S(2) I3, T<2) .11

IC‘

Tm

T(2)

Tm 9, TM

(*0

Sm

The structure of U in (3. 6. 6) requires each 5(1) to be some

Now

Sm .

This implies that each element P performs a permutation on the

cyclic structure as follows:
S(1) P S(R(1))

5(2) E, 5(R(2))

Sm a S<R<t))

where R is a permutation on t integers. We summarize these

results with the following theorem.

Theorem 3. 6. 3.:

 

60

group on the integers 1, 2, ..., t . If G

is a zero-reset

Let Q be any subgroup of the total permutation

probabilistic automaton, then any matrix P 6 4 = {M(x) I x 6 2*}

has the form

s(o)
S(1)

S(2)

S(t)

for some R 6 Q , where each P

1 < i, j _<_ t . The notation implies that each row and column

except the first has exactly one non-zero block that is positive.

S(o) S(1)
F‘O P(0.1)
(1.1)
O 613(1)P
O
(t.1)
O 6t,R(1)P

 

(i.J')

6

6

5(2)

pm. 2)

p(1.2)

1.R(2)

t, R(Z)

Pu. 2)

6

6

Sm

Pm. t)

pl“)

1, R(t)

t, R(t)

(3.

> O and has unit row sums for

We now consider a "reset monoid" probabilistic automata

 

()3 whose set of transition matrices .4 = {M(x) I x 6 2*}

contains a two-sided identity element U = U2 6 ,4

and for each

P there is a corresponding reset Pr 6‘! , such that P Pr ,Q, U .

Thus, for each P 6 ,4 we assume that

UP=PU=P

and that there is a Pr 6 ,3 such that

PPrRJU .

Pu. t)

_J

 

6. 9)

(3. 6.10)

(3. 6.11)

61

The general structure of the stochastic idempotent matrix

U is given by Theorem 3. 6.1 as

 

 

 

 

 

5(0) S(1) S(2) Sm
5(0) (0 Q(l)U(1) Q<2)U(2) QmUm‘
S<1) U(1)
S(2)
U = (3.6.12)
Sm U(t)_

 

 

)

where each U(1 is a positive primitive stochastic idempotent. Let

P be any matrix in )4 partitioned in the same block form as U .
Theorem 3. 6. 2 implies P has the form given in (3. 6. 9). Then it

follows from (3. 6.10) that

where A(i, j) is a 05(1) by 05(3) rectangular matrix whose (k, k)
entries are ones and whose other entries are 0 . Now, if P Pr = UR; U

then U has the block form

S(o) S(1) S(2) ... 5(t)
5(0) F6 T)“ T(Z) T“)-T
S(1)

5(2)

 

 

 

 

 

 

 

62

Since each U“) in (3. 6.12) is a primitive idempotent, we have

1‘1"” Um = U“) (1: 1,2,...,t).

condition U = U U implies that Uh) = U“)

Consequently, the right identity

i=l,Z,..

.,t.

Then, it follows from the left identity condition U: U U that

Tm = Q(i) U(i) (i :

shown that any monoid set .4

1,2,...,t), whence U: U.

Thus, we have

of (n x n) stochastic matrices

which has the "reset property" is a group. We note that it is

much easier to recognize the "reset property” than the "inverse

property", especially on a computer, where round off errors

may obscure an exact inverse.

We summarize these results with the following theorem

which is equivalent to a theorem of M. Rosenblatt [l 5] , 196 5.

Theorem 3. 6. 3.:

 

group on the integers l, 2, . . . ,

Let a be any subgroup of the total permutation

t. If a general element P

contained in a group G of (n x n) stochastic matrices is

partitioned into the same block structure as U , then P has the

form
’0 Q(R(1))U(1)
(1)
0 61’R(1)A(1,1)U
(1)
O 62,R(2)A(2,1)U
P :
(1)
L0 6t,R(1)A(t,l) U

 

6

6

6

Q(13(2)) U(2)

Q(R(t)) Um

(2) (t)
(Z) ' (t)
(2) (t)

 

(3.6.14)

63

for some R in O? , where the U“) and (2(1) are defined by

the stochastic idempotent matrix U in Theorem 3. 6.1.

Definition 3. 6. 2.: A probabilistic automaton 6) whose set of

 

stochastic matrices :4 = {M(x) I X6 2*} forms a group, is
called a group probabilistic automaton.
Our next theorem is a o-stability result for a large class

of NQD automata.

Theorem 3. 6. 4.: Any "zero-reset" probabilistic automaton

 

is o-stable.

Proof: Let U 6 A = {M(x) I x 6 2*} denote the given block
actual partially t-decomposable matrix. We relabel the states of

@ so that U has the form

 

S(o) S(1) S<2) .. Sm
S(o) FD Tm T<2) . Tm ‘
S<1) Ba)

  

S<2) B<2)

 

 

 

 

 

Sm I. Bu)

where each 13(1) > 0 . Let x be any tape in 2):< . We partition

x, as in Theorem 3. 5.1, into cyclic tapes xi,

x : yo"1)’1".2.)’2 XI3 y13

64

n.
1

. ° *
where xi = IT x?) denotes a product of cycling tapes x?) 6 2
i=1

which satisfy the cyclic condition C(ng);$(l), 8(2), . . ., S(t)) .

The different possible ordered cyclic structures are indexed by

i and the tapes which preserve these structures are indexed by
j. It follows from Theorem 3. 6. 2 that there exist no more than
B = t 1 different ordered cyclic structures generated by 2* .
We now prove by induction on the number of distinct ordered
cyclic structures generated by x, that M(x) is o-stable. First,
if x 6 2’:< generates only one distinct ordered cyclic structure,

then it can be partitioned as

hi (1)
x=yoxly1, ”‘1‘ IT X1
i=1
where each x(lJ) satisfies an actual cyclic condition
CP(x(lJ); 8(1), 8(2), . . . , S(t)) . From Theorem 3. 6.2, it follows

that the lengths lg(yo), lg(xgj)) and lg(yl) are no larger than
t! . It then follows from Theorem 2. 3.1 that the matrix product
M(xl) is o-stable, since it can be viewed as a direct sum of t
disjoint quasi-definite automata. Since the lengths lg(yo) and
lg(yl) are no larger than t! , we see that M(x) is o-stable.

To complete the induction proof, we assume that any tape
x 6 2* which generates k or fewer distinct ordered cyclic
structures is o-stable. Consider a tape x 6 2* which generates

k + 1 distinct ordered cyclic structures and partition it as

xzyoxl y1 x‘2 xk+1yk+1 (3.6.15)

65

Now each cyclic tape x?) in (3. 6.15) generates k or fewer distinct
ordered cyclic structures. Hence, by induction, we know that the

matrix products M(x§3)) in (3. 6.15) are o-stable. That is, given

any 61 > 0 there exists a 5(61) > 0 such that the inequalities
|M(6i) - M'(cri)I < 6 v 016 2

imply (3. 6.16)

IM(x§j)) -M'(x(ij))I < e , 1.: XI”): x.

1

Now each matrix string M(Xi) in (3. 6.15) is o-stable by Theorem
2. 3.1. Since the length of each yi is bounded by t! , it follows
that the matrix product M(x) is o-stable. That is, given any

6 > 0, one can choose 6 > O with corresponding 5(61) > O in

l
(3. 6.16) sufficiently small that the inequalities

IM(o-i) - M'(6i)| < 6 v 0'. e 2
imply that

IM(x) - M'(x)I < 6

Since the induction is bounded (k _<_ t! ), we conclude that any "zero-
reset" automaton is o-stable.

We observe in concluding this section that since the group
structure clearly implies the "zero-reset" structure, any "group"

probabilistic automaton is also o-stable.

IV. ISOLATED CUT-POINT PROBLEM

The concept of an isolated cut point plays an important role
in probabilistic automaton theory. The a-stability result of Theorem
2. 4.1 and the equivalence between probabilistic automata and
deterministic automata depend on the existence of an isolated cut
point. As Rabin pointed out in a recent book [ 2 ], 1966, there
are two open problems in this area. Let @ be a probabilistic

automaton with rational cut point X .

Problem 1: Can one give a procedure for deciding whether or not

 

a given cut point )x is isolated?

Problem 2: Can one give a procedure to determine whether or not

 

G) has any isolated cut points?

The results of this chapter focus on these problems. Our
first approach is set theoretic. We define a set of response
intervals which contain the response points. Our second approach
is topological. In this, we define a pseudo-closure operator that

encloses the points which are not isolated cut points.

4.1. Set Theoretic Approach
Consider a probabilistic automaton 6) defined over the
alphabet 2 = {1, Z, ..., 02} and on the state set S = {1, 2, ..., n}.
We begin by giving a very simple sufficient criterion to decide that
a given cut point X is isolated. We follow the deve10pment in

Section 2. 4 by defining the response intervals Ri as in (2. 4. 2),

66

67

R.=[z: Ai.,E WHO [0, 1] (4.1.1)
1 j6F J j6F J

for all i6 2 where

i Min .
A]. - k {M‘l’m}
and
i _ Max .

The range of the response of the jth column of M(i), pre-
multiplied by an arbitrary row stochastic vector p = (p1, p2, . . . , pn) ,

satisfie s the inequality

 

 

(i)
Ml,j
(1)
M2,]
1 < i
Aj _ (p1, p2, ..., pn) . _<_ Vj . (4.1.2)
My].
I. '_
Consequently, we have
>3 Ai. : TTOM(X)M(1) 0F: 2 \71 (4.1.3)
15F J j6F J

for all x 6 2*.

It is clear from (4.1. 3) that all response points are contained in

R =.U R. (4.1.4)

The situation is illustrated on the probability interval, PI = [0, 1]

below:

68

PR OBABILIT Y INTER VAL

WW

0 1

where the intervals may overlap. Any points not contained in any

R1 are eligible isolated cut points.

Criterion 1: Any cut point A 6 PI - R is isolated.

 

The analysis up to now has given only a sufficient criterion
to conclude that a given )\ is isolated. It is by no means necessary,
since there may exist isolated cut points within the response intervals.
The existence cf anisolated cut point is guaranteed for actual automata
in view of the above results, since the entries in the symbol matrices
are positive. However, these extreme cut points may not be very

interesting, since they may accept or reject all tapes in 2* .

ExampJe 4.1.1.: Consider the actual probabilistic automaton

 

@(S, 7? , l, 2) defined over the alphabet 2 = {1, 2} and on the

state set S = {1, 2} by the symbol matrices

l 2 1 2

3 l l 2

1 2: 21' 1 a 3‘

M6) = 2 1_ ,_ . M2) = 2 1_ e
2 2 4 4

Since F = {2} , only the second column need be considered. The

response intervals Ri are given by (4.1.1) as

] .

NW

2
] and R2_[§,

NIH

1
R1'['4"

69

By Criterion 1, any cut point )t 6 [ O, i) U (é: , 33-) U (% , 1] is
isolated.

We now extend these response intervals to tapes of length
N by defining for each tape x 6 2N = {xI lg(x) = N, x 6 2*}

a response interval RX as,

RX :[jEFAli'jEFv11n [0' 1] (4°1°5)
where

A? = N5“ {M(mm}
and

V: = Mix {M(x)k’j}

Now consider any tape x in 2”< with lg(x) _>_ N. If we partition

x as x = y z where z 6 2 then it follows from (4.1. 3) that

N ’

rp(x) is contained in R2. In general, if

R = U R :
YEZN Y

then the response to any tape x 6 2* with lg(x) _>_ N is contained
in RN. However, the response of tapes whose lengths are less

than N may not be contained in RN .

Criterion 2: Any cut point )t 6 PI - RN such that

)\ f {rp(x) I X6 2N-1}

 

is an eligible isolated cut point.

Example 4.1. 2.: Consider the probabilistic automaton G) (S, M , l, 2)

 

defined over the alphabet 2 = {1, 2} and on the state set s = {1, 2}

by the symbol matrices,

7O

 

 

 

1 2 l 2
l- " "‘

3 l 1 l

12 2 II: '2:
M(1)=21_ 1- ,M(2)=ZI1_ 3—
__2 2__ L4 4_j

By Criterion 1, any cut point X 6[ 0, 1:) U (931, 1] is isolated.
However, these points are trivial, since they either accept or reject

all tapes in 2* . Let us now consider all the matrix products of

 

 

 

 

length two:
16 16 8 8
M(11)= , M(21)= 1
.5. 2 _9_ 7
_8 8 J .16 1‘63
F2 .9.“ ”‘9. 2‘
1 16 8 8
M02) = , M(22) =
3 2 _5_ 1.1.
_8 8..I L16 lé-J o

 

 

 

 

. - _5_ _7_ .9. 1.1.
By Criterion 2, any )x 6[O, 16) U(16 , 16) U (16 , l] , not a
response point '31- or :—, is an eligible isolated cut point. One
should note that the response intervals have separated and allow
9

nontrivial isolated cut points within (ll6 , I?) .

We now prove a theorem which focuses on the isolated cut

point problems for quasi-definite automata.

Theorem 4.1.1.: Let G) be a quasi-definite probabilistic automaton

 

defined over the alphabet 2 = {1, 2, . . . , o2 } and on the state

set S = {1, 2, . . . , n} . Given any rational cut point )t , one can

71

conclude with a bounded experiment that either k is not Y -isolated

or i is Y*-isolated for any fixed y > o and some y* > 0 .

£1931: Given any 6 > O , there is, by the quasi-definite condition,
an integer N(6) such that lg(x) ?_ N and x 6 2* imply that

II M(x) II < 6 . A particular integer N can be determined for any

6 > O by Theorem 2. 2.1. Let us consider any tape x in 2*

with lg(x) > N . Partition x as x = y z where lg(z) = N . The
quasi-definite condition implies that II M(z) II < 6 . We now write

the matrix M(z) as a sum

M(z) = UZ + Nz

where U2 is a primitive idempotent matrix whose equal rows are
the average of the rows of M(z) and where Nz is such that
I NzI < 6 . Now let P be any (n x n) stochastic matrix and

consider

PM(z)=P(U +N)=PU +PN =U +PN .
z z z z z z

The stochastic condition implies that I PNzl E I NzI < 6 . Thus,
if we choose 6 = Y/(2 0F) then the response rp(x) is contained

intheinterval R*= [17 U0 --Y-, TI’U O +1] . Hence, if
z oz 2 ozF 2

F
we wrap a closed Y -neighborhood N(rp(z), Y) about rp(z) , then
we enclose the response of rp(y z) for all y 6 2*< . Consequently,

if we form

21
ll

U N(rpb‘): V) 9
X62N

then we can say that any point )t 6 R is not Y -isolated. On the

72

other hand, if )\ 6 PI - R then we can say that )t is Y*-isolated,
where Y* is the minimal distance from )\. to R .

We complete this section by giving a sufficient condition to
conclude, for any quasi-definite automaton @ with a single
starting state so, and a single final state sF, that Q has no
isolated cut points. Let V be any arbitrary (n x 1) vector whose
components vi satisfy 0 E vi _<_ 1 . We shall call such a vector

a probability vector. We define the range of V, @(V) by

(R(V) : [vmin’ vmax]

where v . and v are the minimal and maximal components
min max

of V. We say that the symbol matrix M(cri) covers V if

n’ vmax] '

R(Mtoi) V) 3 [vmi

More generally, we say that the set of matrices M(cri), 0'1 6 2 ,

covers V if

(Rn/)6 0th (R(Mwi) V) .

Theorem 4.1. 2.: Let @(S, 7? , so, sF) be a quasi-definite

 

probabilistic automaton defined over the alphabet 2 ={ 0'1, 0'2, . . . , 0'0 }

2
and on the state set S = {31, 82’ . . ., sn'} . If the symbol matrices
M(O'i), 0'16 2 cover any probability vector V, then 0 has no

isolated cut points.

Proof: We observe for any tape z 6 2N that if the probability

vector V is chosen as the column of M(z) corresponding to the

73

final state s then the range ’ G (V), of V is identical to the

F 9
response interval, Rz , defined in (4. 1. 5). One can easily show

using induction on the tape length that

since the symbol matrices cover any probability vector. The quasi-
definite condition requires the length L(Rz) of each response
interval Rz to approach 0 as lg(z) becomes infinite. Since each
response interval contains at least one response point, it follows

that @ has no isolated cut points.

Exarmile 4.1. 3.: Consider the quasi-definite probabilistic automaton

 

Q (S, ? , 81’ 52) defined over the alphabet 2 = {0, 1} and on

the state set S = (31, 32} by the symbol matrices

We apply the theorem to show that 0) has no isolated cut points if
0 < o. < l .

T
Let V 2 (v1 , v2) be any probability vector with vl _<_ v2 ,

and consider the ranges

Q(M(O) V) = [v1, OV1+(1-C1)V2]
and

@(M(1)V) = [(iv1 +(1 -C1)V2, v2]

74

which clearly covers V. Similarly, if vl > v2 then these symbol
matrices again cover V . Consequently, the theorem implies that

G has no isolated cut points.

4. 2. Topological Approach

The topological approach of this section gives a neat View
of the tape acceptance behavior of probabilistic automata. The
isolated cut-point problem is viewed in a more enlightening setting.
The results of this section focus on the isolated cut point problems

for an arbitrary probabilistic automaton.

R esponse Model

 

Let @ be an arbitrary probabilistic automaton defined

over the alphabet 2 = {01, a 0'0 } and on the state set
2

S = { 31’ 82’ ..., sn} . We introduce a "response model" Q

2, ...,

for G) to characterize the response of all tapes in 2* in terms
of the response of tapes in 2n"l . The central idea, which
stemmed from a recent paper by J. W. Carlyle [3], brings into
consideration the constraints imposed by the finite state assumption.

We recall that the response of G) to a tape x 6 2* is defined by

the bilinear form

rp(x) = no M(x) OF

Consider any collection of 2m (m > n) tapes

x1, x2,...,x and x1,xz,...,x

m m

from 2* . Collect the response of G: to these tapes into a

“response matrix" P defined as follows:

 

75

x1 X2

"" '1

1 rp(x1 £1) rp(xl £2) . . . rp(x1 32m)
x2 rp(xZJ—cl) rp(xzxz) . . . rp(xZ-xm)
P = . . . (4. 2.1)

 

 

X rp(xm;1) rp(xm;2) . . . rp(xm;m)-J

mL.

The response matrix P has the following factorization,
P = O H (4. 2. 2)

where Q and H are (mxn) and (nxm) matrices respectively

defined by

D
II
PH
{0
D
II

Tl’o M(xi)}

and

II
{I}
CC
)1

H M(xj) OF}

It follows from the factorization (4. 2. 2) that the rank of the response
matrix P is no larger than n . Hence, the determinant of P,

denoted by det (P) ; is zero, independent of the tapes selected.

Definition 4. 2.1.: The rank of the response model Q is defined to

 

be the largest rank r (E n) of the response matrix P that can be

n-l. * If r = n then a is said to have maximum

generated from 2
rank.

Now consider one collection of 2r tapes

x1,x2,...,x and x1,x2, ...,xr

 

31‘ -
If follows from a theorem of Carlyle [3 ] that the tapes in 2*1 1

determine the rank of the response model.

76

in 2n-1 such that the rank of the response matrix P is r. Let

k and k- be defined as

Max
1‘ :1515 r{1g(xi)}
and
— Max —
k = 1:1: r{1g(xi)} '
ConSider two tapes X62k+1 and X6 Ek+l and form the response

matrix P partitioned as

;1 x2 ... 2?. 3:
x1 I-rp(xlx1 rp(xl_2) . . . rp(xl Er) I rp(x1 ;)1
x2 rp(xe-l) rp(x2;2) . . . rp(xzxr) : rp(xZ-x)
I
P = ° ' l (4.2.3)
. I
l
_ I _
xr rp(x x1) rp(x x2) . rp(xrxr) I rp(xrx)
____.._—. ________ :__I____.J
x rp(x x1) rp(x x2) . rp(x XI) 1 rp(x x)
_ I .. o

 

 

We then observe that the response matrix P can be factored as

A B(§) 1 o A o I A'1 B(§)
P: :
C(x) D C(x)A-1 1 o (D-C(x)A-1B(;)) o 1

. -l .
Since A eXists. Hence, we have

77

1 _

det (P) = det(A) ° det(D - C(x)A- B(x)) = 0

Since D is a scalar and det(A) )f O, we have

D e rp(x ) e C(x)A-1B(x-) (4.2.4)

where lg(x 32) = k + k + 2 . Thus, the response of tapes in

2 can be determined in terms of the response of tapes in

k+E+2
zk+k+1 by (4. 2.4).
We define YN to be a set of response points, one for each
tape in 2

N,

YN = {rp(x) I x6 2N}
In a similar manner YN denotes the set of response points for
the tapes in 2N ,

YN = {rp(x) I xezN}

The bilinear form in (4. 2. 4) implies that Y

from Yk+k+1 . In general, the linear response transformation

k+k+2 can be determined

C(x)A-1 of (4. 2. 4) may be considered fixed by determining C(x)A-'l

for each tape x 6 2 . This yields a finite family of response (row)

k+1

vectors, (R = {C(x)A"1 I X6 2 , one for each tape in 2

k+1 } k+1 ’

called the response model. The response model, 6? :YN -’ YN+1 ,

for N: k + k + 1 ; defines the entire tape response of 63 recursively

 

by

YN+1={RXB(X)|Rxe(R , xesz}

for N _>_ k + F +1 2 L . We note that this response model can be

used efficiently to carry out the decision algorithm of Theorem 4.1.1.

78

Theorem 4. 2.1.: Each response vector Rx contained in the response

 

model 63 has unit row sum.

Proof: Consider the response matrix P partitioned as shown in

(4. Z. 3). Each response vector RX contained in (R is defined by

R = C(x) 14'1
x

which implie s that

C(x) = RxA

Consequently, if RX = [r1 r2 . . . rr] then we have

(r1 nO M(xl) + r2 nO M(XZ) + . . . + rr n0 M(xr) - nO M(x)) M(Xi) OF = 0

for each xi (i = 1, 2, . . ., r) . Since A"1 exists, it follows that
the vectors nO M(xi) (i = 1, 2, . . . , r) are linearly independent.
This implies that there exists a unique vector Rx = [r1 r.Z . . . rr]

such that

r1 no M(xl) + rZ nO M(xz) + . . . + rr no M(xr) = no M(x)

This in turn implies that Rx satisfies C(x) = RXA . Since the
vectors nO M(Xi) (i = l, 2, . . ., r) are stochastic, it follows that
Rx must have unit row sum. It may have, however, some negative
entries.

A simple example is given here to illustrate the essential

features of the response model.

79

Example 4.2.1.: Consider a probabilistic automaton 69 (S, 7? , 51’ 32)

defined over the alphabet 2 = {0, l} and on the state set S = {$1, 82}

by the symbol matrices,

51—:
O
O
y—a

M(O) =

.4412»
N...

 

 

 

 

Jul"
L

Choose x1 — 321 = O and x2 = 32.2 = l . The response matrix P in

(4.2.1) is defined for tapes x and E; in 22 as

 

 

 

 

o 1 E
o o 1 rp(O E5)
1 l —
P = 1 Z Z rp(l x)
x rp(x 0) rp(x 1) rp(x *)_I
where
r- _
O 1
A 1 1 . C(x) = [rp(x 0) rp(x 1)]
Z Z
.1
and BT(x) [rp(O 3:) rp(l '12)] . The response model

formed by determining for each tape x 6 22 , Rx = C(x)A'1 as

follows:

00

01

10

DO 5U 50 513

ll

C(OO)A'1
C(01)A'1
cuom‘1

C(11)A'l

[101
1011
[34131
31
13;)

80

The entire tape response of G) is given recursively by
YN+1 = {RX B(x) I RxeGK , xe EN_1}

for all N :3 where rp(x _) = RX B(;)
The response model for this example can be organized into
the following convenient matrix recurrence equation. Define the

partitioned matrices

p3

[B(00). B(OI). B(IO), Bun] .

F -

C(OO)A-1

C = ,and

C(10)A'1

L ...

I- _1"
C(01)A

cums.”l

 

 

Now if P4 = C1 P3 and P; = C2 P3 , then the response model is
given by .

C1[ P1 P1] = p1+1

CZIPi Pi'] = pi'+1 (i=4, 5,...)
where the matrices Pi+1 and Pi+1 contain the response points

for tapes in 2i+ The notation [ P1.l P1] denotes a partitioned

1.

matrix formed from Pi and Pi .

81

Pseudo-Closure (_Dperator

 

The setting for the following deve10pment is the probability

interval P1 = [ O, 1] . Let X denote a set of closed Y -neighborhoods

k

N( - , Y), one around each response point in Yk ,

Xk = {N(rp(x), Y) :X62k} .

Similarly, let Xk denote a set of Closed Y -neighborhoods N(°, Y) ,

one around each response point in Y

Xk = {N(rp(x), Y) :X6 2*} .

The "response Operator" CY : Yk -' Xk+1 , is defined by

cY<Yk) = c‘YONY‘k’w EMMY“). v) = x“1

for all k _>_ L = k + E+1 where C(YO)(Yk) = xk and N(ka), y) e xk+1 .

The important point to notice here is that the response operator
utilizes the response model a to generate Yk+l from Yk . It
then wraps Y -neighborhoods about the points in Yk+1 while retaining

all previously generated neighborhoods. The composite response

operator is defined recursively by

(:1; (YL) = cS‘HYL“) = C$-2(YL+2) = = C(Y

Consequently, the response operator has the following important

ne sting pr ope rty,

CIONYL) C C§1)(YL) c c, cI/k'INYL) C Cgk)(YL) C .

82

The following discussion centers on the response operator
and pertains to the solvability of the isolated cut—point problems
for an arbitrary probabilistic automaton. Let CY and CY +€
denote response Operators that enclose the response points with
Y and Y+6 closed neighborhoods respectively, where 6 is any
fixed positive number. We shall prove that if one can effectively
decide whether or not CrYl(YL) C CYN+€(YL) for all n _>_ N ,
then the isolated cut-point problems are recursively solvable. A
cursory examination of the continuity of the linear response model

indicates that such an effective procedure does in fact exist. If

this is true, then the following conjecture would follow:

Conjecture Z. 4. 2.: For an arbitrary probabilistic automaton, there

 

exists a finite integer N such that one can decide from CYN+€(YL)
that a given cut point X is either Y -isolated or not (Y +6)-isolated
for any 6 > O .

The following discussion pertains to the above conjecture.
Case 1: We first observe that if there exists an integer N such that

C$(YL) C CIYWYL) for all n _>_ N then we can decide that

a) X 6 C$I(YL) is not Y -isolated

b) ,X 6 PI - C$(YL) is Y -isolated.

Case 2: If no finite integer N exists such that C:(YL) C CIYWYL)

for n _>_ N, then consider the set

B = PI-Cn(YL) .
n Y

Let 61 be any fixed positive number. If on the one hand, there

83

exists for all ii an integer N such that the measure of B - B
l n n+Nl

satisfies m(Bn - B then there is a finite integer N

>
n+Nl) - 61 ’
such that BN = (I) . Consequently, the automaton has no Y -isolated

cut points. If on the other hand, no integer N1 exists such that

m(Bn - B then we have alimiting situation. Let CY and

>
n+Nl) — E1

CY +6 denote response Operators that enclose the response points

with Y and Y+6 closed neighborhoods respectively. Now stop

the closure process when

C$(YL) C CYN+€(YL) for all n 3 N.

This will be true for some finite integer N, since no integer Nl

. _ > > .
eXists such that m(Bn Bn+Nl) _ 6 for any 6 O . In this case,
one can decide that

$I+€(YL) is Y -isolated

b) )\ 6 C$I+€(YL) is not (Y +6)-isolated.

a) XKC

V. CONCLUSIONS

In this chapter we summarize the important original results
Obtained. Chapter 2 contains a necessary and sufficient condition
for strict stability (Theorem 2. 3. l). A bounded algorithm is given
in Section 3. 3 which efficiently solves the strict stability problem
for an arbitrary probabilistic automaton. The algorithm is
particularly suited for a digital computer. It requires only logical
Operations and does not require the multiplication Of matrices.
Theorem 2. 4. 2 gives a sufficient condition for tape acceptance
stability without requiring the automaton to be strictly stable. This
result is essentially a regional stability result, since it gives a
bound on the size of perturbations that can be permitted without
causing tape acceptance instability.

Chapter 3 contains zero-stability results for NQD automata
in terms of their cyclic and algebraic structures. Section 3. 2
contains some fundamental properties of the cyclic structure Of
NQD automata. These results led to the algorithm given in
Section 3. 3 for locating all prime cycling tapes for an arbitrary
probabilistic automaton. Section 3. 4 refines the cyclic structure,
so that the minimal nonzero entry in a matrix product does not
approach zero prior to attaining the scrambling condition. Theorem
3. 5. 1 gives sufficient conditions for zero-stability in terms of the
prime cyclic conditions. The method Of proof is similar to that Of
Theorem 2. 3. 1. The crucial point is to prevent the minimal nonzero

entry from having a zero limit prior to attaining the scrambling

84

85

condition. The conditions of the theorem are easily checked by
locating the prime cyclic tapes with the algorithm given in Section
3. 3. This result has some important implications in the design Of
o-stable probabilistic computers that have a cyclic behavior. It
points out how one can design a nontrivial cyclic probabilistic
computer that is zero-stable. Section 3. 6 contains some zero-
stability results in terms Of the algebraic structure of NQD
automata. Theorem 3. 6. 4 proves that any zero-reset automaton

is zero-stable. Essentially, a zero-reset automaton consists of

a finite number Of quasi-definite subautomata. Each subautomaton
can compute independently, and each can communicate with any
other by means Of the permutation structure. This structure gives
a powerful computing ability to zero-reset automaton. The develop-
ment in Section 3. 6 proved that a monoid set 1 Of (n x n)
stochastic matrices with identity element U is a group, if each
element P 6,2 has a corresponding reset element Pr 6 I

such that P Prfcb U . This result is important in deciding whether
or not a given set Of stochastic matrices is a group. Since group
automata are subsumed by zero-reset automata, we also know

that group automata are zero-stable.

Chapter 4 gives several tests to decide the isolated cut-
point problems. Theorem 4. l. l proves for quasi-definite automata
that the isolated cut-point problems can be decided with a bounded
experiment. Theorem 4. l. 2 gives sufficient conditions to imply
that a quasi-definite automaton has no isolated cut points. Section

4. 2 gives a neat view Of tape response Of an arbitrary probabilistic

86

automaton. A response model is introduced which defines the entire
response of a probabilistic automaton in terms of the response Of
the automaton to short tapes. A pseudo-closure Operator is defined
in terms of this response model which encloses the cut points which
are not isolated. Conjecture 2. 4. 2 then indicates that the isolated
cut-point problems can be decided in terms Of this closure Operator
with finite experiments.

Let us conclude by pointing out some interesting and still
open problems which merit further investigation. The bound given
on the lengths Of a prime cycling tape was Obtained in Lemma 3. 2. 2
without placing any restrictions on the size Of the alphabet. It
would be important to see if one could lower the given bound by
considering the constraints imposed by the alphabet size. The
crucial idea in Theorem 3. 5.1 is to prevent the minimal nonzero
entry from having a zero limit prior to attaining the scrambling
condition. It would be important to investigate extensions Of this
idea to a larger class of cyclic automata. The algebraic structure
Of NQD automata developed in Section 3. 6 has some interesting
implications on the computing behavior Of NQD automata. It seems
very attractive to pursue this approach to more general algebraic
systems. The development on the isolated cut—point problem
indicates, that it is reasonable to investigate certain properties Of
the response model that would decide the isolated cut-point problems.
Finally, we express the need for a procedure for designing a
probabilistic automaton to accept a given set of tapes, T(CP , )t ),

with respect to the cut point )\ .

10.

11.

12.

13.

14.

R EF ER ENC ES

Arbib, M. A. (1967). Realization of Stochastic Systems.
Amer. Math. Stat., June 1967.

 

Caianiello, E. R. (1966). Automata Theory. Academic Press,
New York, 309-313.

Carlyle, J. W. (1964). On the External Probability Structure
Of Finite State Channels. Information and Control, 7, 385-
397 (1964).

Cleave, J. P. (1962). The Synthesis Of Finite State Homogeneous
Markov Chains. Cybernetics, 5, 38-47.

 

Cox, D. R. and Miller, H. D. (1965). ”The Theory of Stochastic
Processes, " Wiley, New York.

Debrew, G. and Herstein, I. N. (1953). Nonnegative Square
Matrices. Econometrica, 21, 597-607.

 

Frame, J. S. (1964). Matrix Functions and Applications.
IEEE SpectrumJ March-July Issues.

 

Karlins, S. (1966). "A First Course in Stochastic Processes."
Academic Press, New York.

Kemeny, J. G. and Snell, J. L. (1960). "Finite Markov Chains,”
Van Nostrand, Princeton, New Jersey.

Kilmer, W. L. and McCulloch, W. S. (1964). Towards a Theory
of the Reticular Formations. Proc. IEEE 5th Nat'l Symposium
on Human Factors in Electronics, May, 19671.

 

Page, C. V. (1965). Equivalences Between Probabilistic Machines.
Technical Report 03105-41 -T, University of Michigan, November,
1965.

 

Paz, A. (1963). Ph. D. Thesis at the Israel Institute of Technology
on Probabilistic Automata.

Rabin, M. O. (1963). Probabilistic Automata. Information and
Control, 6, 230-245.

 

Rabin, M. O., and Scott, D. (1959). Finite Automata and Their
Decision Problems. IBMJ Res. Develop., 3, 114-125.

 

87

88

15. Rosenblatt, M. (1965). Products Of Independent Identically
Distributed Stochastic Matrices. Journal Of Math. Anal.

and A221" 11, 1-10 (1965).

 

16. Wolfowitz, J. (1963). Products Of Indecomposable Aperiodic
Stochastic Matrices. Proc. Amer. Math. Soc., 733-737.