Constraint Programming on Infinite Data Streams

Lallouet, Arnaud; Law, Yat Chiu; Lee, Jimmy Ho-Man; Siu, Charles F. K.

doi:10.5591/978-1-57735-516-8/IJCAI11-107

Constraint Programming on Infinite Data Streams

Arnaud Lallouet, Yat Chiu Law, Jimmy Ho-Man Lee, Charles F. K. Siu

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 597-603.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-107

Abstract

Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over discrete time points. In this paper, we propose constraint programming on infinite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are specified by ω-regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space. We propose a search procedure that can recognize and avoid infinite search over duplicate search space. The solution set of a stream CSP can be represented by a Büchi automaton allowing stream values to be non-periodic. Consistency notions are defined to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.

Arnaud Lallouet, Yat Chiu Law, Jimmy Ho-Man Lee, and Charles F. K. Siu. 2011. Constraint Programming on Infinite Data Streams. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 597–603. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-107

@inproceedings{ijcai2011p107,
  title     = {Constraint Programming on Infinite Data Streams},
  author    = {Lallouet, Arnaud and Law, Yat Chiu and Lee, Jimmy Ho-Man and Siu, Charles F. K.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {597--603},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-107},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-107},
}

TY  - CPAPER
TI  - Constraint Programming on Infinite Data Streams
AU  - Lallouet, Arnaud
AU  - Law, Yat Chiu
AU  - Lee, Jimmy Ho-Man
AU  - Siu, Charles F. K.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 597
EP  - 603
DO  - 10.5591/978-1-57735-516-8/IJCAI11-107
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-107
ER  -