Schilling, Christian and Smaus, JanGeorg and Wenzelmann, Fabian A Pretty Complete Combinatorial Algorithm for the Threshold Synthesis Problem. (2014) In: International Workshop on Combinatorial Algorithms (IWOCA 2013), 10 July 2013  12 July 2013 (Rouen, France).

(Document in English)
PDF (Author's version)  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 173kB 
Official URL: https://doi.org/10.1007/9783642452789_43
Abstract
A linear pseudoBoolean constraint (LPB) is an expression of the form a_1 l_1+...+a_m l_m>= d$, where each l_i is a literal (it assumes the value 1 or 0 depending on whether a propositional variable x_i is true or false) and a_1,...,a_m,d are natural numbers. An LPB represents a Boolean function, and those Boolean functions that can be represented by exactly one LPB are called threshold functions. The problem of finding an LPB representation of a Boolean function if possible is called threshold recognition problem or threshold synthesis problem. The problem has an O(m^7t^5) algorithm using linear programming, where m is the dimension and t the number of clauses in the DNF input. There is also an entirely combinatorial procedure, which works by decomposing the DNF and "counting" the variable occurrences in it. We have implemented both algorithms and report here on the experiments.
Item Type:  Conference or Workshop Item (Paper) 

Additional Information:  Thanks to Springer editor. This papers appears in Volume 8288 of Lecture Notes in Computer Science ISSN : 03029743 ISBN: 9783642452772 The original PDF is available at: https://link.springer.com/chapter/10.1007/9783642452789_43 
HAL Id:  hal01671327 
Audience (conference):  International conference proceedings 
Uncontrolled Keywords:  
Institution:  French research institutions > Centre National de la Recherche Scientifique  CNRS (FRANCE) Université de Toulouse > Institut National Polytechnique de Toulouse  Toulouse INP (FRANCE) Université de Toulouse > Université Toulouse III  Paul Sabatier  UT3 (FRANCE) Université de Toulouse > Université Toulouse  Jean Jaurès  UT2J (FRANCE) Université de Toulouse > Université Toulouse 1 Capitole  UT1 (FRANCE) Other partners > Universität Freiburg (GERMANY) 
Laboratory name:  
Statistics:  download 
Deposited On:  06 Dec 2017 15:00 
Repository Staff Only: item control page