Lune

LICS2023Top-tier venue

The Logic of Prefixes and Suffixes is Elementary under Homogeneity*

Dario Della Monica, Angelo Montanari, Gabriele Puppis, Pietro Sala

Abstract

In this paper, we study the finite satisfiability problem for the logic BE under the homogeneity assumption. BE is the cornerstone of Halpern and Shoham's interval temporal logic, and features modal operators corresponding to the prefix (a.k.a. "Begins") and suffix (a.k.a. "Ends") relations on intervals. In terms of complexity, BE lies in between the "Chop" logic C, whose satisfiability problem is known to be non-elementary, and the PSpace-complete interval logic D of the sub-interval (a.k.a. "During") relation. BE was shown to be ExpSpace-hard, and the only known satisfiability procedure is primitive recursive, but not elementary. Our contribution consists of tightening the complexity bounds of the satisfiability problem for BE, by proving it to be ExpSpace-complete. We do so by devising an equi-satisfiable normal form with boundedly many nested modalities. The normalization technique resembles Scott's quantifier elimination, but it turns out to be much more involved due to the limitations enforced by the homogeneity assumption.

  • We acknowledge the support from the 2022 Italian INdAM-GNCS project "Elaborazione del Linguaggio Naturale e Logica Temporale per la Formalizzazione di Testi", ref. no. CUP E55F22000270001. We would also like to thank Alberto Molinari, Laura Bozzelli, and Adriano Peron for many useful discussions. Finally, Angelo Montanari would like to acknowledge the work done on the problem, together with Gabriele Puppis and Pietro Sala, when he was on leave at LaBRI in Bordeaux.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Complexity of Safety and coSafety Fragments of Linear Temporal LogicAlessandro Artale, Luca Geatti, Nicola Gigante, Andrea Mazzullo et al.AAAI 2023 · 11 citations
  2. Generalizing Non-punctuality for Timed Temporal Logic with Freeze QuantifiersShankara Narayanan Krishna, Khushraj Madnani, Manuel Mazo Jr., Paritosh K. PandyaFM 2021 · 3 citations
  3. On the Computational Power of Extensional ESOManuel Bodirsky, Santiago Guzmán-ProLICS 2026
  4. Intermediate problems in modular circuits satisfiabilityPawel M. Idziak, Piotr Kawalek, Jacek KrzaczkowskiLICS 2020 · 8 citations
  5. Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally HardJorge Fandinno, Markus HecherAAAI 2021 · 10 citations
Dusk over the sea between two cliffs drawn in fine vertical lines