Pasar al contenido principal

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación 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
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Inference of k-Testable Directed Acyclic Graph Languages

  • López Rodríguez, Damián|||0000-0003-3633-3862
  • Calera Rubio, Jorge
  • Gallego-Sánchez, Antonio-Javier
In this paper, we tackle the task of graph language learning. We first extend the well-known classes of k-testability and k-testability in the strict sense languages to directed graph languages. Second, we propose a graph automata model for directed acyclic graph languages. This graph automata model is used to propose a grammatical inference algorithm to learn the class of directed acyclic k-testable in the strict sense graph languages. The algorithm runs in polynomial time and identifies this class of languages from positive data., Damián López is partially supported by the Spanish Ministerio de Economía y Competitividad under research project TIN2011-28260-C03-01. Jorge Calera-Rubio and Antonio-Javier Gallego-Sánchez thank the Spanish CICyT for partial support of this work through project TIN2009-14205-C04-01, the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778, and the program CONSOLIDER INGENIO2010 (CSD2007-00018).
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

A log square average case algorithm to make insertions in fast similarity search

  • Micó, Luisa
  • Oncina, Jose
To speed up similarity based searches many indexing techniques have been proposed in order to address the problem of efficiency. However, most of the proposed techniques do not admit fast insertion of new elements once the index is built. The main effect is that changes in the environment are very costly to be taken into account. In this work, we propose a new technique to allow fast insertions of elements in a family of static tree-based indexes. Unlike other techniques, the resulting index is exactly equal to the index that would be obtained by building it from scratch. Therefore there is no performance degradation in search time. We show that the expected number of distance computations (and the average time complexity) is bounded by a function that grows with log2(n) where n is the size of the database. In order to check the correctness of our approach some experiments with artificial and real data are carried out.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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.