Lower Bounds for Existential Pebble Games and k-Consistency Tests

DOI10.2168/LMCS-9(4:2)2013zbMath1297.68088MaRDI QIDQ5891234

Christoph Berkholz

Publication date: 16 October 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

first-order logicconstraint propagationfinite-variable logicexistential pebble gameparameterized complexity theory\(k\)-consistency

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (1)

On the speed of constraint propagation and the time complexity of arc consistency testing

This page was built for publication: Lower Bounds for Existential Pebble Games and k-Consistency Tests