uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automatic generation of descriptions of time-series constraints
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)ORCID iD: 0000-0001-8730-4098
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
2017 (English)In: IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, 2017, p. 102-109Conference paper, Published paper (Refereed)
Abstract [en]

Integer time series are often subject to constraints on the aggregation of the features of all occurrences of some pattern within the series. For example, the number of inflexions may be constrained, or the sum of the peak maxima, or the minimum of the valley widths. Many time-series constraints can be described by transducers. The output alphabet of such a transducer consists of symbols that denote the phases of identifying the maximal occurrences of a pattern. It was recently shown how to synthesise automatically a constraint propagator and a constraint checker from such a transducer, which however has to be designed manually from a pattern. Here we define a large class of patterns, present an algorithm for automatically generating a low-level transducer from such a high-level pattern, and prove it correct. This class covers all 20 patterns of the Time-Series Constraint Catalogue, which can now be automatically extended at will.

Place, publisher, year, edition, pages
IEEE Computer Society, 2017. p. 102-109
Series
Proceedings-International Conference on Tools With Artificial Intelligence, ISSN 1082-3409
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-332145DOI: 10.1109/ICTAI.2017.00027ISBN: 978-1-5386-3876-7 (electronic)OAI: oai:DiVA.org:uu-332145DiVA, id: diva2:1152385
Conference
IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston, MA, November 6–8, 2017
Funder
Swedish Research Council, 2012-4908, 2015-0491Available from: 2018-06-07 Created: 2017-10-24 Last updated: 2019-02-28Bibliographically approved
In thesis
1. Analysis, synthesis and application of automaton-based constraint descriptions
Open this publication in new window or tab >>Analysis, synthesis and application of automaton-based constraint descriptions
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Constraint programming (CP) is a technology in which a combinatorial problem is modelled as a conjunction of constraints on variables ranging over given initial domains, and optionally an objective function on the variables. Such a model is given to a general-purpose solver performing systematic search to find constraint-satisfying domain values for the variables, giving an optimal value to the objective function. A constraint predicate (also known as a global constraint) does two things: from the modelling perspective, it allows a modeller to express a commonly occurring combinatorial substructure, for example that a set of variables must take distinct values; from the solving perspective, it comes with a propagation algorithm, called a propagator, which removes some but not necessarily all impossible values from the current domains of its variables when invoked during search.

Although modern CP solvers have many constraint predicates, often a predicate one would like to use is not available. In the past, the choices were either to reformulate the model or to write one's own propagator. In this dissertation, we contribute to the automatic design of propagators for new predicates.

Integer time series are often subject to constraints on the aggregation of the features of all maximal occurrences of some pattern. For example, the minimum width of the peaks may be constrained. Automata allow many constraint predicates for variable sequences, and in particular many time-series predicates, to be described in a high-level way. Our first contribution is an algorithm for generating an automaton-based predicate description from a pattern, a feature, and an aggregator.

It has previously been shown how to decompose an automaton-described constraint on a variable sequence into a conjunction of constraints whose predicates have existing propagators. This conjunction provides the propagation, but it is unknown how to propagate it efficiently. Our second contribution is a tool for deriving, in an off-line process, implied constraints for automaton-induced constraint decompositions to improve propagation. Further, when a constraint predicate functionally determines a result variable that is unchanged under reversal of a variable sequence, we provide as our third contribution an algorithm for deriving an implied constraint between the result variables for a variable sequence, a prefix thereof, and the corresponding suffix.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2017. p. 79
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1591
Keywords
constraint programming, constraint predicates, global constraints, automata, automaton-described constraint predicates, automaton-induced constraint decompositions, implied constraints, time-series constraints, transducers, automaton invariants
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-332149 (URN)978-91-513-0132-7 (ISBN)
Public defence
2017-12-15, ITC 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2017-11-22 Created: 2017-10-24 Last updated: 2018-03-07

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Francisco Rodríguez, María AndreínaFlener, PierrePearson, Justin

Search in DiVA

By author/editor
Francisco Rodríguez, María AndreínaFlener, PierrePearson, Justin
By organisation
Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 191 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf