On the Expressive Power of First-Order Boolean Functions in PCF

Details On the Expressive Power of First-Order Boolean Functions in PCF On the Expressive Power of First-Order Boolean Functions in PCF

2004-05-24

arxiv.org/abs/cs/0405085v1

Theoretical Computer Science 266(1-2), pp. 543-567, 2001

Computer Science

Programming Languages

23 pages

Scientific paper

Recent results of Bucciarelli show that the semilattice of degrees of parallelism of first-order boolean functions in PCF has both infinite chains and infinite antichains. By considering a simple subclass of Sieber's sequentiality relations, we identify levels in the semilattice and derive inexpressibility results concerning functions on different levels. This allows us to further explore the structure of the semilattice of degrees of parallelism: we identify semilattices characterized by simple level properties, and show the existence of new infinite hierarchies which are in a certain sense natural with respect to the levels.

Affiliated with

Also associated with

No associations

Rating

On the Expressive Power of First-Order Boolean Functions in PCF does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Expressive Power of First-Order Boolean Functions in PCF, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Expressive Power of First-Order Boolean Functions in PCF will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-711991