Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Graph Modification Problems: A Modern Perspective Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Approximate Model Counting via Extension Rule

verfasst von : Jinyan Wang, Minghao Yin, Jingli Wu

Erschienen in: Frontiers in Algorithmics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Resolution principle is an important rule of inference in theorem proving. Model counting using extension rule is considered as a counterpart to resolution-based methods for model counting. Based on the exact method, this paper proposes two approximate model counting algorithms, and proves the time complexity of the algorithms. Experimental results show that they have good performance in the accuracy and efficiency.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel A New Distributed Algorithm for Computing a Dominating Set on Grids
Nächstes Kapitel Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory
Fußnoten
1
If \(\sigma \) is very small, then \(S_{accur}\approx S_{appr}\). Consequently, \(\sigma \approx \sigma '=\frac{|S_{accur}-S_{appr}|}{S_{appr}}\). So \(\sigma '\) is also considered as approximate dispersion. In this paper, we use \(\sigma '\) to get the approximate number of unsatisfying assignments of \(\varSigma \), because it is difficult to use \(\sigma \) in the condition that we do not know the exact number of unsatisfying assignments of \(\varSigma \). However, in the experimental results, we obtain the approximate value of models and know the exact number of models, so we use \(\sigma \) to measure the two approximate algorithms.
 
2
When \(sumterm\) is the value of the first sum term, \(svalue = 0\). In this case, we can not run the division operator, so we restrict \(i\ge 2\); because model counting is generally to count the number of models of a Boolean formula, the number of unsatisfying assignments is less than \(2^{v}\). So we restrict its approximate value is less than \(2^{v}\).
 
Literatur
1.
2.
Cai, D., Yin, M.: On the utility of landmarks in SAT based planning. Knowl.-Based Syst. 36, 146–154 (2012)CrossRef
3.
Nakhost, H., Mller, M.: Towards a theory of random walk planning: regress factors. fair homogeneous graphs and extensions. AI Communications 27(4), 329–344 (2014)MathSciNet
4.
Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for # SAT and bayesian inference. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 340–351 (2003)
5.
Li, W., Poupart, P., Beek, P.V.: Exploiting structure in weighted model counting approaches to probabilistic inference. J. Artif. Intell. Res. 40, 729–765 (2011)MATH
6.
Domshlak, C., Hoffmann, J.: Probabilistic planning via heuristic forward search and weighted model counting. J. Artif. Intell. Res. 30, 565–620 (2007)MATHMathSciNet
7.
Satish Kumar, T.K.: A model counting characterization of diagnoses. In: 13th International Workshop on Principles of Diagnosis, pp. 70–76 (2002)
8.
Zhang, S., Zhang, C., Yan, X.: Post-mining: maintenance of association rules by weighting. Inf. Syst. 28(7), 691–707 (2003)CrossRef
9.
Wu, X., Zhang, S.: Synthesizing high-frequency rules from different data sources. IEEE Trans. Knowl. Data Eng. 15(2), 353–367 (2003)CrossRef
10.
Gomes, C.P., Sabharwal, A., Selman, B.: Model counting, handbook of satisfiability. In: Biere, A., et al. (eds.) Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 633–654. IOS Press, Amsterdam (2009)
11.
Birnbaum, E., Lozinskii, E.: The good old davis-putnam procedure helps counting models. J. Artif. Intell. Res. 10, 457–477 (1999)MATHMathSciNet
12.
13.
Bayardo Jr., R.J., Pehoushek, J.D.: Counting models using connected components. In: Seventeenth National Conference on Artificial Intelligence (AAAI), pp. 157–162 (2000)
14.
Sang, T., Bacchus, F., Beame, P., Kautz, H., Pitassi, T.: Combining component caching and clause learning for effective model counting. In: Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT), pp. 20–28 (2004)
15.
Thurley, M.: SharpSAT – counting models with advanced component caching and implicit bcp. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 424–429. Springer, Heidelberg (2006) CrossRef
16.
Bacchus, F., Dalmao, S., Pitassi, T.: Solving # SAT and bayesian inference with backtracking search. J. Artif. Intell. Res. 34, 391–442 (2009)MATHMathSciNet
17.
Wei, W., Selman, B.: A new approach to model counting. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 324–339. Springer, Heidelberg (2005) CrossRef
18.
Wei, W., Erenrich, J., Selman, B.: Towards efficient sampling: exploiting random walk strategies. In: Nineteenth National Conference on Artificial Intelligence (AAAI), pp. 670–676 (2004)
19.
Jweeum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188 (1986)MathSciNetCrossRef
20.
Gomes, C.P., Hoffmann, J., Sabharwal, A., Selman, B.: From sampling to model counting. In: Twentieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 2293–2299 (2007)
21.
Gogate, V., Dechter, R.: Approximate counting by sampling the backtrackfree search space. In: Twenty-Second National Conference on Artificial Intelligence (AAAI), pp. 198–203 (2007)
22.
Kroc, L., Sabharwal, A., Selman, B.: Leveraging belief propagation, backtrack search, and statistics for model counting. Ann. Oper. Res. 184(1), 209–231 (2011)MATHMathSciNetCrossRef
23.
24.
25.
Yin, M., Sun, J.: Counting models using extension rules. In: Twenty-Second National Conference on Artificial Intelligence (AAAI), pp. 1916–1917 (2007)
26.
27.
Bennett, H., Sankaranarayanan, S.: Model counting using the inclusion-exclusion principle. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 362–363. Springer, Heidelberg (2011)CrossRef
28.
29.
30.
Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Trick, M., Johnson, D.S (eds.) Second DIMACS Challenge on Cliques, Coloring and Satisfiability, pp. 521–532 (1993)
Metadaten
Titel
Approximate Model Counting via Extension Rule
verfasst von
Jinyan Wang
Minghao Yin
Jingli Wu
Copyright-Jahr
2015
Buch
Frontiers in Algorithmics

Print ISBN: 978-3-319-19646-6

Electronic ISBN: 978-3-319-19647-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19647-3_22