Sites Inria

Version française

Séminaire des équipes de recherche

Using Finite Transducers for Describing and Synthesising Structural Time-Series Constraints for Constraint Programming and Linear Programming

© INRIA Sophie Auvin - L comme Langage

  • Date : 2/11/2015
  • Place : Salle Verte1, Inria Italie
  • Guest(s) : Prof. Nicolas Beldiceanu, EPI TASC, Ecole des Mines de Nantes

We describe a large family of constraints for structural time series by means of function composition. These constraints are on aggregations of features of patterns that occur in a time series, such as the number of its peaks, or the range of its steepest ascent.

The patterns and features are usually linked to physical properties of the time series generator, which are important to capture in a constraint model of the system, i.e. a conjunction of constraints that produces similar time series. We formalise the patterns using finite transducers, whose output alphabet corresponds to semantic values that precisely describe the steps for identifying the occurrences of a pattern.Based on that description, we automatically synthesise constraint checkers as well as automata with accumulators . These automata can be used both in the context of constraint programming and of linear programming.

The description scheme not only unifies the structure of the existing 30 time-series constraints in the Global Constraint Catalogue, but also leads to over 600 new constraints, with more than 100,000 lines of synthesised code.

Keywords: Transducers Describing Synthesising Structural Time-Series Linear Lifeware Programming