Portal de Periódicos da CAPES

The Expressivity of Constraint Query Languages with Boolean Algebra Linear Cardinality Constraints

2005; Springer Science+Business Media; Linguagem: Inglês

10.1007/11547686_13

1611-3349

Péter Révész,

Constraint Satisfaction and Optimization

Constraint query languages with Boolean algebra linear cardinality constraints were introduced recently and shown to be evaluable using a quantifier elimination method in [22]. However, the expressive power of constraint query languages with linear cardinality constraints is still poorly understood in comparison with other cases of constraint query languages. This paper makes several contributions to the analysis of their expressive power. Several problems that were previously provably impossible to express even in FO+POLY are shown to be expressible using first-order query languages with linear cardinality constraints FO+BALC. We also show that all monadic Datalog queries are expressible in FO+BALC. Finally, we also show a new results for FO+LINEAR by expressing in it the problem of finding the time when two linearly moving point objects are closest to each other.