On the computational complexity of querying bounds on differences constraints

DOI10.1016/0004-3702(95)00008-3MaRDI QIDQ1855216zbMATH OpenOpenAlexFDO

Authors Vittorio Brusoni, Luca Console, Paolo Terenziani

Publication date 4 February 2003

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(95)00008-3

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Database theory (68P15)

Recommendations

• Optimization of bound disjunctive queries with constraints
• On Bounded Queries and Approximation
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Computer Science Logic
• Bounded queries, approximations, and the Boolean hierarchy
• Complexity of solving a system of difference constraints with variables restricted to a finite set
• Bounding queries in the analytic polynomial-time hierarchy
• The complexity of problems for quantified constraints
• Nondeterministic bounded query reducibilities
• Publication:4945218

Cites work

• Constraint propagation with interval labels
• Temporal constraint networks
• The logic of constraint satisfaction

Cited in

(4)

• Complexity studies of a temporal constraint propagation algorithm: a statistical analysis
• Solving systems of difference constraints incrementally with bidirectional search
• A spectrum of definitions for temporal model-based diagnosis
• Querying temporal and spatial constraint networks in PTIME

This page was built for publication: On the computational complexity of querying bounds on differences constraints

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