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 complexityrelational structurequantified constraint satisfactionomega-categorical structureequality template

Mathematics Subject Classification ID

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

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)

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