Invariants for time-series constraints

Show simple item record Arafailova, Ekaterina Beldiceanu, Nicolas Simonis, Helmut 2021-02-02T16:50:53Z 2021-02-02T16:50:53Z 2020-07-18
dc.identifier.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 en
dc.identifier.volume 25 en
dc.identifier.startpage 71 en
dc.identifier.endpage 120 en
dc.identifier.issn 1383-7133
dc.identifier.doi 10.1007/s10601-020-09308-z en
dc.description.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. en
dc.description.sponsorship Fondation Mathématique Jacques Hadamard (Gaspard Monge Program for Optimisation and Operations Research (PGMO)); en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer en
dc.rights © 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: en
dc.subject Register automaton en
dc.subject Time-series constraints en
dc.subject Linear invariant en
dc.subject Non-linear invariant en
dc.subject Parameterised invariant en
dc.subject Finite automaton en
dc.title Invariants for time-series constraints en
dc.type Article (peer-reviewed) en
dc.internal.authorcontactother Helmut Simonis, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en Access to this article is restricted until 12 months after publication by request of the publisher en 2021-07-18 2021-02-02T16:38:02Z
dc.description.version Accepted Version en
dc.internal.rssid 528833950
dc.internal.wokid WOS:000549805700001
dc.contributor.funder Horizon 2020 en
dc.contributor.funder Fondation Mathématique Jacques Hadamard en
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Constraints en
dc.internal.copyrightchecked Yes
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress en
dc.relation.project info:eu-repo/grantAgreement/EC/H2020::RIA/640954/EU/Global systems Rapid Assessment tools through Constraint FUnctional Languages/GRACeFUL en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/10/IN.1/I3032/IE/New Paradigms in Constraint Programming: Applications in Data Centres/ en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement