Invariants for time-series constraints

Loading...
Thumbnail Image
Files
revised_paper.pdf(1.04 MB)
Accepted version
Date
2020-07-18
Authors
Arafailova, Ekaterina
Beldiceanu, Nicolas
Simonis, Helmut
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Research Projects
Organizational Units
Journal Issue
Abstract
Many constraints restricting the result of some computations over an integer sequence can be compactly represented by counter automata. We improve the propagation of the conjunction of such constraints on the same sequence by synthesising a database of linear and non-linear invariants using their counter-automaton representation. The obtained invariants are formulae parameterised by the sequence length and proven to be true for any long enough sequence. To assess the quality of such linear invariants, we developed a method to verify whether a generated linear invariant is a facet of the convex hull of the feasible points. This method, as well as the proof of non-linear invariants, are based on the systematic generation of constant-size deterministic finite automata that accept all integer sequences whose result verifies some simple condition. We apply such methodology to a set of 44 time-series constraints and obtain 1400 linear invariants from which 70% are facet defining, and 600 non-linear invariants, which were tested on short-term electricity production problems.
Description
Keywords
Register automaton , Time-series constraints , Linear invariant , Non-linear invariant , Parameterised invariant , Finite automaton
Citation
Arafailova, E., Beldiceanu, N. and Simonis, H. (2020) 'Invariants for time-series constraints', Constraints, 25(3), pp. 71-120. doi: 10.1007/s10601-020-09308-z
Copyright
© Springer Science+Business Media, LLC, part of Springer Nature 2020. This is a post-peer-review, pre-copyedit version of an article published in Constraints The final authenticated version is available online at: http://dx.doi.org/10.1007/s10601-020-09308-z