Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 8
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

A combinatorial characterization of resolution width

  • Atserias, Albert
  • Dalmau, Víctor
We provide a characterization of the resolution width introduced in the context of propositional proof complexity in terms of the existential pebble game introduced in the context of finite model theory. The characterization is tight and purely combinatorial. Our first application of this result is a surprising proof that the minimum space of refuting a 3-CNF formula is always bounded from below by the minimum width of refuting it (minus 3). This solves a well-known open problem. The second application is the unification of several width lower bound arguments, and a new width lower bound for the dense linear order principle. Since we also show that this principle has resolution refutations of polynomial size, this provides yet another example showing that the relationship between size and width cannot be made subpolynomial., Supported in part by CICYT TIN2004-04343 and by the European Commission through the RTN COMBSTRU HPRN-CT2002-00278. Research partially supported by the MEC under the program “Ramon y Cajal,” grants TIC 2002-04470-C03 and TIC 2002-04019-C03, the EU PASCAL Network of Excellence, IST-2002-506778, and the MODNET Marie Curie Research Training Network, MRTN-CT-2004-512234.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Learning intersection-closed classes with signatures

  • Bulatov, Andrei A.
  • Chen, Hubie
  • Dalmau, Víctor
Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature., The first author was supported by an NSERC Discovery Grant. The second and third authors were supported by grant TIC 2002-04470-C03 and the EU PASCAL Network of Excellence IST-2002-506778. The third author was also supported by the MEC under the program “Ramon y Cajal”, grant TIC 2002-04019-C03, and MODNET Marie Curie Research Training Network MRTN-CT-2004-512234.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Majority constraints have bounded pathwidth duality

  • Dalmau, Víctor
  • Krokhin, Andrei
We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL., This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged. The first author is also supported by the MEC under the program “Ramon y Cajal”, grants TIC 2002-04470-C03, TIC 2002-04019-C03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The second author is also supported by the UK EPSRC grant EP/C543831/1.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Branching and pruning: an optimal temporal POCL planner based on constraint programming

  • Vidal, Vincent
  • Geffner, Héctor
A key feature of modern optimal planners such as graphplan and blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.1, H. Geffner is partially supported by Grant TIC2002-04470-C03-02, MCyT, Spain.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Majority constraints have bounded pathwidth duality

  • Dalmau, Víctor
  • Krokhin, Andrei
We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL., This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged. The first author is also supported by the MEC under the program “Ramon y Cajal”, grants TIC 2002-04470-C03, TIC 2002-04019-C03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The second author is also supported by the UK EPSRC grant EP/C543831/1.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Learning intersection-closed classes with signatures

  • Bulatov, Andrei A.
  • Chen, Hubie
  • Dalmau, Víctor
Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature., The first author was supported by an NSERC Discovery Grant. The second and third authors were supported by grant TIC 2002-04470-C03 and the EU PASCAL Network of Excellence IST-2002-506778. The third author was also supported by the MEC under the program “Ramon y Cajal”, grant TIC 2002-04019-C03, and MODNET Marie Curie Research Training Network MRTN-CT-2004-512234.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Branching and pruning: an optimal temporal POCL planner based on constraint programming

  • Vidal, Vincent
  • Geffner, Héctor
A key feature of modern optimal planners such as graphplan and blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.1, H. Geffner is partially supported by Grant TIC2002-04470-C03-02, MCyT, Spain.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A combinatorial characterization of resolution width

  • Atserias, Albert
  • Dalmau, Víctor
We provide a characterization of the resolution width introduced in the context of propositional proof complexity in terms of the existential pebble game introduced in the context of finite model theory. The characterization is tight and purely combinatorial. Our first application of this result is a surprising proof that the minimum space of refuting a 3-CNF formula is always bounded from below by the minimum width of refuting it (minus 3). This solves a well-known open problem. The second application is the unification of several width lower bound arguments, and a new width lower bound for the dense linear order principle. Since we also show that this principle has resolution refutations of polynomial size, this provides yet another example showing that the relationship between size and width cannot be made subpolynomial., Supported in part by CICYT TIN2004-04343 and by the European Commission through the RTN COMBSTRU HPRN-CT2002-00278. Research partially supported by the MEC under the program “Ramon y Cajal,” grants TIC 2002-04470-C03 and TIC 2002-04019-C03, the EU PASCAL Network of Excellence, IST-2002-506778, and the MODNET Marie Curie Research Training Network, MRTN-CT-2004-512234.