13 Search Results for "Abramsky, Samson"

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-dev.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.MFCS.2022.75
Cohomology in Constraint Satisfaction and Structure Isomorphism

Authors: Adam Ó Conghaile

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

Abstract
Constraint satisfaction (CSP) and structure isomorphism (SI) are among the most well-studied computational problems in Computer Science. While neither problem is thought to be in PTIME, much work is done on PTIME approximations to both problems. Two such historically important approximations are the k-consistency algorithm for CSP and the k-Weisfeiler-Leman algorithm for SI, both of which are based on propagating local partial solutions. The limitations of these algorithms are well-known – k-consistency can solve precisely those CSPs of bounded width and k-Weisfeiler-Leman can only distinguish structures which differ on properties definable in C^k. In this paper, we introduce a novel sheaf-theoretic approach to CSP and SI and their approximations. We show that both problems can be viewed as deciding the existence of global sections of presheaves, ℋ_k(A,B) and ℐ_k(A,B) and that the success of the k-consistency and k-Weisfeiler-Leman algorithms correspond to the existence of certain efficiently computable subpresheaves of these. Furthermore, building on work of Abramsky and others in quantum foundations, we show how to use Čech cohomology in ℋ_k(A,B) and ℐ_k(A,B) to detect obstructions to the existence of the desired global sections and derive new efficient cohomological algorithms extending k-consistency and k-Weisfeiler-Leman. We show that cohomological k-consistency can solve systems of equations over all finite rings and that cohomological Weisfeiler-Leman can distinguish positive and negative instances of the Cai-Fürer-Immerman property over several important classes of structures.
Cite as

Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 75:1-75:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oconghaile:LIPIcs.MFCS.2022.75,
  author =	{\'{O} Conghaile, Adam},
  title =	{{Cohomology in Constraint Satisfaction and Structure Isomorphism}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{75:1--75:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.75},
  URN =		{urn:nbn:de:0030-drops-168738},
  doi =		{10.4230/LIPIcs.MFCS.2022.75},
  annote =	{Keywords: constraint satisfaction problems, finite model theory, descriptive complexity, rank logic, Weisfeiler-Leman algorithm, cohomology}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.115
Arboreal Categories and Resources

Authors: Samson Abramsky and Luca Reggio

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We introduce arboreal categories, which have an intrinsic process structure, allowing dynamic notions such as bisimulation and back-and-forth games, and resource notions such as number of rounds of a game, to be defined. These are related to extensional or "static" structures via arboreal covers, which are resource-indexed comonadic adjunctions. These ideas are developed in a very general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling, Ehrenfeucht-Fraïssé and modal bisimulation games recently introduced in [Abramsky et al., 2017; S. Abramsky and N. Shah, 2018; Abramsky and Shah, 2021] are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.
Cite as

Samson Abramsky and Luca Reggio. Arboreal Categories and Resources. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.ICALP.2021.115,
  author =	{Abramsky, Samson and Reggio, Luca},
  title =	{{Arboreal Categories and Resources}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{115:1--115:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.115},
  URN =		{urn:nbn:de:0030-drops-141845},
  doi =		{10.4230/LIPIcs.ICALP.2021.115},
  annote =	{Keywords: factorisation system, embedding, comonad, coalgebra, open maps, bisimulation, game, resources, relational structures, finite model theory}
}
Document
DOI: 10.4230/LIPIcs.CSL.2021.5
The Logic of Contextuality

Authors: Samson Abramsky and Rui Soares Barbosa

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Abstract
Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.
Cite as

Samson Abramsky and Rui Soares Barbosa. The Logic of Contextuality. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.CSL.2021.5,
  author =	{Abramsky, Samson and Barbosa, Rui Soares},
  title =	{{The Logic of Contextuality}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.5},
  URN =		{urn:nbn:de:0030-drops-134394},
  doi =		{10.4230/LIPIcs.CSL.2021.5},
  annote =	{Keywords: partial Boolean algebras, contextuality, exclusivity principles, Kochen-Specker paradoxes, tensor product}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.2
Relating Structure and Power: Comonadic Semantics for Computational Resources

Authors: Samson Abramsky and Nihil Shah

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

Abstract
Combinatorial games are widely used in finite model theory, constraint satisfaction, modal logic and concurrency theory to characterize logical equivalences between structures. In particular, Ehrenfeucht-Fraïssé games, pebble games, and bisimulation games play a central role. We show how each of these types of games can be described in terms of an indexed family of comonads on the category of relational structures and homomorphisms. The index k is a resource parameter which bounds the degree of access to the underlying structure. The coKleisli categories for these comonads can be used to give syntax-free characterizations of a wide range of important logical equivalences. Moreover, the coalgebras for these indexed comonads can be used to characterize key combinatorial parameters: tree-depth for the Ehrenfeucht-Fraïssé comonad, tree-width for the pebbling comonad, and synchronization-tree depth for the modal unfolding comonad. These results pave the way for systematic connections between two major branches of the field of logic in computer science which hitherto have been almost disjoint: categorical semantics, and finite and algorithmic model theory.
Cite as

Samson Abramsky and Nihil Shah. Relating Structure and Power: Comonadic Semantics for Computational Resources. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.CSL.2018.2,
  author =	{Abramsky, Samson and Shah, Nihil},
  title =	{{Relating Structure and Power: Comonadic Semantics for Computational Resources}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{2:1--2: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.2},
  URN =		{urn:nbn:de:0030-drops-96698},
  doi =		{10.4230/LIPIcs.CSL.2018.2},
  annote =	{Keywords: Finite model theory, combinatorial games, Ehrenfeucht-Fra\"{i}ss\'{e} games, pebble games, bisimulation, comonads, coKleisli category, coalgebras of a comonad}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.9
Minimum Quantum Resources for Strong Non-Locality

Authors: Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
We analyse the minimum quantum resources needed to realise strong non-locality, as exemplified e.g. by the classical GHZ construction. It was already known that no two-qubit system, with any finite number of local measurements, can realise strong non-locality. For three-qubit systems, we show that strong non-locality can only be realised in the GHZ SLOCC class, and with equatorial measurements. However, we show that in this class there is an infinite family of states which are pairwise non LU-equivalent that realise strong non-locality with finitely many measurements. These states have decreasing entanglement between one qubit and the other two, necessitating an increasing number of local measurements on the latter.
Cite as

Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield. Minimum Quantum Resources for Strong Non-Locality. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.TQC.2017.9,
  author =	{Abramsky, Samson and Barbosa, Rui Soares and Car\`{u}, Giovanni and de Silva, Nadish and Kishida, Kohei and Mansfield, Shane},
  title =	{{Minimum Quantum Resources for Strong Non-Locality}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.9},
  URN =		{urn:nbn:de:0030-drops-85822},
  doi =		{10.4230/LIPIcs.TQC.2017.9},
  annote =	{Keywords: strong non-locality, maximal non-locality, quantum resources, three-qubit states}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.35
The Quantum Monad on Relational Structures

Authors: Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction, and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.
Cite as

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata. The Quantum Monad on Relational Structures. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.MFCS.2017.35,
  author =	{Abramsky, Samson and Barbosa, Rui Soares and de Silva, Nadish and Zapata, Octavio},
  title =	{{The Quantum Monad on Relational Structures}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.35},
  URN =		{urn:nbn:de:0030-drops-81290},
  doi =		{10.4230/LIPIcs.MFCS.2017.35},
  annote =	{Keywords: non-local games, quantum computation, monads}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.211
Contextuality, Cohomology and Paradox

Authors: Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
Contextuality is a key feature of quantum mechanics that provides an important non-classical resource for quantum information and computation. Abramsky and Brandenburger used sheaf theory to give a general treatment of contextuality in quantum theory [New Journal of Physics 13 (2011) 113036]. However, contextual phenomena are found in other fields as well, for example database theory. In this paper, we shall develop this unified view of contextuality. We provide two main contributions: firstly, we expose a remarkable connection between contexuality and logical paradoxes; secondly, we show that an important class of contextuality arguments has a topological origin. More specifically, we show that "All-vs-Nothing" proofs of contextuality are witnessed by cohomological obstructions.
Cite as

Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield. Contextuality, Cohomology and Paradox. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 211-228, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.CSL.2015.211,
  author =	{Abramsky, Samson and Soares Barbosa, Rui and Kishida, Kohei and Lal, Raymond and Mansfield, Shane},
  title =	{{Contextuality, Cohomology and Paradox}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{211--228},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.211},
  URN =		{urn:nbn:de:0030-drops-54166},
  doi =		{10.4230/LIPIcs.CSL.2015.211},
  annote =	{Keywords: Quantum mechanics, contextuality, sheaf theory, cohomology, logical paradoxes}
}
Document
DOI: 10.4230/DagRep.5.1.197
Coalgebraic Semantics of Reflexive Economics (Dagstuhl Seminar 15042)

Authors: Samson Abramsky, Alexander Kurz, Pierre Lescanne, and Viktor Winschel

Published in: Dagstuhl Reports, Volume 5, Issue 1 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15042 "Coalgebraic Semantics of Reflexive Economics".
Cite as

Samson Abramsky, Alexander Kurz, Pierre Lescanne, and Viktor Winschel. Coalgebraic Semantics of Reflexive Economics (Dagstuhl Seminar 15042). In Dagstuhl Reports, Volume 5, Issue 1, pp. 197-206, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{abramsky_et_al:DagRep.5.1.197,
  author =	{Abramsky, Samson and Kurz, Alexander and Lescanne, Pierre and Winschel, Viktor},
  title =	{{Coalgebraic Semantics of Reflexive Economics (Dagstuhl Seminar 15042)}},
  pages =	{197--206},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{1},
  editor =	{Abramsky, Samson and Kurz, Alexander and Lescanne, Pierre and Winschel, Viktor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.1.197},
  URN =		{urn:nbn:de:0030-drops-50398},
  doi =		{10.4230/DagRep.5.1.197},
  annote =	{Keywords: Programming language semantics, Coalgebra, Category theory, Economics, Epistemic game theory}
}
Document
DOI: 10.4230/DagRep.4.4.49
Categorical Methods at the Crossroads (Dagstuhl Perspectives Workshop 14182)

Authors: Samson Abramsky, John C. Baez, Fabio Gadducci, and Viktor Winschel

Published in: Dagstuhl Reports, Volume 4, Issue 4 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14182 "Perspectives Workshop: Categorical Methods at the Crossroads". The aim of the meeting was to investigate the potential of category theory as a paradigm for mathematical modeling and applied science. The envisaged application areas included computation, physics, biology, complex systems, social and cognitive science and linguistics. Many of these areas were indeed tackled in the variety of topics dealt with during the workshop. Each working day followed the same structure: two survey lectures during the morning, followed by two/three shorter talks in the afternoon, and closed by a working group session. During these sessions the attendants split into several groups according to the main thematic areas that had been identified on the first day. Both surveys and talks are reported in the "Overview" section of the report, while a wrap-up of the discussions that occurred inside the working groups is reported in the "Working Groups" section.
Cite as

Samson Abramsky, John C. Baez, Fabio Gadducci, and Viktor Winschel. Categorical Methods at the Crossroads (Dagstuhl Perspectives Workshop 14182). In Dagstuhl Reports, Volume 4, Issue 4, pp. 49-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{abramsky_et_al:DagRep.4.4.49,
  author =	{Abramsky, Samson and Baez, John C. and Gadducci, Fabio and Winschel, Viktor},
  title =	{{Categorical Methods at the Crossroads (Dagstuhl Perspectives Workshop 14182)}},
  pages =	{49--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{4},
  editor =	{Abramsky, Samson and Baez, John C. and Gadducci, Fabio and Winschel, Viktor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.4.49},
  URN =		{urn:nbn:de:0030-drops-46189},
  doi =		{10.4230/DagRep.4.4.49},
  annote =	{Keywords: Category theory, concurrency, economics, game theory, logics, quantum computing, semantics}
}
Document
DOI: 10.4230/DagRep.3.2.45
Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071)

Authors: Samson Abramsky, Juha Kontinen, Jouko Väänanen, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 3, Issue 2 (2013)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 13071 "Dependence Logic: Theory and Applications". The seminar brought together researchers from different areas such as mathematical logic, quantum mechanics, statistics, social choice theory, and theoretical computer science. A key objective of the seminar was to bring together, for the first time, researchers working in dependence logic and in the application areas so that they can communicate state-of-the-art advances and embark on a systematic interaction.
Cite as

Samson Abramsky, Juha Kontinen, Jouko Väänanen, and Heribert Vollmer. Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071). In Dagstuhl Reports, Volume 3, Issue 2, pp. 45-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{abramsky_et_al:DagRep.3.2.45,
  author =	{Abramsky, Samson and Kontinen, Juha and V\"{a}\"{a}nanen, Jouko and Vollmer, Heribert},
  title =	{{Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071)}},
  pages =	{45--54},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{2},
  editor =	{Abramsky, Samson and Kontinen, Juha and V\"{a}\"{a}nanen, Jouko and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.2.45},
  URN =		{urn:nbn:de:0030-drops-40127},
  doi =		{10.4230/DagRep.3.2.45},
  annote =	{Keywords: Data structures, Algorithms, Complexity, Verification, Logic}
}
Document
DOI: 10.4230/DagRep.2.8.99
Information Flow and Its Applications (Dagstuhl Seminar 12352)

Authors: Samson Abramsky, Jean Krivine, and Michael W. Mislove

Published in: Dagstuhl Reports, Volume 2, Issue 8 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12352 "Information Flow and Its Applications". This seminar brought together mathematicians, computer scientists, physicists and researchers from related disciplines such as computational biology who are working on problems concerning information and information flow.
Cite as

Samson Abramsky, Jean Krivine, and Michael W. Mislove. Information Flow and Its Applications (Dagstuhl Seminar 12352). In Dagstuhl Reports, Volume 2, Issue 8, pp. 99-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{abramsky_et_al:DagRep.2.8.99,
  author =	{Abramsky, Samson and Krivine, Jean and Mislove, Michael W.},
  title =	{{Information Flow and Its Applications (Dagstuhl Seminar 12352)}},
  pages =	{99--112},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{8},
  editor =	{Abramsky, Samson and Krivine, Jean and Mislove, Michael W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.8.99},
  URN =		{urn:nbn:de:0030-drops-37866},
  doi =		{10.4230/DagRep.2.8.99},
  annote =	{Keywords: Information flow; semantics of computation; quantum computing; systems biology; information theory; informatics}
}
Document
DOI: 10.4230/DagSemProc.04351.14
Discrete classical vs. continuous quantum data in abstract quantum mechanics

Authors: Samson Abramsky and Bob Coecke

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
``Quantum'' stands for for the concepts (both operational and formal) which had to be added to classical physics in order to understand otherwise unexplainable observed phenomena such as the structure of the spectral lines in atomic spectra. While the basic part of classical mechanics deals with the (essentially) reversible dynamics, quantum required adding the notions of ``measurement'' and (possibly non-local) ``correlations'' to the discussion. Crucially, all this comes with a ``probabilistic calculus''. The corresponding mathematical formalism was considered to have reached maturity in [von Neumann 1932], but there are some manifest problems with that formalism: (i) While measurements are applied to physical systems, application of their formal counterpart (i.e. a self-adjoint linear operator) to the vector representing that state of the system in no way reflects how the state changes during the act of measurement. Analogously, the composite of two self-adjoint operators has no physical significance while in practice measurements can be effectuated sequentially. More generally, the formal types in von Neumann's formalism do not reflect the nature of the corresponding underlying concept at all! (ii) Part of the problem regarding the measurements discussed above is that in the von Neumann formalism there is no place for storage, manipulation and exchange of the classical data obtained from measurements. Protocols such as quantum teleportation involving these cannot be given a full formal description. (iii) The behavioral properties of quantum entanglement which for example enable continuous data exchange using only finitary communication are hidden in the formalism. In [Abramsky and Coecke 2004] we addressed all these problems, and in addition provided a purely categorical axiomatization of quantum mechanics. The concepts of the abstract quantum mechanics are formulated relative to a strongly compact closed category with biproducts (of which the category FdHilb of finite dimensional Hilbert spaces and linear maps is an example). Preparations, measurements, either destructive or not, classical data exchange are all morphisms in that category, and their types fully reflect their kinds. Correctness properties of standard quantum protocols can be abstractly proven. Surprisingly, in this seemingly purely qualitative setting even the quantitative Born rule arises, that is the rule which tells you how to calculate the probabilities. Indeed, each such category has as endomorphism Hom of the tensor unit an abelian semiring of `scalars', and a special subset of these scalars will play the role of weights: each scalar induces a natural transformation which propagates through physical processes, and when a `state' undergoes a `measurement', the composition of the corresponding morphisms gives rise to the weight. Hence the probabilistic weights live within the category of processes. J. von Neumann. Mathematische Grundlagen der Quantenmechanik. Springer-Verlag (1932). English translation in Mathematical Foundations of Quantum Mechanics. Princeton University Press (1955). S. Abramsky and B. Coecke. A categorical semantics of quantum protocols. In the proceedings of LiCS'04 (2004). An extended version is available at arXiv:quant-ph/0402130 A more reader friendly version entitled `Quantum information flow, concretely, abstractly' is at http://www.vub.ac.be/CLEA/Bob/Papers/QPL.pdf
Cite as

Samson Abramsky and Bob Coecke. Discrete classical vs. continuous quantum data in abstract quantum mechanics. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:DagSemProc.04351.14,
  author =	{Abramsky, Samson and Coecke, Bob},
  title =	{{Discrete classical vs. continuous quantum data in abstract quantum mechanics}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.14},
  URN =		{urn:nbn:de:0030-drops-1316},
  doi =		{10.4230/DagSemProc.04351.14},
  annote =	{Keywords: Category theory , strong compact closure , quantum information-flow}
}
  • Refine by Author
  • 12 Abramsky, Samson
  • 3 Barbosa, Rui Soares
  • 2 Kishida, Kohei
  • 2 Mansfield, Shane
  • 2 Winschel, Viktor
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Finite Model Theory
  • 2 Theory of computation → Categorical semantics
  • 1 Mathematics of computing
  • 1 Theory of computation → Logic
  • 1 Theory of computation → Modal and temporal logics
  • Show More...

  • Refine by Keyword
  • 3 Category theory
  • 2 bisimulation
  • 2 cohomology
  • 2 comonads
  • 2 contextuality
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 2 2013
  • 2 2015
  • 2 2018
  • 2 2021
  • 2 2022
  • Show More...

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 Imprint Privacy Contact