Invariants for time-series constraints

Simple item page
dc.contributor.authorArafailova, Ekaterina
dc.contributor.authorBeldiceanu, Nicolas
dc.contributor.authorSimonis, Helmut
dc.contributor.funderHorizon 2020en
dc.contributor.funderFondation Mathématique Jacques Hadamarden
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2021-02-02T16:50:53Z
dc.date.available2021-02-02T16:50:53Z
dc.date.issued2020-07-18
dc.date.updated2021-02-02T16:38:02Z
dc.description.abstractMany 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.sponsorshipFondation Mathématique Jacques Hadamard (Gaspard Monge Program for Optimisation and Operations Research (PGMO));en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationArafailova, E., Beldiceanu, N. and Simonis, H. (2020) 'Invariants for time-series constraints', Constraints, 25(3), pp. 71-120. doi: 10.1007/s10601-020-09308-zen
dc.identifier.doi10.1007/s10601-020-09308-zen
dc.identifier.endpage120en
dc.identifier.issn1383-7133
dc.identifier.journaltitleConstraintsen
dc.identifier.startpage71en
dc.identifier.urihttps://hdl.handle.net/10468/11023
dc.identifier.volume25en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.projectinfo:eu-repo/grantAgreement/EC/H2020::RIA/640954/EU/Global systems Rapid Assessment tools through Constraint FUnctional Languages/GRACeFULen
dc.relation.projectinfo: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.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://link.springer.com/article/10.1007/s10601-020-09308-z
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: http://dx.doi.org/10.1007/s10601-020-09308-zen
dc.subjectRegister automatonen
dc.subjectTime-series constraintsen
dc.subjectLinear invarianten
dc.subjectNon-linear invarianten
dc.subjectParameterised invarianten
dc.subjectFinite automatonen
dc.titleInvariants for time-series constraintsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
revised_paper.pdf
Size:
1.04 MB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles