6 Search Results for "Gehrke, Mai"

Document
DOI: 10.4230/LIPIcs.FSCD.2024.14
Two-Dimensional Kripke Semantics I: Presheaves

Authors: G. A. Kavvos

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract
The study of modal logic has witnessed tremendous development following the introduction of Kripke semantics. However, recent developments in programming languages and type theory have led to a second way of studying modalities, namely through their categorical semantics. We show how the two correspond.
Cite as

G. A. Kavvos. Two-Dimensional Kripke Semantics I: Presheaves. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kavvos:LIPIcs.FSCD.2024.14,
  author =	{Kavvos, G. A.},
  title =	{{Two-Dimensional Kripke Semantics I: Presheaves}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{14:1--14:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.14},
  URN =		{urn:nbn:de:0030-drops-203438},
  doi =		{10.4230/LIPIcs.FSCD.2024.14},
  annote =	{Keywords: modal logic, categorical semantics, Kripke semantics, duality, open maps}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.9
Causal Unfoldings

Authors: Marc de Visme and Glynn Winskel

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
In the simplest form of event structure, a prime event structure, an event is associated with a unique causal history, its prime cause. However, it is quite common for an event to have disjunctive causes in that it can be enabled by any one of multiple sets of causes. Sometimes the sets of causes may be mutually exclusive, inconsistent one with another, and sometimes not, in which case they coexist consistently and constitute parallel causes of the event. The established model of general event structures can model parallel causes. On occasion however such a model abstracts too far away from the precise causal histories of events to be directly useful. For example, sometimes one needs to associate probabilities with different, possibly coexisting, causal histories of a common event. Ideally, the causal histories of a general event structure would correspond to the configurations of its causal unfolding to a prime event structure; and the causal unfolding would arise as a right adjoint to the embedding of prime in general event structures. But there is no such adjunction. However, a slight extension of prime event structures remedies this defect and provides a causal unfolding as a universal construction. Prime event structures are extended with an equivalence relation in order to dissociate the two roles, that of an event and its enabling; in effect, prime causes are labelled by a disjunctive event, an equivalence class of its prime causes. With this enrichment a suitable causal unfolding appears as a pseudo right adjoint. The adjunction relies critically on the central and subtle notion of extremal causal realisation as an embodiment of causal history.
Cite as

Marc de Visme and Glynn Winskel. Causal Unfoldings. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{devisme_et_al:LIPIcs.CALCO.2019.9,
  author =	{de Visme, Marc and Winskel, Glynn},
  title =	{{Causal Unfoldings}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.9},
  URN =		{urn:nbn:de:0030-drops-114376},
  doi =		{10.4230/LIPIcs.CALCO.2019.9},
  annote =	{Keywords: Event Structures, Parallel Causes, Causal Unfolding, Probability}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.13
Stone Duality and the Substitution Principle

Authors: Célia Borlido, Silke Czarnetzki, Mai Gehrke, and Andreas Krebs

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
In this paper we relate two generalisations of the finite monoid recognisers of automata theory for the study of circuit complexity classes: Boolean spaces with internal monoids and typed monoids. Using the setting of stamps, this allows us to generalise a number of results from algebraic automata theory as it relates to Büchi's logic on words. We obtain an Eilenberg theorem, a substitution principle based on Stone duality, a block product principle for typed stamps and, as our main result, a topological semidirect product construction, which corresponds to the application of a general form of quantification. These results provide tools for the study of language classes given by logic fragments such as the Boolean circuit complexity classes.
Cite as

Célia Borlido, Silke Czarnetzki, Mai Gehrke, and Andreas Krebs. Stone Duality and the Substitution Principle. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borlido_et_al:LIPIcs.CSL.2017.13,
  author =	{Borlido, C\'{e}lia and Czarnetzki, Silke and Gehrke, Mai and Krebs, Andreas},
  title =	{{Stone Duality and the Substitution Principle}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.13},
  URN =		{urn:nbn:de:0030-drops-77060},
  doi =		{10.4230/LIPIcs.CSL.2017.13},
  annote =	{Keywords: C-variety of languages, typed monoid, Boolean space with an internal monoid, substitution principle, semidirect product}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.112
The Schützenberger Product for Syntactic Spaces

Authors: Mai Gehrke, Daniela Petrisan, and Luca Reggio

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Starting from Boolean algebras of languages closed under quotients and using duality theoretic insights, we derive the notion of Boolean spaces with internal monoids as recognisers for arbitrary formal languages of finite words over finite alphabets. This leads to recognisers and syntactic spaces in a setting that is well-suited for applying tools from Stone duality as applied in semantics. The main focus of the paper is the development of topo-algebraic constructions pertinent to the treatment of languages given by logic formulas. In particular, using the standard semantic view of quantification as projection, we derive a notion of Schützenberger product for Boolean spaces with internal monoids. This makes heavy use of the Vietoris construction - and its dual functor - which is central to the coalgebraic treatment of classical modal logic. We show that the unary Schützenberger product for spaces yields a recogniser for the language of all models of the formula EXISTS x.phi(x), when applied to a recogniser for the language of all models of phi(x). Further, we generalise global and local versions of the theorems of Schützenberger and Reutenauer characterising the languages recognised by the binary Schützenberger product. Finally, we provide an equational characterisation of Boolean algebras obtained by local Schützenberger product with the one element space based on an Egli-Milner type condition on generalised factorisations of ultrafilters on words.
Cite as

Mai Gehrke, Daniela Petrisan, and Luca Reggio. The Schützenberger Product for Syntactic Spaces. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 112:1-112:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gehrke_et_al:LIPIcs.ICALP.2016.112,
  author =	{Gehrke, Mai and Petrisan, Daniela and Reggio, Luca},
  title =	{{The Sch\"{u}tzenberger Product for Syntactic Spaces}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{112:1--112:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.112},
  URN =		{urn:nbn:de:0030-drops-62474},
  doi =		{10.4230/LIPIcs.ICALP.2016.112},
  annote =	{Keywords: Stone duality and Stone-Cech compactification, Vietoris hyperspace construction, logic on words, algebraic language theory beyond the regular setting}
}
Document
DOI: 10.4230/DagRep.5.10.66
Duality in Computer Science (Dagstuhl Seminar 15441)

Authors: Mai Gehrke, Achim Jung, Victor Selivanov, and Dieter Spreen

Published in: Dagstuhl Reports, Volume 5, Issue 10 (2016)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 15441 `Duality in Computer Science'. This seminar served as a follow-up seminar to the seminar `Duality in Computer Science' (Dagstuhl Seminar 13311). In this seminar, we focused on applications of duality to semantics for probability in computation, to algebra and coalgebra, and on applications in complexity theory. A key objective of this seminar was to bring together researchers from these communities within computer science as well as from mathematics with the goal of uncovering commonalities, forging new collaborations, and sharing tools and techniques between areas based on their common use of topological methods and duality.
Cite as

Mai Gehrke, Achim Jung, Victor Selivanov, and Dieter Spreen. Duality in Computer Science (Dagstuhl Seminar 15441). In Dagstuhl Reports, Volume 5, Issue 10, pp. 66-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{gehrke_et_al:DagRep.5.10.66,
  author =	{Gehrke, Mai and Jung, Achim and Selivanov, Victor and Spreen, Dieter},
  title =	{{Duality in Computer Science (Dagstuhl Seminar 15441)}},
  pages =	{66--88},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{10},
  editor =	{Gehrke, Mai and Jung, Achim and Selivanov, Victor and Spreen, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.10.66},
  URN =		{urn:nbn:de:0030-drops-56999},
  doi =		{10.4230/DagRep.5.10.66},
  annote =	{Keywords: coalgebra, domain theory, probabilistic systems, recognizability, semantics of non-classical logics, Stone duality}
}
Document
DOI: 10.4230/DagRep.3.7.54
Duality in Computer Science (Dagstuhl Seminar 13311)

Authors: Mai Gehrke, Jean-Eric Pin, Victor Selivanov, and Dieter Spreen

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

Abstract
Duality allows one to move between the two worlds: the world of certain algebras of properties and a spacial world of individuals, thereby leading to a change of perspective that may, and often does, lead to new insights. Dualities have given rise to active research in a number of areas of theoretical computer science. Dagstuhl Seminar 13311 "Duality in Computer Science" was held to stimulate research in this area. This report collects the ideas that were presented and discussed during the course of the seminar.
Cite as

Mai Gehrke, Jean-Eric Pin, Victor Selivanov, and Dieter Spreen. Duality in Computer Science (Dagstuhl Seminar 13311). In Dagstuhl Reports, Volume 3, Issue 7, pp. 54-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{gehrke_et_al:DagRep.3.7.54,
  author =	{Gehrke, Mai and Pin, Jean-Eric and Selivanov, Victor and Spreen, Dieter},
  title =	{{Duality in Computer Science (Dagstuhl Seminar 13311)}},
  pages =	{54--73},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{7},
  editor =	{Gehrke, Mai and Pin, Jean-Eric and Selivanov, Victor and Spreen, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.7.54},
  URN =		{urn:nbn:de:0030-drops-43068},
  doi =		{10.4230/DagRep.3.7.54},
  annote =	{Keywords: Stone-Priestley duality, Point free topology, Infinite computations Exact real number computation, Computability in analysis, Hierarchies, Reducibilit Topological complexity, Domain theory, Semantics, Recognizability, Profinite topology}
}
  • Refine by Author
  • 4 Gehrke, Mai
  • 2 Selivanov, Victor
  • 2 Spreen, Dieter
  • 1 Borlido, Célia
  • 1 Czarnetzki, Silke
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Categorical semantics
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Modal and temporal logics

  • Refine by Keyword
  • 1 Boolean space with an internal monoid
  • 1 C-variety of languages
  • 1 Causal Unfolding
  • 1 Computability in analysis
  • 1 Domain theory
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2016
  • 1 2013
  • 1 2017
  • 1 2019
  • 1 2024

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