Arrow Research search

Author name cluster

Chris Barrett

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

CSL Conference 2023 Conference Paper

The Functional Machine Calculus II: Semantics

  • Chris Barrett
  • Willem Heijltjes
  • Guy McCusker

The Functional Machine Calculus (FMC), recently introduced by the second author, is a generalization of the lambda-calculus which may faithfully encode the effects of higher-order mutable store, I/O and probabilistic/non-deterministic input. Significantly, it remains confluent and can be simply typed in the presence of these effects. In this paper, we explore the denotational semantics of the FMC. We have three main contributions: first, we argue that its syntax - in which both effects and lambda-calculus are realised using the same syntactic constructs - is semantically natural, corresponding closely to the structure of a Scott-style domain theoretic semantics. Second, we show that simple types confer strong normalization by extending Gandy’s proof for the lambda-calculus, including a small simplification of the technique. Finally, we show that the typed FMC (without considering the specifics of encoded effects), modulo an appropriate equational theory, is a complete language for Cartesian closed categories.

Details

IJCAI Conference 2007 Conference Paper

  • Chris Barrett
  • H. B. Hunt III
  • M. V. Marathe
  • S. S. Ravi
  • D. J. Rosenkrantz
  • R. E. Stearns
  • M. Thakur

Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also point out the implications of our results on other computational models such as Hopfield networks, communicating finite state machines and systolic arrays.

PDF Details