Stephen Brookes

Chicago Journal of Theoretical (2003)

We present a denotational semantics based on action traces, for parallel programs which share mutable data and synchronize using resources and conditional critical regions. We introduce a...

Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...

We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.

Data sharing and crime reduction: The long and winding road. (2003)

Brookes, Stephen, Moss, Kate, Pease, Ken

The Crime and Disorder Act 1998 charges responsible authorities with devising and implementing strategies for community safety. Responsible authorities comprice police and local authorities working...

Controlling Effects (1999)

Controlling Effects (1999)

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

An Axiomatic Treatment of Partial Correctness and Deadlock in a Shared Variable Parallel Language, (1998)

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

Full Abstraction for a Shared Variable Parallel Language, (1998)

We give a semantically based axiomatic treatment of partial correctness and deadlock for an imperative shared variable parallel programming language. The Owicki-Gries proof methodology for this...

Sequential Functions on Indexed Domains and Full Abstraction for a Sub-Language of PCF, (1998)

We give a new denotational semantics for a shared variable parallel programming language and prove full abstraction: the semantics gives identical meanings to commands if and only if they induce the...

Brookes, Stephen, Geva, Shai

We present a general semantic framework of sequential functions on domains equipped with a parameterized notion of incremental sequential computation. Under the simplifying assumption that...

Idealized CSP: Combining Procedures with Communicating Processes (1998)

On the Kahn Principle and Fair Networks (1998)

Idealized CSP is a programming language combining simply typed, call-by-name procedures with asynchronous communicating processes. The language also generalizes Reynolds' Idealized Algol by adding...

On the Kahn Principle and Fair Networks (1998)

The Kahn Principle states that each node in an asynchronous deterministic network computes a continuous function from input histories to output histories, and the behavior of the network can be...

The Essence of Parallel ALGOL, (1997)

The Kahn Principle states that each node in an asynchronous deterministic network computes a continuous function from input histories to output histories, and the behavior of the network can be...

The Essence of Parallel Algol (1997)

We consider a parallel Algol-like language, combining procedures with shared variable parallelism. Procedures permit encapsulation of common parallel programming idioms. Local variables provide a way...

We consider a parallel Algol-like language, combining procedures with shared-variable parallelism. Procedures permit encapsulation of common parallel programming idioms. Local variables provide a way...

Parallel Algol (1997)

Circuit Semantics and Intensional Expressivity (1996)

We consider a parallel Algol-like language, combining procedures with shared-variable parallelism. Procedures permit encapsulation of common parallel programming idioms. Local variables provide a way...

Circuit Semantics and Intensional Expressivity (1996)

We introduce a new denotational semantics for functional programming languages and use it to reason about intensional aspects of programs. Circuit semantics associates a gate with each basic...

Circuit Semantics and Intensional Expressivity (1996)

We introduce a new denotational semantics for functional programming languages and use it to reason about intensional aspects of programs. Circuit semantics associates a gate with each basic...

We introduce a new denotational semantics for functional programming languages and use it to reason about intensional aspects of programs. Circuit semantics associates a gate with each basic...

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

Programming Language Expressiveness and Circuit Complexity (1996)

Many computational effects, such as exceptions, state, or nondeterminism, can be conveniently specified in terms of monads. We investigate a technique for uniformly adding arbitrary such effects to...

Denis Dancanet, Stephen Brookes

This paper is a continuation of the work begun in [5] on establishing relative intensional expressiveness results for programming languages. Language L 1 is intensionally more expressive than L 2 ,...

Programming Language Expressiveness and Circuit Complexity (1996)

Denis Dancanet, Stephen Brookes

This paper is a continuation of the work begun in [5] on establishing relative intensional expressiveness results for programming languages. Language L 1 is intensionally more expressive than L 2 ,...

Programming Language Expressiveness and Circuit Complexity (1996)

Denis Dancanet, Stephen Brookes

This paper is a continuation of the work begun in [5] on establishing relative intensional expressiveness results for programming languages. Language L 1 is intensionally more expressive than L 2 ,...

Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness (1995)

Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness (1995)

We call language L 1 intensionally more expressive than L 2 if there are functions which can be computed faster in L 1 than in L 2 . We study the intensional expressiveness of several languages: the...

Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness (1995)

We call language L 1 intensionally more expressive than L 2 if there are functions which can be computed faster in L 1 than in L 2 . We study the intensional expressiveness of several languages: the...

Sequential Functions on Indexed Domains and Full Abstraction for a Sub-language of PCF (1993)

We call language L 1 intensionally more expressive than L 2 if there are functions which can be computed faster in L 1 than in L 2 . We study the intensional expressiveness of several languages: the...

Monads and Comonads in Intensional Semantics (1993)

ion for a Sub-language of PCF Stephen Brookes Shai Geva April 1993 CMU-CS-93-163 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 To appear in Proceedings of Mathematical...

Stephen Brookes, Kathryn Van Stone

Kleisli categories over monads have been used in denotational semantics to describe functional languages using various notions of computations as values. Kleisli categories over comonads have also...

Full Abstraction for a Shared Variable Parallel Language (1993)

Stable and Sequential Functions on Scott domains (1992)

ion for a Shared Variable Parallel Language Stephen Brookes April 1993 CMU-CS-93-141 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 To appear in the Proceedings of the...

Towards a Theory of Parallel Algorithms on Concrete Data Structures (1992)

The search for a general semantic characterization of sequential functions is motivated by the full abstraction problem for sequential programming languages such as PCF. We present here some new...

Continuous Functions and Parallel Algorithms on Concrete Data Structures (1992)

Building on Kahn and Plotkin's theory of concrete data structures and sequential functions, Berry and Curien defined an intensional model of sequential algorithms between concrete data structures. In...

Computational Comonads and Intensional Semantics (1992)

We report progress in two closely related lines of research: the semantic study of sequentiality and parallelism, and the development of a theory of intensional semantics. We generalize Kahn and...

A Cartesian Closed Category of Parallel Algorithms between Scott Domains (1992)

We explore some foundational issues in the development of a theory of intensional semantics. A programming language may be given a variety of semantics, differing in the level of abstraction; one...