skip to main content
10.1145/1233341.1233446acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
Article

Propositional reasoning by dimensional reduction: a preliminary report

Published: 23 March 2007 Publication History

Abstract

Divide-and-conquer is an effective general problem solving strategy, and has been applied to improve to the performance of search procedures. The challenge in applying the strategy is to find an appropriate decomposition of the problem into subproblems. In this paper, a decomposition is presented for n-dimensional propositional satisfiability problems. Experiments with timetable scheduling show the potential for the technique.

References

[1]
E. Amir and S. McIlraith. Solving Satisfiability using Decomposition and the Most Constrained Subproblem. In Proceedings of the Workshop on Theory and Applications of Satisfiability Testing, 2001
[2]
C. Bessière and J. RéAgin. Enforcing arc consistency on global constraints by solving subproblems on the fly. In Proceedings of the Principles and Practice of Constraint Programming, pages 103--117. Springer-Verlag, 1999.
[3]
P. Bjesse, J. H. Kukula, R. F. Damiano, T. Stanion, and Y. Zhu. Guiding SAT Diagnosis with Tree Decompositions. In SAT, pages 315--329, 2003.
[4]
W. Li and P. van Beek. Guiding Real-World SAT Solving with Dynamic Hypergraph Separator Decomposition. In Proceedings of ICTAI, pages 542--548. IEEE Computer Society, 2004.
[5]
J. J. Lu, J. S. Rosenthal, and A. E. Shaffer. A case study in the meta-reasoning procedure ND. J. Exp. Theor. Artif. Intell., 15(1):47--71, 2003.
[6]
H. Zhang. SATO: An Efficient Propositional Prover. In Proceedings of CADE. Springer-Verlag, 1997.

Index Terms

  1. Propositional reasoning by dimensional reduction: a preliminary report

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ACMSE '07: Proceedings of the 45th annual ACM Southeast Conference
      March 2007
      574 pages
      ISBN:9781595936295
      DOI:10.1145/1233341
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 23 March 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. artificial intelligence
      2. deduction

      Qualifiers

      • Article

      Conference

      ACM SE07
      Sponsor:
      ACM SE07: ACM Southeast Regional Conference
      March 23 - 24, 2007
      North Carolina, Winston-Salem

      Acceptance Rates

      ACMSE '07 Paper Acceptance Rate 81 of 137 submissions, 59%;
      Overall Acceptance Rate 502 of 1,023 submissions, 49%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 0
        Total Citations
      • 144
        Total Downloads
      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 07 Jan 2025

      Other Metrics

      Citations

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media