Abstract/Details

UNIQUENESS OF SOLUTION OF FIXED POINT EQUATIONS IN REGULAR EXTENSIONS OF ITERATIVE ALGEBRAS

PARISI-PRESICCE, FRANCESCO. 
 University of Connecticut ProQuest Dissertations Publishing,  1981. 8116739.

Abstract (summary)

Two approaches to the semantics of programming languages using fixed points have been investigated for a number of years.

The first approach deals with least fixed points of continuous mappings defined on complete posets and it has been extensively studied by D. Scott, M. Nivat and J. W. Thatcher, among others.

The second approach, based on the existence and uniqueness of fixed points of certain maps, was introduced by C. C. Elgot.

The two approaches were compared by J. Tiuryn, who proved the existence of extensions of algebras with the unique fixed point property (iterative algebras) to ordered algebras with the least fixed point property (regular algebras), extensions preserving the fixed point solutions.

Given an iterative algebra A, the construction of the extension is carried out by considering the algebra R(,(SIGMA))(A) of all (SIGMA)(A)-trees of finite index and defining on it two successive equivalence relations, =(,A) and =(omega)(,1) . A* = R(,(SIGMA))(A)/=(,A) and A(,R) = A*/=(omega)(,1) are obtained using the two relations: A(,R) is the sought extension of A, which coincides with A* whenever the extension is "faithful", that is obtained without collapsing elements of the carrier A.

It had been conjectured that both A* and A(,R) are again iterative algebras.

My dissertation shows that A* is again iterative, while J. Tiuryn has constructed an iterative algebra A whose regular extension A(,R) is not iterative.

The positive answer provides us with a method for extending iterative algebras to iterative regular algebras, where every nontrivial algebraic system of fixed point equations has a unique solution which can furthermore be generated by taking the least upper bound of an increasing sequence of successive approximations.

The dissertation also extends this result to a more general situation.

Given an iterative algebra A, let K(,1) be a congruence relation on(, )

R(,(SIGMA))(A), the (SIGMA)-algebra of all totally defined regular trees on (SIGMA)(A). Let

r = (r(,1),...,r(,n)) and s = (s(,1),...,s(,n)) and define

K(,2) = {(q{r},q{s}) : q(ELEM)R(,(SIGMA))(X(,n)),(r(,i),s(,i))(ELEM)K(,1) for i = 1,...,n}.

Theorem. If R(,(SIGMA))(A)/K(,1) is iterative, then R(,(SIGMA))(A)/K(,2) is iterative.

Indexing (details)


Subject
Mathematics
Classification
0405: Mathematics
Identifier / keyword
Pure sciences
Title
UNIQUENESS OF SOLUTION OF FIXED POINT EQUATIONS IN REGULAR EXTENSIONS OF ITERATIVE ALGEBRAS
Author
PARISI-PRESICCE, FRANCESCO
Number of pages
112
Degree date
1981
School code
0056
Source
DAI-B 42/02, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9798661951472
University/institution
University of Connecticut
University location
United States -- Connecticut
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8116739
ProQuest document ID
303128940
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/303128940/abstract