3 Search Results for "Reggio, Luca"

Document
DOI: 10.4230/LIPIcs.CSL.2024.27
Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth

Authors: Eva Fluck, Tim Seppelt, and Gian Luca Spitzer

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment 𝖢^k_q, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio (2021) proved that two graphs satisfy the same 𝖢^k_q-sentences if and only if they are homomorphism indistinguishable over the class 𝒯^k_q of graphs admitting a k-pebble forest cover of depth q. Their proof builds on the categorical framework of game comonads developed by Abramsky, Dawar, and Wang (2017). We reprove their result using elementary techniques inspired by Dvořák (2010). Using these techniques we also give a characterisation of guarded counting logic. Our main focus, however, is to provide a graph theoretic analysis of the graph class 𝒯^k_q. This allows us to separate 𝒯^k_q from the intersection of the graph class TW_{k-1}, that is graphs of treewidth less or equal k-1, and TD_q, that is graphs of treedepth at most q if q is sufficiently larger than k. We are able to lift this separation to the semantic separation of the respective homomorphism indistinguishability relations. A part of this separation is to prove that the class TD_q is homomorphism distinguishing closed, which was already conjectured by Roberson (2022).
Cite as

Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fluck_et_al:LIPIcs.CSL.2024.27,
  author =	{Fluck, Eva and Seppelt, Tim and Spitzer, Gian Luca},
  title =	{{Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello 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.CSL.2024.27},
  URN =		{urn:nbn:de:0030-drops-196704},
  doi =		{10.4230/LIPIcs.CSL.2024.27},
  annote =	{Keywords: Treewidth, treedepth, homomorphism indistinguishability, counting first-order logic}
}
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.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-dev.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}
}
  • Refine by Author
  • 2 Reggio, Luca
  • 1 Abramsky, Samson
  • 1 Fluck, Eva
  • 1 Gehrke, Mai
  • 1 Petrisan, Daniela
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Finite Model Theory
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Categorical semantics

  • Refine by Keyword
  • 1 Stone duality and Stone-Cech compactification
  • 1 Treewidth
  • 1 Vietoris hyperspace construction
  • 1 algebraic language theory beyond the regular setting
  • 1 bisimulation
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2021
  • 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