---
title: "Constraint Programming on Infinite Data Streams"
authors:
  - "Arnaud Lallouet"
  - "Yat Chiu Law"
  - "Jimmy Ho-Man Lee"
  - "Charles F. K. Siu"
doi: "10.5591/978-1-57735-516-8/IJCAI11-107"
url: "https://ijcai.org/proceedings/2011/107"
pdf: "https://ijcai.org/proceedings/2011/0107.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "597-603"
track: ""
keywords:
---

# Constraint Programming on Infinite Data Streams

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

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 597-603. DOI: [10.5591/978-1-57735-516-8/IJCAI11-107](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.