EUVIMEDEUVIMED entdecken
Crossref

On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries

K. Subramani

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →