Search Results

Documents authored by Linker, Sven

Document
DOI: 10.4230/LIPIcs.MFCS.2021.72
Finite Models for a Spatial Logic with Discrete and Topological Path Operators

Authors: Sven Linker, Fabio Papacchini, and Michele Sevegnani

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
This paper analyses models of a spatial logic with path operators based on the class of neighbourhood spaces, also called pretopological or closure spaces, a generalisation of topological spaces. For this purpose, we distinguish two dimensions: the type of spaces on which models are built, and the type of allowed paths. For the spaces, we investigate general neighbourhood spaces and the subclass of quasi-discrete spaces, which closely resemble graphs. For the paths, we analyse the cases of quasi-discrete paths, which consist of an enumeration of points, and topological paths, based on the unit interval. We show that the logic admits finite models over quasi-discrete spaces, both with quasi-discrete and topological paths. Finally, we prove that for general neighbourhood spaces, the logic does not have the finite model property, either for quasi-discrete or topological paths.
Cite as

Sven Linker, Fabio Papacchini, and Michele Sevegnani. Finite Models for a Spatial Logic with Discrete and Topological Path Operators. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{linker_et_al:LIPIcs.MFCS.2021.72,
  author =	{Linker, Sven and Papacchini, Fabio and Sevegnani, Michele},
  title =	{{Finite Models for a Spatial Logic with Discrete and Topological Path Operators}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{72:1--72:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.72},
  URN =		{urn:nbn:de:0030-drops-145120},
  doi =		{10.4230/LIPIcs.MFCS.2021.72},
  annote =	{Keywords: spatial logic, topology, finite models}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.66
Analysing Spatial Properties on Neighbourhood Spaces

Authors: Sven Linker, Fabio Papacchini, and Michele Sevegnani

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We present a bisimulation relation for neighbourhood spaces, a generalisation of topological spaces. We show that this notion, path preserving bisimulation, preserves formulas of the spatial logic SLCS. We then use this preservation result to show that SLCS cannot express standard topological properties such as separation and connectedness. Furthermore, we compare the bisimulation relation with standard modal bisimulation and modal bisimulation with converse on graphs and prove it coincides with the latter.
Cite as

Sven Linker, Fabio Papacchini, and Michele Sevegnani. Analysing Spatial Properties on Neighbourhood Spaces. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{linker_et_al:LIPIcs.MFCS.2020.66,
  author =	{Linker, Sven and Papacchini, Fabio and Sevegnani, Michele},
  title =	{{Analysing Spatial Properties on Neighbourhood Spaces}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.66},
  URN =		{urn:nbn:de:0030-drops-127352},
  doi =		{10.4230/LIPIcs.MFCS.2020.66},
  annote =	{Keywords: spatial logic, topology, bisimulation}
}
Document
DOI: 10.4230/DagRep.9.10.95
Analysis of Autonomous Mobile Collectives in Complex Physical Environments (Dagstuhl Seminar 19432)

Authors: Mario Gleirscher, Anne E. Haxthausen, Martin Leucker, and Sven Linker

Published in: Dagstuhl Reports, Volume 9, Issue 10 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19432 "Analysis of Autonomous Mobile Collectives in Complex Physical Environments". Our working hypothesis for this seminar was that for systems of such complexity and criticality, the trustworthy certification and the successful operation in society will strongly benefit from the coordinated application of several rigorous engineering methods and formal analysis techniques. In this context, we discussed the state-of-the-art based on the working example of a Smart Farm. Our aim was to understand the practical challenges and the capabilities and limitations of recent formal modelling and analysis techniques when tackling these challenges, and to initiate a special research community on the verification of autonomous collectives.
Cite as

Mario Gleirscher, Anne E. Haxthausen, Martin Leucker, and Sven Linker. Analysis of Autonomous Mobile Collectives in Complex Physical Environments (Dagstuhl Seminar 19432). In Dagstuhl Reports, Volume 9, Issue 10, pp. 95-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{gleirscher_et_al:DagRep.9.10.95,
  author =	{Gleirscher, Mario and Haxthausen, Anne E. and Leucker, Martin and Linker, Sven},
  title =	{{Analysis of Autonomous Mobile Collectives in Complex Physical Environments (Dagstuhl Seminar 19432)}},
  pages =	{95--116},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{9},
  number =	{10},
  editor =	{Gleirscher, Mario and Haxthausen, Anne E. and Leucker, Martin and Linker, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.10.95},
  URN =		{urn:nbn:de:0030-drops-118579},
  doi =		{10.4230/DagRep.9.10.95},
  annote =	{Keywords: autonomous collectives, control engineering, formal verification, hybrid systems, uncertainty and risk}
}
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