Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Analysis, synthesis and application of automaton-based constraint descriptions
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (ASTRA)
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
Keyword [en]
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: urn:nbn:se:uu:diva-332149ISBN: 978-91-513-0132-7 (print)OAI: oai:DiVA.org:uu-332149DiVA, id: diva2:1152391
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
List of papers
1. Automatic generation of descriptions of time-series constraints
Open this publication in new window or tab >>Automatic generation of descriptions of time-series constraints
2017 (English)In: Proc. 29th International Conference on Tools with Artificial Intelligence, IEEE Computer Society, 2017Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE Computer Society, 2017
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-332145 (URN)
Conference
ICTAI 2017, November 6–8, Boston, MA
Available from: 2017-10-24 Created: 2017-10-24 Last updated: 2018-01-13Bibliographically approved
2. Generation of implied constraints for automaton-induced decompositions
Open this publication in new window or tab >>Generation of implied constraints for automaton-induced decompositions
2013 (English)In: Proc. 25th International Conference on Tools with Artificial Intelligence, IEEE Computer Society, 2013, p. 1076-1083Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE Computer Society, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-218040 (URN)10.1109/ICTAI.2013.160 (DOI)978-1-4799-2971-9 (ISBN)
Conference
ICTAI 2013, November 4-6, Herndon, VA
Available from: 2014-02-06 Created: 2014-02-06 Last updated: 2018-01-11Bibliographically approved
3. Implied constraints for AUTOMATON constraints
Open this publication in new window or tab >>Implied constraints for AUTOMATON constraints
2015 (English)In: Global Conference on Artificial Intelligence: GCAI 2015, Manchester, UK: Cool Press , 2015, p. 113-126Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Manchester, UK: Cool Press, 2015
Series
EasyChair Proceedings in Computing, ISSN 2040-557X ; 36
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-268653 (URN)
Conference
GCAI 2015, October 16–18, Tbilisi, Georgia
Funder
Swedish Research Council
Available from: 2015-12-18 Created: 2015-12-09 Last updated: 2018-01-10Bibliographically approved
4. Time-series constraints: Improvements and application in CP and MIP contexts
Open this publication in new window or tab >>Time-series constraints: Improvements and application in CP and MIP contexts
Show others...
2016 (English)In: Integration of AI and OR Techniques in Constraint Programming, Springer, 2016, p. 18-34Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2016
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9676
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-298447 (URN)10.1007/978-3-319-33954-2_2 (DOI)000378993700002 ()978-3-319-33953-5 (ISBN)
Conference
CPAIOR 2016, May 29 – June 1, Banff, Canada
Available from: 2016-05-12 Created: 2016-07-04 Last updated: 2018-01-10Bibliographically approved
5. Linking prefixes and suffixes for constraints encoded using automata with accumulators
Open this publication in new window or tab >>Linking prefixes and suffixes for constraints encoded using automata with accumulators
Show others...
2014 (English)In: Principles and Practice of Constraint Programming: CP 2014, Springer, 2014, p. 142-157Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2014
Series
Lecture Notes in Computer Science ; 8656
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-238534 (URN)10.1007/978-3-319-10428-7_13 (DOI)978-3-319-10427-0 (ISBN)
Conference
CP 2014, September 8–12, Lyon, France
Funder
Swedish Research Council
Available from: 2014-09-12 Created: 2014-12-13 Last updated: 2018-01-11Bibliographically approved
6. Systematic derivation of bounds and glue constraints for time-series constraints
Open this publication in new window or tab >>Systematic derivation of bounds and glue constraints for time-series constraints
Show others...
2016 (English)In: Principles and Practice of Constraint Programming: CP 2016, Springer, 2016, p. 13-29Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2016
Series
Lecture Notes in Computer Science ; 9892
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-302048 (URN)10.1007/978-3-319-44953-1_2 (DOI)000389019700003 ()978-3-319-44952-4 (ISBN)
Conference
CP 2016, September 5–9, Toulouse, France
Funder
Swedish Research Council, 2011-6133Swedish Research Council, 2012-4908
Available from: 2016-08-23 Created: 2016-08-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

fulltext(789 kB)114 downloads
File information
File name FULLTEXT01.pdfFile size 789 kBChecksum SHA-512
a1084c818a674581375c84e8708e3f131ddab4d6fc2c4d91e4efc40089a503ef2630bcf2c22ee5bb83d36ecb73a561044842ddbad2e0543c9ce38de7489ea8ce
Type fulltextMimetype application/pdf
errata(92 kB)7 downloads
File information
File name ERRATA01.pdfFile size 92 kBChecksum SHA-512
9e425675668d721eb8bb9f15f7383cd4157ad9e8c27ad763dfda18c2e2b032bbfddcfd0ff89a93e452b4dc1022cd51fb82e503b71dfdd5b4d9b7f376a61e0933
Type errataMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
Francisco Rodríguez, María Andreína
By organisation
Division of Computing ScienceComputing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 114 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
v. 2.34-SNAPSHOT
|