Quantified Equality Constraints

DOI10.1137/080725209MaRDI QIDQ5390611zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Hubie Chen

Publication date 4 April 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/080725209

zbMATH Keywords

computational complexityequality templateomega-categorical structurequantified constraint satisfactionrelational structure

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Categoricity and completeness of theories (03C35) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1761416
• Equality detection for linear arithmetic constraints
• Equivalence constraint satisfaction problems
• Inner and Outer Approximations of Existentially Quantified Equality Constraints
• Soft constraints of difference and equality
• From Boolean equalities to constraints
• Quantified Constraints and Containment Problems
• Equivalence of constrained models
• The complexity of equality constraint languages
• The Complexity of Equality Constraint Languages

Cited in

(16)

• Equivalence of constrained models
• Reconstructing the topology of clones
• The Complexity of Counting Quantifiers on Equality Languages
• The Complexity of Equality Constraint Languages
• The complexity of positive first-order logic without equality. II: The four-element case
• Quantified Constraints in Twenty Seventeen
• The complexity of quantified constraints using the algebraic formulation
• The complexity of counting quantifiers on equality languages
• Tractability of quantified temporal constraints to the max
• Quantified constraint satisfaction problem on semicomplete digraphs
• Quantified constraint satisfaction on monoids
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Equality detection for linear arithmetic constraints
• Identifying tractable quantified temporal constraints within Ord-Horn
• Datalog-expressibility for monadic and guarded second-order logic
• The complexity of equality constraint languages

This page was built for publication: Quantified Equality Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5390611)