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
Minds and Machines
Erschienen in: Minds and Machines 1/2013

01.03.2013

Variable-Centered Consistency in Model RB

verfasst von: Liang Li, Tian Liu, Ke Xu

Erschienen in: Minds and Machines | Ausgabe 1/2013

Einloggen

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

search-config
loading …

Abstract

Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to some kind of consistency in constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent.
Vorheriger Artikel A Lewisian Logic of Causal Counterfactuals
Nächster Artikel An Ontology-Based Approach to Metaphor Cognitive Computation

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
Literatur
Bessiere, C. (2006). Constraint propagation, handbook of constraint programming (pp. 29–84).
Cai, S., Su, K., & Sattar, A. (2011). Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence, 175(9–10), 1672–1696.MathSciNetMATHCrossRef
Cheeseman, P., Kanefsky, R., & Taylor, W. (1991). Where the really hard problems are. In Proceedings of IJCAI (pp. 163–169).
Dechter, R. (2003). Constraint processing. San Mateo, CA: Morgan Kaufmann.
Fan, Y., & Shen, J. (2011). On the phase transitions of random k-constraint satisfaction problems. Artificial Intelligence, 175, 914–927.MathSciNetMATHCrossRef
Freuder, E. C. (1982). A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery, 29(1), 24–32.MathSciNetMATHCrossRef
Gao, Y., & Culberson, J. C. (2007). Consistency and random constraint satisfaction models. Journal of Artificial Intelligence Research, 28, 517–557.MathSciNetMATH
Gomes, C., & Walsh, T. (2006). Randomness and structures, handbook of constraint programming (pp. 639–664).
Lecoutre, C. (2009). Constraint networks: Techniques and algorithms. New York: ISTE/Wiley.CrossRef
Li, W. (2010). Logical verification of scientific discovery. Science China Information Sciences, 53(4), 677–684.MathSciNetCrossRef
Liu, T., Lin, X., Wang, C., Su, K., & Xu, K. (2011). Large hinge width on sparse random hypergraphs. In Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI’2011) (pp. 611–616).
Luo, J., & Li, W. (2011). An algorithm to compute maximal contractions for Horn clauses. Science China Information Sciences, 54(2), 244–257.MathSciNetMATHCrossRef
Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8, 99–118.MATHCrossRef
Mitzenmacher, M., & Upfal, E. (2005). Probability and computing. Cambridge, UK: Cambridge University Press.MATH
Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information sciences, 7, 95–132.MathSciNetMATHCrossRef
Tsang, E. P. K. (1993). Foundations of constraint satisfaction. London and San Diego: Academic Press.
Xu, K., & Li, W. (2000). Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12, 93–103.MathSciNetMATH
Xu, K., Boussemart, F., Hemery, F., & Lecoutre, C. (2007). Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 171, 514–534.MathSciNetMATHCrossRef
Metadaten
Titel
Variable-Centered Consistency in Model RB
verfasst von
Liang Li
Tian Liu
Ke Xu
Publikationsdatum
01.03.2013
Verlag
Springer Netherlands
Erschienen in
Minds and Machines / Ausgabe 1/2013
Print ISSN: 0924-6495
Elektronische ISSN: 1572-8641
DOI
https://doi.org/10.1007/s11023-012-9270-6

Weitere Artikel der Ausgabe 1/2013

Minds and Machines 1/2013 Zur Ausgabe

OriginalPaper

Reasoning About Agent Types and the Hardest Logic Puzzle Ever

OriginalPaper

Preferential Semantics for Plausible Subsumption in Possibility Theory

OriginalPaper

Proof Systems for Planning Under Cautious Semantics

OriginalPaper

An Ontology-Based Approach to Metaphor Cognitive Computation

Introduction

Logic and AI in China: An Introduction

OriginalPaper

A Lewisian Logic of Causal Counterfactuals