Search Results

Documents authored by Marsden, Dan

Document
DOI: 10.4230/LIPIcs.MFCS.2022.7
Comonadic semantics for hybrid logic

Authors: Samson Abramsky and Dan Marsden

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Hybrid logic is a widely-studied extension of basic modal logic, which corresponds to the bounded fragment of first-order logic. We study it from two novel perspectives: (1) We apply the recently introduced paradigm of comonadic semantics, which provides a new set of tools drawing on ideas from categorical semantics which can be applied to finite model theory, descriptive complexity and combinatorics. (2) We give a novel semantic characterization of hybrid logic in terms of invariance under disjoint extensions, a minimal form of locality. A notable feature of this result is that we give a uniform proof, valid for both the finite and infinite cases.
Cite as

Samson Abramsky and Dan Marsden. Comonadic semantics for hybrid logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.MFCS.2022.7,
  author =	{Abramsky, Samson and Marsden, Dan},
  title =	{{Comonadic semantics for hybrid logic}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-168055},
  doi =		{10.4230/LIPIcs.MFCS.2022.7},
  annote =	{Keywords: comonads, model comparison games, semantic characterizations, hybrid logic, bounded fragment}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.32
Quantitative Foundations for Resource Theories

Authors: Dan Marsden and Maaike Zwart

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
Considering resource usage is a powerful insight in the analysis of many phenomena in the sciences. Much of the current research on these resource theories focuses on the analysis of specific resources such quantum entanglement, purity, randomness or asymmetry. However, the mathematical foundations of resource theories are at a much earlier stage, and there has been no satisfactory account of quantitative aspects such as costs, rates or probabilities. We present a categorical foundation for quantitative resource theories, derived from enriched category theory. Our approach is compositional, with rich algebraic structure facilitating calculations. The resulting theory is parameterized, both in the quantities under consideration, for example costs or probabilities, and in the structural features of the resources such as whether they can be freely copied or deleted. We also achieve a clear separation of concerns between the resource conversions that are freely available, and the costly resources that are typically the object of study. By using an abstract categorical approach, our framework is naturally open to extension. We provide many examples throughout, emphasising the resource theoretic intuitions for each of the mathematical objects under consideration.
Cite as

Dan Marsden and Maaike Zwart. Quantitative Foundations for Resource Theories. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{marsden_et_al:LIPIcs.CSL.2018.32,
  author =	{Marsden, Dan and Zwart, Maaike},
  title =	{{Quantitative Foundations for Resource Theories}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.32},
  URN =		{urn:nbn:de:0030-drops-96996},
  doi =		{10.4230/LIPIcs.CSL.2018.32},
  annote =	{Keywords: Resource Theory, Enriched Category, Profunctor, Monad, Combinatorial Species, Multicategory, Operad, Bimodule}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2017.17
Custom Hypergraph Categories via Generalized Relations

Authors: Dan Marsden and Fabrizio Genovese

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

Abstract
Process theories combine a graphical language for compositional reasoning with an underlying categorical semantics. They have been successfully applied to fields such as quantum computation, natural language processing, linear dynamical systems and network theory. When investigating a new application, the question arises of how to identify a suitable process theoretic model. We present a conceptually motivated parameterized framework for the construction of models for process theories. Our framework generalizes the notion of binary relation along four axes of variation, the truth values, a choice of algebraic structure, the ambient mathematical universe and the choice of proof relevance or provability. The resulting categories are preorder-enriched and provide analogues of relational converse and taking graphs of maps. Our constructions are functorial in the parameter choices, establishing mathematical connections between different application domains. We illustrate our techniques by constructing many existing models from the literature, and new models that open up ground for further development.
Cite as

Dan Marsden and Fabrizio Genovese. Custom Hypergraph Categories via Generalized Relations. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{marsden_et_al:LIPIcs.CALCO.2017.17,
  author =	{Marsden, Dan and Genovese, Fabrizio},
  title =	{{Custom Hypergraph Categories via Generalized Relations}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.17},
  URN =		{urn:nbn:de:0030-drops-80494},
  doi =		{10.4230/LIPIcs.CALCO.2017.17},
  annote =	{Keywords: Process Theory, Categorical Compositional Semantics, Generalized Relations, Hypergraph Category, Compact Closed Category}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact