On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
Mathematical Logic Quarterly · 2004-05 · 50 (3) · 281-292
DOI: 10.1002/malq.200310099 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Logic Quarterly, online erschienen am 07.04.2004. Verfasst von K. Subramani. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 40 Literaturangaben.
Abstract (Originalsprache)
This paper is concerned with techniques for identifying simple and quantified lattice points in 2SAT polytopes. 2SAT polytopes generalize the polyhedra corresponding to Boolean 2SAT formulas, Vertex‐Packing (Covering, Partitioning) and Network flow problems; they find wide application in the domains of Program verification (Software Engineering) and State‐Space search (Artificial Intelligence). Our techniques are based on the symbolic elimination strategy called the Fourier‐Motzkin elimination procedure and thus have the advantages of being extremely simple (from an implementational perspective) and incremental. We also provide a characterization of a 2SAT polytope in terms of its extreme points and derive some interesting hardness results for associated optimization problems. Finally, we provide a brief discussion on the maximum size of a subdeterminant of the linear system representing a 2SAT polytope; this parameter plays a vital role in deriving analytical bounds on the size of the search space for checking whether the polyhedron includes a lattice point. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)
Zitieren
APA
Subramani, K. (2004). On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries. Mathematical Logic Quarterly, 50(3), 281-292. https://doi.org/10.1002/malq.200310099
Vancouver
Subramani K. On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries. Mathematical Logic Quarterly. 2004;50(3):281-292. doi:10.1002/malq.200310099
BibTeX
@article{Subramani2004,
author = {Subramani, K.},
title = {On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries},
journal = {Mathematical Logic Quarterly},
year = {2004},
volume = {50},
number = {3},
pages = {281--292},
doi = {10.1002/malq.200310099}
}
EUVIMED