Constraint Programming on Infinite Data Streams
Arnaud Lallouet, Yat-Chiu Law, Jimmy H. M. Lee, Charles F. K. Siu
Constrained problems of dynamic nature, such as ecology system and physical simulation, contain values that change over discrete time points. Such problems are unnatural to model as classical Constraint Satisfaction Problems (CSPs) since the domain values are infinite sequences containing possibly non-periodic values. We propose Constraint Programming on infinite data streams, which gives a useful tool for modeling time-varying problems. In our framework, variables take on stream values. A variable domain becomes a, possibly infinite, set of stream values, which is specified by an omega-regular language recognizable by Buchi automata. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space, but 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 Buchi automata allowing stream values to be non-periodic in nature. Consistency notions are defined to help reduce the search space early.