A classic result by Stockmeyer [16] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic, notably for formulas that make use of the so-called chop operator. Such an operator can indeed be interpreted as the inverse of the concatenation operation on regular languages, and this correspondence enables reductions between non-emptiness of star-free generalized regular expressions and satisfiability of formulas of the interval temporal logic of the chop operator under the homogeneity assumption [5]. In this paper, we study the complexity of the satisfiability problem for a suitable weakening of the chop interval temporal logic, that can be equivalently viewed as a fragment of Halpern and Shoham interval logic featuring the operators B, for “begins”, corresponding to the prefix relation on pairs of intervals, and D, for “during”, corresponding to the infix relation. The homogeneous models of the considered logic naturally correspond to languages defined by restricted forms of regular expressions, that use union, complementation, and the inverses of the prefix and infix relations.

On a temporal logic of prefixes and infixes / Bozzelli, L.; Montanari, A.; Peron, A.; Sala, P.. - 170:(2020), pp. 1-14. (Intervento presentato al convegno 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 tenutosi a Prague, Czech Republic nel August 24-28, 2020) [10.4230/LIPIcs.MFCS.2020.21].

On a temporal logic of prefixes and infixes

Bozzelli L.;Montanari A.;Peron A.;
2020

Abstract

A classic result by Stockmeyer [16] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic, notably for formulas that make use of the so-called chop operator. Such an operator can indeed be interpreted as the inverse of the concatenation operation on regular languages, and this correspondence enables reductions between non-emptiness of star-free generalized regular expressions and satisfiability of formulas of the interval temporal logic of the chop operator under the homogeneity assumption [5]. In this paper, we study the complexity of the satisfiability problem for a suitable weakening of the chop interval temporal logic, that can be equivalently viewed as a fragment of Halpern and Shoham interval logic featuring the operators B, for “begins”, corresponding to the prefix relation on pairs of intervals, and D, for “during”, corresponding to the infix relation. The homogeneous models of the considered logic naturally correspond to languages defined by restricted forms of regular expressions, that use union, complementation, and the inverses of the prefix and infix relations.
2020
On a temporal logic of prefixes and infixes / Bozzelli, L.; Montanari, A.; Peron, A.; Sala, P.. - 170:(2020), pp. 1-14. (Intervento presentato al convegno 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 tenutosi a Prague, Czech Republic nel August 24-28, 2020) [10.4230/LIPIcs.MFCS.2020.21].
File in questo prodotto:
File Dimensione Formato  
LIPIcs-MFCS-2020-21(1).pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 522.57 kB
Formato Adobe PDF
522.57 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/828978
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact