DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.60

Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity

Authors: Juha Kontinen, Max Sandström, and Jonni Virtema

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We introduce and develop a set-based semantics for asynchronous TeamLTL. We consider two canonical logics in this setting: the extensions of TeamLTL by the Boolean disjunction and by the Boolean negation. We relate the new semantics with the original semantics based on multisets and establish one of the first positive complexity theoretic results in the temporal team semantics setting. In particular we show that both logics enjoy normal forms that can be utilised to obtain results related to expressivity and complexity (decidability) of the new logics.

Cite as

Juha Kontinen, Max Sandström, and Jonni Virtema. Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kontinen_et_al:LIPIcs.MFCS.2023.60,
  author =	{Kontinen, Juha and Sandstr\"{o}m, Max and Virtema, Jonni},
  title =	{{Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.60},
  URN =		{urn:nbn:de:0030-drops-185949},
  doi =		{10.4230/LIPIcs.MFCS.2023.60},
  annote =	{Keywords: Hyperproperties, Linear Temporal Logic, Team Semantics}
}

Search Results

Documents authored by Sandström, Max

Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message