We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Exact and approximate algorithms for computing a second Hamiltonian cycle.

Deligkas, A. and Mertzios, G.B. and Spirakis, P.G. and Zamaraev, V. (2020) 'Exact and approximate algorithms for computing a second Hamiltonian cycle.', in 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Dagstuhl, Germany: Dagstuhl Publishing, 21:1-21:13. Leibniz International Proceedings in Informatics (LIPIcs).


A classic result by Stockmeyer [Stockmeyer, 1974] 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 [Halpern et al., 1983]. 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.

Item Type:Book chapter
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
File format - PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Argyrios Deligkas and George B. Mertzios and Paul G. Spirakis and Viktor Zamaraev; licensed under Creative Commons License CC-BY.
Date accepted:29 June 2020
Date deposited:05 August 2020
Date of first online publication:18 August 2020
Date first made open access:11 September 2020

Save or Share this output

Look up in GoogleScholar