Standard

Improving Refutational Completeness of Relational Search via Divergence Test. / Rozplokhas, Dmitri; Булычев, Дмитрий Юрьевич.

Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. Association for Computing Machinery, 2018. (Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Rozplokhas, D & Булычев, ДЮ 2018, Improving Refutational Completeness of Relational Search via Divergence Test. in Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming, Association for Computing Machinery. https://doi.org/10.1145/3236950.3236958

APA

Rozplokhas, D., & Булычев, Д. Ю. (2018). Improving Refutational Completeness of Relational Search via Divergence Test. In Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming (Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming). Association for Computing Machinery. https://doi.org/10.1145/3236950.3236958

Vancouver

Rozplokhas D, Булычев ДЮ. Improving Refutational Completeness of Relational Search via Divergence Test. In Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. Association for Computing Machinery. 2018. (Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming). https://doi.org/10.1145/3236950.3236958

Author

Rozplokhas, Dmitri ; Булычев, Дмитрий Юрьевич. / Improving Refutational Completeness of Relational Search via Divergence Test. Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. Association for Computing Machinery, 2018. (Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming).

BibTeX

@inproceedings{0fd398463bd24951bb34da32a81af560,
title = "Improving Refutational Completeness of Relational Search via Divergence Test",
abstract = "We describe a search optimization technique for implementation of relational programming language miniKanren which makes more queries converge. Specifically, we address the problem of conjunction non-commutativity. Our technique is based on a certain divergence criterion that we use to trigger a dynamic reordering of conjuncts. We present a formal semantics of a miniKanren-like language and prove that our optimization does not compromise already converging programs, thus, being a proper improvement. We also present the prototype implementation of the improved search and demonstrate its application for a number of realistic specifications.",
author = "Dmitri Rozplokhas and Булычев, {Дмитрий Юрьевич}",
year = "2018",
month = sep,
day = "3",
doi = "10.1145/3236950.3236958",
language = "English",
series = "Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming",
publisher = "Association for Computing Machinery",
booktitle = "Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming",
address = "United States",

}

RIS

TY - GEN

T1 - Improving Refutational Completeness of Relational Search via Divergence Test

AU - Rozplokhas, Dmitri

AU - Булычев, Дмитрий Юрьевич

PY - 2018/9/3

Y1 - 2018/9/3

N2 - We describe a search optimization technique for implementation of relational programming language miniKanren which makes more queries converge. Specifically, we address the problem of conjunction non-commutativity. Our technique is based on a certain divergence criterion that we use to trigger a dynamic reordering of conjuncts. We present a formal semantics of a miniKanren-like language and prove that our optimization does not compromise already converging programs, thus, being a proper improvement. We also present the prototype implementation of the improved search and demonstrate its application for a number of realistic specifications.

AB - We describe a search optimization technique for implementation of relational programming language miniKanren which makes more queries converge. Specifically, we address the problem of conjunction non-commutativity. Our technique is based on a certain divergence criterion that we use to trigger a dynamic reordering of conjuncts. We present a formal semantics of a miniKanren-like language and prove that our optimization does not compromise already converging programs, thus, being a proper improvement. We also present the prototype implementation of the improved search and demonstrate its application for a number of realistic specifications.

U2 - 10.1145/3236950.3236958

DO - 10.1145/3236950.3236958

M3 - Conference contribution

T3 - Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming

BT - Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming

PB - Association for Computing Machinery

ER -

ID: 36966914