2 Search Results for "Mendling, Jan"

Document
DOI: 10.4230/LIPIcs.STACS.2025.19
The Complexity of Learning LTL, CTL and ATL Formulas

Authors: Benjamin Bordais, Daniel Neider, and Rajarshi Roy

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider the problem of learning temporal logic formulas from examples of system behavior. Learning temporal properties has crystallized as an effective means to explain complex temporal behaviors. Several efficient algorithms have been designed for learning temporal formulas. However, the theoretical understanding of the complexity of the learning decision problems remains largely unexplored. To address this, we study the complexity of the passive learning problems of three prominent temporal logics, Linear Temporal Logic (LTL), Computation Tree Logic (CTL) and Alternating-time Temporal Logic (ATL) and several of their fragments. We show that learning formulas with unbounded occurrences of binary operators is NP-complete for all of these logics. On the other hand, when investigating the complexity of learning formulas with bounded occurrences of binary operators, we exhibit discrepancies between the complexity of learning LTL, CTL and ATL formulas (with a varying number of agents).
Cite as

Benjamin Bordais, Daniel Neider, and Rajarshi Roy. The Complexity of Learning LTL, CTL and ATL Formulas. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bordais_et_al:LIPIcs.STACS.2025.19,
  author =	{Bordais, Benjamin and Neider, Daniel and Roy, Rajarshi},
  title =	{{The Complexity of Learning LTL, CTL and ATL Formulas}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.19},
  URN =		{urn:nbn:de:0030-drops-228441},
  doi =		{10.4230/LIPIcs.STACS.2025.19},
  annote =	{Keywords: Temporal logic, passive learning, complexity}
}
Document
DOI: 10.4230/DagRep.8.8.67
Blockchain Technology for Collaborative Information Systems (Dagstuhl Seminar 18332)

Authors: Marlon Dumas, Richard Hull, Jan Mendling, and Ingo Weber

Published in: Dagstuhl Reports, Volume 8, Issue 8 (2019)

Abstract
Blockchain technology enables an evolving set of parties to maintain a safe, permanent, and tamper-proof ledger of transactions without a central authority. This technology opens manifold opportunities to redesign business-to-business collaborations, while bringing about numerous challenges. These opportunities and challenges were discussed in the Dagstuhl Seminar 18332 "Blockchain Technology for Collaborative Information Systems". This report documents the program and the outcomes of the seminar.
Cite as

Marlon Dumas, Richard Hull, Jan Mendling, and Ingo Weber. Blockchain Technology for Collaborative Information Systems (Dagstuhl Seminar 18332). In Dagstuhl Reports, Volume 8, Issue 8, pp. 67-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{dumas_et_al:DagRep.8.8.67,
  author =	{Dumas, Marlon and Hull, Richard and Mendling, Jan and Weber, Ingo},
  title =	{{Blockchain Technology for Collaborative Information Systems (Dagstuhl Seminar 18332)}},
  pages =	{67--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{8},
  editor =	{Dumas, Marlon and Hull, Richard and Mendling, Jan and Weber, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.8.67},
  URN =		{urn:nbn:de:0030-drops-102361},
  doi =		{10.4230/DagRep.8.8.67},
  annote =	{Keywords: Blockchain, BPM, Business Collaboration, Commerce, Logistics, Business Models (economic), Smart Contracts, Privacy}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2019

  • Refine by Author
  • 1 Bordais, Benjamin
  • 1 Dumas, Marlon
  • 1 Hull, Richard
  • 1 Mendling, Jan
  • 1 Neider, Daniel
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 1 Theory of computation

  • Refine by Keyword
  • 1 BPM
  • 1 Blockchain
  • 1 Business Collaboration
  • 1 Business Models (economic)
  • 1 Commerce
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact