Declarative Programming of Search Problems with Built-in Arithmetic
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 942-946.
Abstract
We address the problem of providing a logical formalization of arithmetic in declarative modelling languages for NP search problems. The challenge is to simultaneously allow quantification over an infinite domain such as the natural numbers, provide natural modelling facilities, and control expressive power of the language. To address the problem, we introduce an extension of the model expansion (MX) based framework to finite structures embedded in an infinite secondary structure, together with double-guarded logics for representing MX specifications for these structures. The logics also contain multi-set functions (aggregate operations). Our main result is that these logics capture the complexity class NP on small-cost arithmetical structures.Eugenia Ternovska, David G. Mitchell
@inproceedings{ijcai2009p160,
title = {Declarative Programming of Search Problems with Built-in Arithmetic},
author = {Ternovskaia, Eugenia and Mitchell, David G.},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {942--946},
year = {2009},
url = {https://ijcai.org/proceedings/2009/160},
}
TY - CPAPER TI - Declarative Programming of Search Problems with Built-in Arithmetic AU - Ternovskaia, Eugenia AU - Mitchell, David G. T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 942 EP - 946 UR - https://ijcai.org/proceedings/2009/160 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
