Skip to main content

Research Repository

Advanced Search

Exact and approximate algorithms for computing a second Hamiltonian cycle

Deligkas, A.; Mertzios, G.B.; Spirakis, P.G.; Zamaraev, V.

Exact and approximate algorithms for computing a second Hamiltonian cycle Thumbnail


Authors

A. Deligkas

P.G. Spirakis

V. Zamaraev



Contributors

Javier Esparza
Editor

Daniel Král
Editor

Abstract

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.

Citation

Deligkas, A., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Exact and approximate algorithms for computing a second Hamiltonian cycle. In J. Esparza, & D. Král (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (21:1-21:13). https://doi.org/10.4230/lipics.mfcs.2020.27

Conference Name MFCS 2020 (International Symposium on Mathematical Foundations of Computer Science)
Conference Location Prague, Czech Republic
Acceptance Date Jun 29, 2020
Online Publication Date Aug 18, 2020
Publication Date 2020
Deposit Date Aug 4, 2020
Publicly Available Date Sep 11, 2020
Pages 21:1-21:13
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series ISSN 1868-8969
Book Title 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).
DOI https://doi.org/10.4230/lipics.mfcs.2020.27
Public URL https://durham-repository.worktribe.com/output/1140398

Files






You might also like



Downloadable Citations