3 Search Results for "Kleine-Büning, Hans"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.43
New Results on Cutting Plane Proofs for Horn Constraint Systems

Authors: Hans Kleine Büning, Piotr Wojciechowski, and K. Subramani

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
In this paper, we investigate properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCS). Briefly, a system of linear inequalities A * x >= b is called a Horn constraint system, if each entry in A belongs to the set {0,1,-1} and furthermore there is at most one positive entry per row. Our focus is on deriving refutations i.e., proofs of unsatisfiability of such programs using cutting planes as a proof system. We also look at several properties of these refutations. Horn constraint systems can be considered as a more general form of propositional Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for Horn constraints when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems.
Cite as

Hans Kleine Büning, Piotr Wojciechowski, and K. Subramani. New Results on Cutting Plane Proofs for Horn Constraint Systems. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kleinebuning_et_al:LIPIcs.FSTTCS.2019.43,
  author =	{Kleine B\"{u}ning, Hans and Wojciechowski, Piotr and Subramani, K.},
  title =	{{New Results on Cutting Plane Proofs for Horn Constraint Systems}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.43},
  URN =		{urn:nbn:de:0030-drops-116056},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.43},
  annote =	{Keywords: Horn constraints, cutting planes, proof length}
}
Document
DOI: 10.4230/DagRep.4.5.1
Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201)

Authors: Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turán

Published in: Dagstuhl Reports, Volume 4, Issue 5 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14201 "Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications". The seminar brought together researchers working in various areas of mathematics and computer science, mostly in algebra, logic, date base theory, artificial intelligence and data mining. A key objective of the seminar has been to bring together a critical mass of researchers and to provide a platform for personal contacts and scientific interchange between the different disciplines in an atmosphere that will stimulate collaboration and lead to new partnerships. The goal was to crystallize the main research directions and to disseminate challenging open problems across the different research areas.
Cite as

Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turán. Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201). In Dagstuhl Reports, Volume 4, Issue 5, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{adaricheva_et_al:DagRep.4.5.1,
  author =	{Adaricheva, Kira V. and Italiano, Giuseppe F. and Kleine B\"{u}ning, Hans and Tur\'{a}n, Gy\"{o}rgy},
  title =	{{Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201)}},
  pages =	{1--26},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{5},
  editor =	{Adaricheva, Kira V. and Italiano, Giuseppe F. and Kleine B\"{u}ning, Hans and Tur\'{a}n, Gy\"{o}rgy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.5.1},
  URN =		{urn:nbn:de:0030-drops-46193},
  doi =		{10.4230/DagRep.4.5.1},
  annote =	{Keywords: Horn formulas, directed hypergraphs, lattices, closure system, data bases, implicational systems and concept analysis}
}
Document
DOI: 10.4230/DagSemRep.40
Computer Science Logic (Dagstuhl Seminar 9229)

Authors: Egon Börger, Yuri Gurevich, Hans Kleine-Büning, and M. M. Richter

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Egon Börger, Yuri Gurevich, Hans Kleine-Büning, and M. M. Richter. Computer Science Logic (Dagstuhl Seminar 9229). Dagstuhl Seminar Report 40, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{borger_et_al:DagSemRep.40,
  author =	{B\"{o}rger, Egon and Gurevich, Yuri and Kleine-B\"{u}ning, Hans and Richter, M. M.},
  title =	{{Computer Science Logic (Dagstuhl Seminar 9229)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{40},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.40},
  URN =		{urn:nbn:de:0030-drops-149288},
  doi =		{10.4230/DagSemRep.40},
}
  • Refine by Author
  • 2 Kleine Büning, Hans
  • 1 Adaricheva, Kira V.
  • 1 Börger, Egon
  • 1 Gurevich, Yuri
  • 1 Italiano, Giuseppe F.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Horn constraints
  • 1 Horn formulas
  • 1 closure system
  • 1 cutting planes
  • 1 data bases
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 1992
  • 1 2014
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact