betaFeedback

WorksComputer Science

Tight Width Minimisation of Self-Join-Free Quantified Conjunctive Queries

Abstract

Query minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. We study width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. For this subclass, we show that rewriting optimality coincides with semantic optimality: given a query ϕϕ, the minimum-width query obtainable from ϕϕ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to ϕϕ. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.

CCS Concepts: • Theory of computation → Logic and databases; Finite Model Theory.

Additional Key Words and Phrases: Quantified Conjunctive Queries, Finite Model Theory, Width.

Introduction

Background. The problem of minimising a query while preserving logical equivalence is a classical and central topic in database theory. Indeed, the notions of equivalence, containment, and minimisation were already identified in the 1970s [14] as giving rise to fundamental algorithmic problems underlying conjunctive queries (CQs). Since then, a rich line of work has studied these questions in close connection with constraint satisfaction, homomorphisms, and finite-variable logics [2, 3, 5, 15, 23, 24, 25, 30, 31, 33, 35, 36]. In this line of research, a central structural measure is the width of a formula φ\varphi, denoted by width⁡(φ)\operatorname{width}(\varphi), which is the maximum number of free variables over all subformulae [1, 9, 11, 22, 30, 31, 41]. Using standard variable renaming, in ordinary one-sorted first-order logic, the minimum width of a sentence ϕ\phi over all formulae logically equivalent to ϕ\phi, which we call the logical width and denote by logwidth⁡(ϕ)\operatorname{logwidth}(\phi), coincides with the minimum number of variables needed to express ϕ\phi [32]. This coincidence does not hold in general in many-sorted variants, where sorts can restrict variable reuse. Width is therefore a more general structural parameter in such settings, particularly for lower-bound arguments, and we take it as our reference measure throughout this work. The natural bottom-up evaluation algorithm for first-order logic (on finite structures) has an exponential dependence on the width [41] and can be performed in polynomial time for sentences of bounded width. Moreover, when the arity of relations is fixed, there are dichotomy theorems showing that bounded width is the exclusive explanation for the tractability of classes of formulae [17, 23, 24, 30, 31]. Thus, width is a fundamental measure in query evaluation.

A strongly related measure associated with CQs, and generalisations thereof, is the treewidth [39] of the query hypergraph: each atom induces a hyperedge on its variables. This measure has been used to identify structurally tractable classes of formulae and related evaluation problems [25, 27, 36]. The interaction between width and treewidth in this context, as well as the study of other measures of the query hypergraph, has proved central to modern approaches to query evaluation, semantic optimisation, and query rewriting [6, 15, 22, 27, 30, 31, 38]. However, width minimisation of a first-order query up to logical equivalence is noncomputable in general [1], and already noncomputable in positive logic [9]. This motivates the search for exact minimisation results on robust subclasses of queries [12], as well as characterisations of the minimum width obtainable under rewritings [22].

Quantified Conjunctive Queries. The aim of this article is to go beyond the purely existential case by considering width minimisation for quantified conjunctive queries (QCQs). These naturally extend CQs by allowing both existential and universal quantifiers, while keeping conjunction as the only Boolean connective.1 In this sense, QCQs are closely related to the quantified constraint satisfaction problem (QCSP) and, more generally, to positive Horn logic [8, 16]. This connection has been fruitfully exploited in the study of containment problems: for QCSPs, inclusion between templates admits homomorphic and algebraic characterisations [19, 20]; for QCQs, entailment admits a Chandra–Merlin style characterisation via Skolem homomorphisms, is NP-complete, and coincides with its finite variant [13]. The model-checking problem for QCQs has also been studied through parameters that generalise treewidth to account for the interaction between the quantifier prefix and the query hypergraph [18]. Thus, QCQs combine the structural discipline of CQs with the additional expressive power brought by the presence of both existential and universal quantification and the resulting quantifier alternation. This makes minimisation questions for QCQs particularly compelling. In the existential-positive setting, when the goal is to optimise a given existential-positive query, optimising within the class of existential-positive queries is equivalent to optimising within the class of all first-order queries [12].2 This raises the question of whether a similar phenomenon holds for QCQs and whether the logical width of QCQs can be analysed.

We take a first step in this direction by considering the width minimisation of self-join-free QCQs, namely QCQs where no relation symbol is repeated. This setting captures the essential interaction between width and quantifier alternation, while providing a clean stepping stone towards understanding general QCQs. Minimisation within the class of CQs is a classical issue [14]; for width minimisation, after passing to the core, the minimal width is controlled by treewidth [12]. In contrast, even for self-join-free QCQs, prior to this work, there was no transparent method for minimising width within the class of QCQs itself, let alone over the class of first-order formulae.

Rewriting. To address the problem of width minimisation for QCQs, we consider a rewriting framework developed recently by Chen and Mengel [22]. Informally, this framework is based on a set of rewriting rules A\mathcal{A} that are known to preserve logical equivalence, and in the case of QCQs, contain rules that reorder quantifiers of the same kind, push existential quantifiers towards the atoms, split universal quantification over conjunctions, and remove vacuous quantifiers. These rules organise a QCQ into alternating regions: {∃,∧}\{\exists,\land\}-regions, built from existential quantifiers and conjunctions, and {∀}\{\forall\}-regions, built from universal quantifiers only. Each region ψ\psi has an associated hypergraph HψH_\psi. Its hyperedges record how ψ\psi interacts both with its immediate subregions and the context above it: for each (potentially atomic) child region, there is a hyperedge containing the variables of said child, and there is a further hyperedge containing all the free variables of ψ\psi.

This rewriting framework [22] provides an algorithm that, upon input of a positive first-order formula φ\varphi, outputs a formula φ+\varphi^{+} of minimum width within the class of all formulae obtainable from φ\varphi via the rewriting rules; this class is denoted by [φ]A[\varphi]_{\mathcal{A}}. The width of this output can be characterised (in a certain precise sense) as the maximum hypertreewidth over all regions.

The following examples suggest why, in the presence of universal quantifiers, a measure more sophisticated than the treewidth of the query is needed to characterise its logical width, and also anticipate some of the complexity involved in showing width lower bounds. First, consider

φ1=∃x1⋯∃xl∃x⋀i=1lRi(x,xi)≡∃x∃x1⋯∃xl⋀i=1lRi(x,xi)≡∃x⋀i=1l∃xiRi(x,xi).\varphi_1 = \exists x_1 \cdots\exists x_l \exists x \bigwedge_{i=1}^{l} R_i(x,x_i) \quad\equiv\quad\exists x \exists x_1 \cdots\exists x_l \bigwedge_{i=1}^{l} R_i(x,x_i) \quad\equiv\quad\exists x \bigwedge_{i=1}^{l} \exists x_i R_i(x,x_i).

Its query hypergraph is clearly a star, and hence has treewidth 1; as shown above, the query can be rewritten into one of width 2, by reordering the quantifiers and pushing each ∃xi\exists x_i in front of the unique atom in which xix_i occurs. This is the kind of behaviour captured by the existential-positive theory of variable minimisation [12]. Next, consider instead the QCQ

φ2=∀y1⋯∀ymψ∃,where ψ∃=∃x⋀j=1mSj(x,yj).\varphi_2 = \forall y_1 \cdots\forall y_m \psi_{\exists}, \quad\text{where } \psi_{\exists} = \exists x \bigwedge_{j=1}^{m} S_j(x,y_j).

Although the query hypergraph is again a star, the universal variables yjy_j, intuitively speaking, must remain simultaneously available when the existential witness xx is chosen. There is a hypergraph associated with the formula ψ∃\psi_{\exists}; this hypergraph accounts for the universal variables by including a top-boundary hyperedge that contains all of its free variables, namely, {y1,…,ym}\{y_1,\ldots,y_m\}. The relevant treewidth is no longer that of the query hypergraph, but of a larger hypergraph that includes this boundary hyperedge. Indeed, this article shows this formula to have logical width m+1m+1. Finally, the combination of the above two situations gives formulae, for m>0m>0, of the form

φ3=∃x1⋯∃xlψ∀,where ψ∀=∀y1⋯∀ymψ∃ and ψ∃=∃x(⋀i=1lRi(x,xi)∧⋀j=1mSj(x,yj)).\varphi_3 = \exists x_1 \cdots\exists x_l \psi_{\forall}, \quad\text{where } \psi_{\forall} = \forall y_1 \cdots\forall y_m \psi_{\exists} \text{ and } \psi_{\exists} = \exists x \left(\bigwedge_{i=1}^{l} R_i(x,x_i) \land\bigwedge_{j=1}^{m} S_j(x,y_j)\right).

Intuitively speaking, here the universal variables yjy_j depend on the existential variables xix_i, and so all of these variables must be kept in scope when considering how to assign xx. This is accounted for in the hypergraph associated to ψ∃\psi_{\exists}, where the top-boundary hyperedge contains all variables but xx; as this article shows, for these formulae the logical width is l+m+1l+m+1. These examples point to why the theory of CQs does not transfer directly.

Contributions. Our main result shows that, for self-join-free QCQs, the minimum width over all formulae in [φ]A[\varphi]_{\mathsf{A}} is in fact the logical width of φ\varphi.

Theorem 1.1 (Main Result). Let φ\varphi be a self-join-free QCQ and φ+\varphi^+ a self-join-free QCQ of minimum width among all formulae in [φ]A[\varphi]_{\mathsf{A}}. Then, logwidth⁡(φ)=width⁡(φ+)\operatorname{logwidth}(\varphi)=\operatorname{width}(\varphi^+). Moreover, there is an algorithm that, given a self-join-free QCQ φ\varphi, computes such a QCQ φ+\varphi^+ in polynomial time, assuming access to an oracle for computing minimum-width tree decompositions.

This result also gives a complexity description of width computation. Given a self-join-free QCQ φ\varphi and a number k∈Nk \in\mathbb{N}, deciding whether logwidth⁡(φ)≤k\operatorname{logwidth}(\varphi)\leq k is NP-complete. Moreover, computing the logical width of such a query is polynomial-time equivalent to computing graph treewidth. See Corollary 4.3 for details on these results.

To reformulate this main theorem (Theorem 1.1), for self-join-free QCQs, logical width admits exact algorithmic optimisation via syntactic rewriting, and thus the width found by rewriting is not merely an artefact, but rather the true logical width of the query. An alternative reading of this theorem is that no width blow-up is incurred when passing from full first-order logic back to self-join-free QCQs: when a first-order formula of width kk is equivalent to a self-join-free QCQ, it is equivalent to a self-join-free QCQ of width kk. This extends a tightness phenomenon previously known for existential-positive queries [12, 40].

Regarding the theorem’s statement, the inequality logwidth⁡(φ)≤width⁡(φ+)\operatorname{logwidth}(\varphi) \leq\operatorname{width}(\varphi^+) is immediate, since φ+\varphi^+ is logically equivalent to φ\varphi. The difficult part is the reverse inequality, since the rewriting algorithm only gives an a priori syntactic upper bound: it constructs an equivalent QCQ whose width is governed by the maximum value of the treewidth (plus one) over its regions; the algorithm does not, by itself, rule out the possibility of a completely different first-order formula of smaller width. To prove semantic optimality, we focus on a region having maximum treewidth, and use it to show a lower bound on finite-variable definability. Here pebble games [32], a variant of Ehrenfeucht–Fraïssé games [26, 29], enter the picture: by the classical characterisation of finite-variable first-order logic, to show that logwidth⁡(φ)>k\operatorname{logwidth}(\varphi) > k, it suffices to construct two finite structures A\mathcal{A} and B\mathcal{B} that are separated by φ\varphi, but indistinguishable by first-order formulae using only kk variables; this is the route we take. We first carry out these constructions in variable-sorted logic, where each query variable has its own domain. This lets us choose these domains independently and forces pebble-game responses to remain in the domain associated with the relevant variable. The resulting lower bounds are then transferred back to ordinary one-sorted structures (see Lemma 2.9).

On the role of self-join-freeness. One may wonder whether a result like Theorem 1.1 holds without the self-join-free assumption. However, even for conjunctive queries, a result analogous to Theorem 1.1 does not hold. For example, the conjunctive query

φ1=∃x1∃x2∃x3⋀i,j∈{1,2,3}E(xi,xj)\varphi_1 = \exists x_1 \exists x_2 \exists x_3 \bigwedge_{i,j \in\{1,2,3\}} E(x_i,x_j)

is logically equivalent to the conjunctive query

φ2=∃xE(x,x);\varphi_2 = \exists x E(x,x);

this latter query φ2\varphi_2 has width 1, but the minimum width among all formulae in [φ1]A[\varphi_1]_{\mathcal{A}} can be verified to be 3.3 Bova and Chen [12] establish that the logical width of a CQ φ\varphi is equal to the treewidth of the core of φ\varphi plus one; equivalently, one can apply the rewriting methods described in the present article to minimise the width of the core. Paralleling this situation for CQs, we conjecture that the logical width of an arbitrary QCQ φ\varphi can be obtained similarly: pass to an appropriate notion of core of φ\varphi, and then apply the rewriting methods. This would involve introducing a notion of core for QCQs, see § 7 for more details. Moreover, we use the assumption that the query is self-join-free for many proofs along the way to establishing our main result; more details are provided throughout the paper.

Organisation. § 2 provides the requisite preliminaries. In § 3, we detail the rewriting framework established in [22] needed to formalise our main results, which are stated in § 4. The rest of the article is dedicated to establishing our main result. We handle the case where a {∀}\{\forall\}-region is the region with maximum treewidth directly in § 4, leaving the more complicated case of when a {∃,∧}\{\exists,\land\}-region has maximum treewidth. § 5 establishes the logical width lower bound on simple QCQs, a syntactic restriction on QCQs where the lower-bound argument can be carried out explicitly via pebble games. Finally, a sequence of reductions, sketched in Section 6, reduces the general {∃,∧}\{\exists,\land\} case to the simple QCQ case, in effect lifting the lower bound.

Preliminaries

Let N:={0,1,…}\mathbb{N} := \{0,1,\ldots\} and N+:=N∖{0}\mathbb{N}_{+} := \mathbb{N} \setminus\{0\}. We use ⊔\sqcup for disjoint union. For i,j∈Ni,j \in\mathbb{N}, let [i,j]:={i,i+1,…,j}[i,j] := \{i,i+1,\ldots,j\} and [j]:=[1,j][j] := [1,j], with [i,j]:=∅[i,j] := \varnothing, if i>ji > j. When f:A→Bf:A \to B is a (partial) function, we denote by dom⁡(f)\operatorname{dom}(f) the domain and by ran⁡(f)\operatorname{ran}(f) the range of ff; in addition, we use f[x↦a]f[x \mapsto a] to denote the (partial) function equal to ff everywhere except xx, where it is mapped to aa. The restriction of ff to A′A', for some A′⊆dom⁡(f)A' \subseteq\operatorname{dom}(f), is denoted by f∣A′f|_{A'}. For a tuple t⃗=(t1,…,tr)\vec{t}=(t_1,\ldots,t_r), let πi(t⃗)=ti\pi_i(\vec{t})=t_i, for every i∈[r]i \in[r]. When AA is a set, (A2)\binom{A}{2} denotes the set of 2-element subsets of AA.

Graphs and Hypergraphs. A graph G:=(V,E)G := (V,E) is a pair consisting of a finite set VV of vertices and a set E⊆(V2)E \subseteq\binom{V}{2} of edges. A walk in GG is a sequence (v1,…,vm)∈Vm(v_1,\ldots,v_m) \in V^m, with m≥2m \ge2, such that {vi,vi+1}∈E\{v_i,v_{i+1}\} \in E, for all i∈[m−1]i \in[m-1]. For a vertex v∈Vv \in V, we use EvE_v for the set of edges incident on vv.

A tree decomposition of a graph G:=(V,E)G := (V,E) is a tree TT where each node uu of TT is associated with a non-empty subset BuB_u of VV called a bag such that:

a) for all edges e∈Ee \in E, there is some node uu of TT such that e⊆Bue \subseteq B_u;

b) for all vertices v∈Vv \in V, the nodes uu of TT with v∈Buv \in B_u form a non-empty connected subtree of TT.

References

  1. [1]I. Adler and M. Weyer. 2012. Tree-Width for First Order Formulae. Logical Methods in Computer Science 8, 1 (2012), 1–32. doi:10.2168/LMCS-8(1:32)2012DOI
  2. [2]A.V. Aho, Y. Sagiv, and J.D. Ullman. 1979. Efficient Optimization of a Class of Relational Expressions. Transactions on Database Systems 4, 4 (1979), 435–454. doi:10.1145/320107.320112DOI
  3. [3]A.V. Aho, Y. Sagiv, and J.D. Ullman. 1979. Equivalences Among Relational Expressions. SIAM J. Comput. 8, 2 (1979), 218–246. doi:10.1137/0208017DOI
  4. [4]S. Arnborg, D.G. Corneil, and A. Proskurowski. 1987. Complexity of Finding Embeddings in a k-Tree. SIAM Journal on Algebraic Discrete Methods 8, 2 (1987), 277–284. doi:10.1137/0608024DOI
  5. [5]P. Barceló, L. Libkin, and M. Romero. 2014. Efficient Approximations of Conjunctive Queries. SIAM J. Comput. 43, 3 (2014), 1085–1130. doi:10.1137/13091731
  6. [6]P. Barceló, A. Pieris, and M. Romero. 2017. Semantic Optimization in Tractable Classes of Conjunctive Queries. Special Interest Group on Management of Data’ 46, 2 (2017), 5–17. doi:10.1145/3137586.3137588DOI
  7. [7]J.A. Bondy and U.S.R. Murty. 2008. Graph Theory. Springer.
  8. [8]F. Börner, A. Bulatov, H. Chen, P. Jeavons, and A. Krokhin. 2009. The Complexity of Constraint Satisfaction Games and QCSP. Information and Computation 207, 9 (2009), 923–944. doi:10.1016/j.ic.2009.05.003DOI
  9. [9]S. Bova and H. Chen. 2014. The Complexity of Width Minimization of Existential Positive Queries. In International Conference on Database Theory’14. OpenProceedings.org, 235–244. doi:10.5441/002/icdt.2014.25DOI
  10. [10]S. Bova and H. Chen. 2015. The Complexity of Equivalence, Entailment, and Minimization in Existential Positive Logic. J. Comput. System Sci. 81, 2 (2015), 443–457. doi:10.1016/j.jcss.2014.10.002DOI
  11. [11]S. Bova and H. Chen. 2017. How Many Variables are Needed to Express an Existential Positive Query?. In International Conference on Database Theory’17. OpenProceedings.org, 9:1–16. doi:10.4230/LIPIcs.ICDT.2017.9DOI
  12. [12]S. Bova and H. Chen. 2019. How Many Variables are Needed to Express an Existential Positive Query? Theory of Computing Systems 63, 7 (2019), 1573–1594. doi:10.1007/s00224-018-9884-zDOI
  13. [13]S. Bova and F. Mogavero. 2017. Herbrand Property, Finite Quasi-Herbrand Models, and a Chandra-Merlin Theorem for Quantified Conjunctive Queries. In Logic in Computer Science’17. Association for Computing Machinery, 1–12. doi:10.1109/LICS.2017.8005073DOI
  14. [14]A.K. Chandra and P.M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Symposium on Theory of Computing’77. Association for Computing Machinery, 77–90.DOI
  15. [15]C. Chekuri and A. Rajaraman. 2000. Conjunctive Query Containment Revisited. Theoretical Computer Science 239, 2 (2000), 211–229. doi:10.1016/S0304-3975(99)00220-0DOI
  16. [16]H. Chen. 2008. The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case. SIAM J. Comput. 37, 5 (2008), 1674–1701. doi:10.1137/060668572DOI
  17. [17]H. Chen. 2017. The Tractability Frontier of Graph-Like First-Order Query Sets. J. ACM 64, 4 (2017), 26:1–29. doi:10.1145/3073409DOI
  18. [18]H. Chen and V. Dalmau. 2016. Decomposing Quantified Conjunctive (or Disjunctive) Formulas. SIAM J. Comput. 45, 6 (2016), 2066–2086.
  19. [19]H. Chen, F.R. Madelaine, and B. Martin. 2008. Quantified Constraints and Containment Problems. In Logic in Computer Science’08. IEEE Computer Society, 317–328.
  20. [20]H. Chen, F.R. Madelaine, and B. Martin. 2015. Quantified Constraints and Containment Problems. Logical Methods in Computer Science 11, 3 (2015), 9:1–28. doi:10.2168/LMCS-11(3:9)2015DOI
  21. [21]H. Chen and S. Mengel. 2024. Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity. In International Conference on Database Theory’24 (LIPIcs 290). Leibniz-Zentrum fuer Informatik, 16:1–17. doi:10.4230/LIPIcs.ICDT.2024.16DOI
  22. [22]H. Chen and S. Mengel. 2026. Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity. Logical Methods in Computer Science 22, 2 (2026), 6:1–34. doi:10.46298/lmcs-22(2:6)2026DOI
  23. [23]Hubie Chen and Moritz Müller. 2015. The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space. TOCT 7, 2 (2015), 7.
  24. [24]Hubie Chen and Moritz Müller. 2017. One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries. ACM Trans. Comput. Log. 18, 4 (2017), 29:1–29:37.
  25. [25]V. Dalmau, P.G. Kolaitis, and M.Y. Vardi. 2002. Constraint Satisfaction, Bounded Treewidth, and Infinite-Variable Logics. In Constraint Programming’02 (LNCS 2470). Springer, 310–326.
  26. [26]H.D. Ebbinghaus and J. Flum. 1995. Finite Model Theory. Springer.
  27. [27]G. Gottlob, N. Leone, and F. Scarcello. 2002. Hypertree Decompositions and Tractable Queries. J. Comput. System Sci. 64, 3 (2002), 579–627. doi:10.1006/jcss.2001.1809DOI
  28. [28]E. Grädel, M. Model Checking Games. Electronic Notes in Theoretical Computer Science 67, 15–34. doi:10.1016/S1571-0661(04)80538-3DOI
  29. [29]E. Grädel, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M.Y. Vardi, Y. Venema, and S. Weinstein. 2005. Finite Model Theory and Its Applications. Springer.
  30. [30]M. Grohe. 2007. The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. J. ACM 54, 1 (2007), 1:1–24. doi:10.1145/1206035.1206036DOI
  31. [31]M. Grohe, T. Schwentick, and L. Segoufin. 2001. When is the Evaluation of Conjunctive Queries Tractable?. In Symposium on Theory of Computing’01. Association for Computing Machinery, 657–666. doi:10.1145/380752.380867DOI
  32. [32]N. Immerman. 1982. Upper and Lower Bounds for First Order Expressibility. J. Comput. System Sci. 25, 1 (1982), 76–98. doi:10.1016/0022-0000(82)90011-3DOI
  33. [33]Y.E. Ioannidis and R. Ramakrishnan. 1995. Containment of Conjunctive Queries: Beyond Relations as Sets. Transactions on Database Systems 20, 3 (1995), 288–324. doi:10.1145/211414.211419DOI
  34. [34]Dmitry Itsykson, Artur Riazanov, and Petr Smirnov. 2022. Tight Bounds for Tseitin Formulas. In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 236). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 6:1–6:21. doi:10.4230/LIPIcs.SAT.2022.6
  35. [35]A. Kara, Z. Luo, M. Nikolic, D. Olteanu, and H. Zhang. 2025. Tractable Conjunctive Queries over Static and Dynamic Relations. In International Conference on Database Theory’25 (LIPIcs 328). Leibniz-Zentrum fuer Informatik, 12:1–21. doi:10.4230/LIPIcs.ICDT.2025.12DOI
  36. [36]P.G. Kolaitis and M.Y. Vardi. 2000. Conjunctive-Query Containment and Constraint Satisfaction. J. Comput. System Sci. 61, 2 (2000), 302–332. doi:10.1006/jcss.2000.1713DOI
  37. [37]L. Libkin. 2004. Elements of Finite Model Theory. Springer.DOI
  38. [38]D. Marx. 2010. Can You Beat Treewidth? Theory of Computing 6, 1 (2010), 5:85–112. doi:10.4086/toc.2010.v006a005DOI
  39. [39]N. Robertson and P.D. Seymour. 1986. Graph minors. II. Algorithmic Aspects of Tree-Width. Journal of Algorithms 7, 3 (1986), 309–322.DOI
  40. [40]B. Rossman. 2025. Equi-Rank Homomorphism Preservation Theorem on Finite Structures. In Computer Science Logic ’25 (LIPIcs 328). Leibniz-Zentrum fuer Informatik, 6:1–17. doi:10.4230/LIPIcs.CSL.2025.6DOI
  41. [41]R. Williams. 2014. Faster Decision of First-Order Graph Properties. In Computer Science Logic’14 & Logic in Computer Science’14. Association for Computing Machinery, 80:1–6.DOI

Paper details

vlnc:W_arf5ed9e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents