EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Expressivity of asynchronous TeamLTL and HyperLTL

Juha Kontinen, Max Sandström, Jonni Virtema

Acta Informatica · 2026-06 · 63 (2)

DOI: 10.1007/s00236-025-00514-x ↗

Kurz gefasst

Fachartikel in der Zeitschrift Acta Informatica, online erschienen am 26.05.2026. Verfasst von Juha Kontinen und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of Helsinki.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Linear temporal logic (LTL) is used in system verification to write formal specifications for reactive systems. However, some relevant properties, e.g. non-inference in information flow security, cannot be expressed in LTL. A class of such properties that has recently received ample attention is known as hyperproperties. There are two major streams in the research regarding capturing hyperproperties, namely hyperlogics, which extend LTL with trace quantifiers (HyperLTL), and logics that employ team semantics, extending truth to sets of traces. In this article we explore the relation between asynchronous LTL under set-based team semantics (TeamLTL) and HyperLTL. In particular we consider the extensions of TeamLTL with the Boolean disjunction and a fragment of the extension of TeamLTL with the Boolean negation, where the negation cannot occur in the right-hand side of the strong release operator or within the global operator. We show that TeamLTL extended with the Boolean disjunction is equi-expressive with the positive Boolean closure of HyperLTL restricted to one universal quantifier, while the right-downward closed fragment of TeamLTL extended with the Boolean negation is expressively equivalent with the Boolean closure of HyperLTL restricted to one universal quantifier. Furthermore, we show that formulae of TeamLTL extended with the Boolean negation are equivalent with sentences of first-order logic interpreted over grid structures.

Förderung

  • University of Helsinki

Zitieren

APA

Kontinen, J., Sandström, M., & Virtema, J. (2026). Expressivity of asynchronous TeamLTL and HyperLTL. Acta Informatica, 63(2). https://doi.org/10.1007/s00236-025-00514-x

Vancouver

Kontinen J, Sandström M, Virtema J. Expressivity of asynchronous TeamLTL and HyperLTL. Acta Informatica. 2026;63(2). doi:10.1007/s00236-025-00514-x

BibTeX
@article{Kontinen2026,
  author = {Kontinen, Juha and Sandström, Max and Virtema, Jonni},
  title = {Expressivity of asynchronous TeamLTL and HyperLTL},
  journal = {Acta Informatica},
  year = {2026},
  volume = {63},
  number = {2},
  doi = {10.1007/s00236-025-00514-x}
}
Kostenlos starten →