6 Search Results for "Russo, Alessandra"

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/OASIcs.ICLP.2018.12
Learning Commonsense Knowledge Through Interactive Dialogue

Authors: Benjamin Wu, Alessandra Russo, Mark Law, and Katsumi Inoue

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)

Abstract
One of the most difficult problems in Artificial Intelligence is related to acquiring commonsense knowledge - to create a collection of facts and information that an ordinary person should know. In this work, we present a system that, from a limited background knowledge, is able to learn to form simple concepts through interactive dialogue with a user. We approach the problem using a syntactic parser, along with a mechanism to check for synonymy, to translate sentences into logical formulas represented in Event Calculus using Answer Set Programming (ASP). Reasoning and learning tasks are then automatically generated for the translated text, with learning being initiated through question and answering. The system is capable of learning with no contextual knowledge prior to the dialogue. The system has been evaluated on stories inspired by the Facebook's bAbI's question-answering tasks, and through appropriate question and answering is able to respond accurately to these dialogues.
Cite as

Benjamin Wu, Alessandra Russo, Mark Law, and Katsumi Inoue. Learning Commonsense Knowledge Through Interactive Dialogue. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{wu_et_al:OASIcs.ICLP.2018.12,
  author =	{Wu, Benjamin and Russo, Alessandra and Law, Mark and Inoue, Katsumi},
  title =	{{Learning Commonsense Knowledge Through Interactive Dialogue}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{12:1--12:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.12},
  URN =		{urn:nbn:de:0030-drops-98780},
  doi =		{10.4230/OASIcs.ICLP.2018.12},
  annote =	{Keywords: Commonsense Reasoning, Answer Set Programming, Event Calculus, Inductive Logic Programming}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2012.15
Predicate Invention in Inductive Logic Programming

Authors: Duangtida Athakravi, Krysia Broda, and Alessandra Russo

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop

Abstract
The ability to recognise new concepts and incorporate them into our knowledge is an essential part of learning. From new scientific concepts to the words that are used in everyday conversation, they all must have at some point in the past, been invented and their definition defined. In this position paper, we discuss how a general framework for predicate invention could be made, by reasoning about the problem at the meta-level using an appropriate notion of top theory in inductive logic programming.
Cite as

Duangtida Athakravi, Krysia Broda, and Alessandra Russo. Predicate Invention in Inductive Logic Programming. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 15-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{athakravi_et_al:OASIcs.ICCSW.2012.15,
  author =	{Athakravi, Duangtida and Broda, Krysia and Russo, Alessandra},
  title =	{{Predicate Invention in Inductive Logic Programming}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{15--21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.15},
  URN =		{urn:nbn:de:0030-drops-37596},
  doi =		{10.4230/OASIcs.ICCSW.2012.15},
  annote =	{Keywords: Predicate invention, Inductive logic programming, Machine learning}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.106
An Inductive Approach for Modal Transition System Refinement

Authors: Dalal Alrajeh, Jeff Kramer, Alessandra Russo, and Sebastian Uchitel

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
Modal Transition Systems (MTSs) provide an appropriate framework for modelling software behaviour when only a partial specification is available. A key characteristic of an MTS is that it explicitly models events that a system is required to provide and is proscribed from exhibiting, and those for which no specification is available, called maybe events. Incremental elaboration of maybe events into either required or proscribed events can be seen as a process of MTS refinement, resulting from extending a given partial specification with more information about the system behaviour. This paper focuses on providing automated support for computing strong refinements of an MTS with respect to event traces that describe required and proscribed behaviours using a non-monotonic inductive logic programming technique. A real case study is used to illustrate the practical application of the approach.
Cite as

Dalal Alrajeh, Jeff Kramer, Alessandra Russo, and Sebastian Uchitel. An Inductive Approach for Modal Transition System Refinement. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 106-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{alrajeh_et_al:LIPIcs.ICLP.2011.106,
  author =	{Alrajeh, Dalal and Kramer, Jeff and Russo, Alessandra and Uchitel, Sebastian},
  title =	{{An Inductive Approach for Modal Transition System Refinement}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{106--116},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.106},
  URN =		{urn:nbn:de:0030-drops-31758},
  doi =		{10.4230/LIPIcs.ICLP.2011.106},
  annote =	{Keywords: Modal Transition Systems, Refinement, Inductive Logic Programming, Event Calculus}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.175
Multi-agent Confidential Abductive Reasoning

Authors: Jiefei Ma, Alessandra Russo, Krysia Broda, and Emil Lupu

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a global query they collaborate with each other to make correct inferences and hypothesis, whilst maintaining global constraints. Most collaborative reasoning systems operate on the assumption that agents can share or communicate any information they have. However, in application domains like multi-agent systems for healthcare or distributed software agents for security policies in coalition networks, confidentiality of knowledge is an additional primary concern. These agents are required to collaborately compute consistent answers for a query whilst preserving their own private information. This paper addresses this issue showing how this dichotomy between "open communication" in collaborative reasoning and protection of confidentiality can be accommodated. We present a general-purpose distributed abductive logic programming system for multi-agent hypothetical reasoning with confidentiality. Specifically, the system computes consistent conditional answers for a query over a set of distributed normal logic programs with possibly unbound domains and arithmetic constraints, preserving the private information within the logic programs. A case study on security policy analysis in distributed coalition networks is described, as an example of many applications of this system.
Cite as

Jiefei Ma, Alessandra Russo, Krysia Broda, and Emil Lupu. Multi-agent Confidential Abductive Reasoning. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 175-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{ma_et_al:LIPIcs.ICLP.2011.175,
  author =	{Ma, Jiefei and Russo, Alessandra and Broda, Krysia and Lupu, Emil},
  title =	{{Multi-agent Confidential Abductive Reasoning}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{175--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.175},
  URN =		{urn:nbn:de:0030-drops-31736},
  doi =		{10.4230/LIPIcs.ICLP.2011.175},
  annote =	{Keywords: Abductive Logic Programming, Coordination, Agents}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2010.54
Inductive Logic Programming as Abductive Search

Authors: Domenico Corapi, Alessandra Russo, and Emil Lupu

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract
We present a novel approach to non-monotonic ILP and its implementation called TAL (Top-directed Abductive Learning). TAL overcomes some of the completeness problems of ILP systems based on Inverse Entailment and is the first top-down ILP system that allows background theories and hypotheses to be normal logic programs. The approach relies on mapping an ILP problem into an equivalent ALP one. This enables the use of established ALP proof procedures and the specification of richer language bias with integrity constraints. The mapping provides a principled search space for an ILP problem, over which an abductive search is used to compute inductive solutions.
Cite as

Domenico Corapi, Alessandra Russo, and Emil Lupu. Inductive Logic Programming as Abductive Search. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 54-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{corapi_et_al:LIPIcs.ICLP.2010.54,
  author =	{Corapi, Domenico and Russo, Alessandra and Lupu, Emil},
  title =	{{Inductive Logic Programming as Abductive Search}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{54--63},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.54},
  URN =		{urn:nbn:de:0030-drops-25838},
  doi =		{10.4230/LIPIcs.ICLP.2010.54},
  annote =	{Keywords: Inductive Logic Programming, Abductive Logic Programming, Non-monotonic Reasoning}
}
  • Refine by Type
  • 6 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018
  • 1 2012
  • 2 2011
  • 1 2010

  • Refine by Author
  • 5 Russo, Alessandra
  • 2 Broda, Krysia
  • 2 Lupu, Emil
  • 1 Alrajeh, Dalal
  • 1 Athakravi, Duangtida
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Theory of computation

  • Refine by Keyword
  • 3 Inductive Logic Programming
  • 2 Abductive Logic Programming
  • 2 Event Calculus
  • 1 Agents
  • 1 Answer Set Programming
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact