License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2016.24
URN: urn:nbn:de:0030-drops-59982
Go to the corresponding LIPIcs Volume Portal

Laird, James

Weighted Relational Models for Mobility

LIPIcs-FSCD-2016-24.pdf (0.5 MB)


We investigate operational and denotational semantics for
computational and concurrent systems with mobile names which capture
their computational properties. For example, various properties of
fixed networks, such as shortest or longest path, transition
probabilities, and secure data flows, correspond to the ``sum'' in a
semiring of the weights of paths through the network: we aim to model
networks with a dynamic topology in a similar way. Alongside rich
computational formalisms such as the lambda-calculus, these can be
represented as terms in a calculus of solos with weights from a
complete semiring $R$, so that reduction associates a weight in R to
each reduction path.

Taking inspiration from differential nets, we develop a denotational
semantics for this calculus in the category of sets and R-weighted
relations, based on its differential and compact-closed structure, but
giving a simple, syntax-independent representation of terms as
matrices over R. We show that this corresponds to the sum in R of
the values associated to its independent reduction paths, and that our
semantics is fully abstract with respect to the observational
equivalence induced by sum-of-paths evaluation.

BibTeX - Entry

  author =	{James Laird},
  title =	{{Weighted Relational Models for  Mobility}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Delia Kesner and Brigitte Pientka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-59982},
  doi =		{10.4230/LIPIcs.FSCD.2016.24},
  annote =	{Keywords: Concurrency, Mobility, Denotational Semantics}

Keywords: Concurrency, Mobility, Denotational Semantics
Collection: 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)
Issue Date: 2016
Date of publication: 17.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI