# On the expressive power of first-order boolean functions in PCF

@article{Pucella2001OnTE, title={On the expressive power of first-order boolean functions in PCF}, author={Riccardo Pucella and P. Panangaden}, journal={Theor. Comput. Sci.}, year={2001}, volume={266}, pages={543-567} }

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…

#### Topics from this paper

#### 2 Citations

Hypergraphs and Degrees of Parallelism: A Completeness Result

- Mathematics, Computer ScienceFoSSaCS
- 2004

The notion of timed hypergraph morphism is introduced and it is shown that if there exists a timed morphism from H f to H g then f is PCF-definable relatively to g.

Embedding the Pi-Calculus into a Concurrent Functional Programming Language

- 2019

Correctness of program transformations and translations in concurrent programming is the focus of our research. In this case study the relation of the synchronous pi-calculus and a core language of…

#### References

SHOWING 1-10 OF 25 REFERENCES

Relative definability of boolean functions via hypergraphs

- Computer Science, MathematicsTheor. Comput. Sci.
- 2002

It is shown that the sup-semilattice of degrees has a categorical counterpart: a category of hypergraphs such that every object "represents" a monotone boolean function; finite coproducts in this category correspond to lubs of degrees.

Degrees of Parallelism in the Continuous Type Hierarchy

- Computer Science, MathematicsTheor. Comput. Sci.
- 1997

A degree of parallelism is an equivalence class of Scott-continuous functions which are relatively definable by each other with respect to the language PCF (a paradigmatic sequential language). We…

On Representation of Sequential and Parallel Functions

- Mathematics, Computer ScienceMFCS
- 1975

This paper investigates the problem of comparative power of different sequential and parallel functions with respect to composition and recursion and answers the question of D.Scott concerning the power of his Logic for Computable Functions.

Sequentiality in an Extensional Framework

- Computer Science, MathematicsInf. Comput.
- 1994

We present a cartesian closed category of dI-domains with coherence and strongly stable functions which provides a new model of PCF, where terms are interpreted by functions and where, at first…

Categorical Combinators, Sequential Algorithms, and Functional Programming

- Computer ScienceProgress in Theoretical Computer Science
- 1993

The new edition covers new results, and introduces new connections, as suggested by the following non-exhaustive fist of keywords: confluence properties of categorical combinators, explicit substitutions, control operations, linear logic, geometry of interaction, strong stability.

Modularity and expressibility for nets of relations

- Mathematics, Computer ScienceActa Informatica
- 1998

The central objective of this paper is the characterization of modular classes of relations and hence indirectly the set of dataflow nets without anomalies and the interesting role played by stable functions introduced by Berry.

Mechanizing Logical Relations

- Computer ScienceMFPS
- 1993

We give an algorithm for deciding whether there exists a definable element of a finite model of an applied typed lambda calculus that passes certain tests, in the special case when all the constants…

LCF Considered as a Programming Language

- Computer ScienceTheor. Comput. Sci.
- 1977

Study of connections between denotational and operational semantics for a simple programming language based on LCF finds that by allowing further parallel facilities, every r.e. element of the fully abstract semantics becomes definable, thus characterising the programming language, up to interdefinability, from the set of elements of the domains of the semantics.

Sequentiality and strong stability

- Mathematics, Computer Science[1991] Proceedings Sixth Annual IEEE Symposium on Logic in Computer Science
- 1991

It is shown that Kahn-Plotkin sequentiality can be expressed by a preservation property similar to stability and that this kind of generalized stability can be extended to higher order. The main…

Fully Abstract Models of Typed lambda-Calculi

- Computer ScienceTheor. Comput. Sci.
- 1977

It is shown that under certain conditions there exists, for an extended typed λ-calculus, a unique fully abstract model.