Search Results

Documents authored by Bresolin, Davide

Document
DOI: 10.4230/OASIcs.TIME.2026.3
The Σ-Chain Product: A Succinct Model of Automata (De)Composition

Authors: Roberto Borelli, Davide Bresolin, Luca Geatti, Angelo Montanari, and Matteo Zavatteri

Published in: OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)

Abstract
The cascade product is a fundamental construction in automata theory, enabling hierarchical composition of automata and playing a central role in decomposition results such as the Krohn–Rhodes theorem. However, its use is limited by the exponential size required to represent cascades, which stems from the fact that each component may depend on all preceding ones, leading to exponentially large alphabets. To address this issue, we introduce the Σ-chain product, a restricted variant in which each component depends only on the input alphabet and the component immediately preceding it. We show that Σ-chains achieve linear-size representations and can be exponentially more succinct than cascades. We prove that Σ-chains and cascades are expressively equivalent even when restricting the components to specific classes of automata, such as permutation-reset automata. As a consequence, we derive that a language is regular if and only if it is recognized by a Σ-chain of permutation-reset automata. Finally, we analyze structural properties of Σ-chains of reset automata, including a relation with well-known subclasses of star-free languages.
Cite as

Roberto Borelli, Davide Bresolin, Luca Geatti, Angelo Montanari, and Matteo Zavatteri. The Σ-Chain Product: A Succinct Model of Automata (De)Composition. In 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026). Open Access Series in Informatics (OASIcs), Volume 146, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{borelli_et_al:OASIcs.TIME.2026.3,
  author =	{Borelli, Roberto and Bresolin, Davide and Geatti, Luca and Montanari, Angelo and Zavatteri, Matteo},
  title =	{{The \Sigma-Chain Product: A Succinct Model of Automata (De)Composition}},
  booktitle =	{33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)},
  pages =	{3:1--3:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-448-2},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{146},
  editor =	{Orlandini, AndreA and Pinchinat, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.3},
  URN =		{urn:nbn:de:0030-drops-276999},
  doi =		{10.4230/OASIcs.TIME.2026.3},
  annote =	{Keywords: Automata, Cascade Product, Formal Languages, Krohn-Rhodes Theory}
}
Document
DOI: 10.4230/LIPIcs.TIME.2018.7
Extracting Interval Temporal Logic Rules: A First Approach

Authors: Davide Bresolin, Enrico Cominato, Simone Gnani, Emilio Muñoz-Velasco, and Guido Sciavicco

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract
Discovering association rules is a classical data mining task with a wide range of applications that include the medical, the financial, and the planning domains, among others. Modern rule extraction algorithms focus on static rules, typically expressed in the language of Horn propositional logic, as opposed to temporal ones, which have received less attention in the literature. Since in many application domains temporal information is stored in form of intervals, extracting interval-based temporal rules seems the natural choice. In this paper we extend the well-known algorithm APRIORI for rule extraction to discover interval temporal rules written in the Horn fragment of Halpern and Shoham's interval temporal logic.
Cite as

Davide Bresolin, Enrico Cominato, Simone Gnani, Emilio Muñoz-Velasco, and Guido Sciavicco. Extracting Interval Temporal Logic Rules: A First Approach. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bresolin_et_al:LIPIcs.TIME.2018.7,
  author =	{Bresolin, Davide and Cominato, Enrico and Gnani, Simone and Mu\~{n}oz-Velasco, Emilio and Sciavicco, Guido},
  title =	{{Extracting Interval Temporal Logic Rules: A First Approach}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.7},
  URN =		{urn:nbn:de:0030-drops-97728},
  doi =		{10.4230/LIPIcs.TIME.2018.7},
  annote =	{Keywords: Interval temporal logic, Horn fragment, Rule extraction}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.17
Fast(er) Reasoning in Interval Temporal Logic

Authors: Davide Bresolin, Emilio Muñoz-Velasco, and Guido Sciavicco

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
Clausal forms of logics are of great relevance in Artificial Intelligence, because they couple a high expressivity with a low complexity of reasoning problems. They have been studied for a wide range of classical, modal and temporal logics to obtain tractable fragments of intractable formalisms. In this paper we show that such restrictions can be exploited to lower the complexity of interval temporal logics as well. In particular, we show that for the Horn fragment of the interval logic AAbar (that is, the logic with the modal operators for Allen’s relations meets and met by) without diamonds the complexity lowers from NEXPTIME-complete to P-complete. We prove also that the tractability of the Horn fragments of interval temporal logics is lost as soon as other interval temporal operators are added to AAbar, in most of the cases.
Cite as

Davide Bresolin, Emilio Muñoz-Velasco, and Guido Sciavicco. Fast(er) Reasoning in Interval Temporal Logic. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bresolin_et_al:LIPIcs.CSL.2017.17,
  author =	{Bresolin, Davide and Mu\~{n}oz-Velasco, Emilio and Sciavicco, Guido},
  title =	{{Fast(er) Reasoning in Interval Temporal Logic}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.17},
  URN =		{urn:nbn:de:0030-drops-76782},
  doi =		{10.4230/LIPIcs.CSL.2017.17},
  annote =	{Keywords: Temporal Logic, Horn Fragments, Satisfiability, Complexity}
}

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