Efficient Algorithms for Description Problems over Finite Totally Ordered Domains

DOI10.1137/050635900MaRDI QIDQ3631897zbMATH OpenOpenAlexFDO

Authors Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini

Publication date 22 June 2009

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

Full work available at URL https://semanticscholar.org/paper/3e3284dca26a707d4a41f73eb0ce6a0276dfcbdf

zbMATH Keywords

algorithmscomplexitydescription problemsfinite domain

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Analysis of algorithms (68W40)

Recommendations

• Automated Reasoning
• Tractable constraints on ordered domains
• An efficient algorithm for Horn description
• Tractable constraints in finite semilattices
• Complexity of clausal constraints over chains

Cited in

(6)

• MCP: capturing big data by satisfiability (tool description)
• An algorithm to minimize representations of finite order relations
• Automated Reasoning
• A first polynomial non-clausal class in many-valued logic
• The complexity of promise SAT on non-Boolean domains
• A note on some collapse results of valued constraints

This page was built for publication: Efficient Algorithms for Description Problems over Finite Totally Ordered Domains

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