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
Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search
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)
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2013. , 74 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1027
Keyword [en]
constraint programming, regular constraint, automaton constraint, context-free grammar constraint, solution neighbourhood, counter automaton
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-196347ISBN: 978-91-554-8617-4 (print)OAI: oai:DiVA.org:uu-196347DiVA: diva2:609984
Public defence
2013-04-26, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:00 (English)
Opponent
Supervisors
Available from: 2013-03-26 Created: 2013-03-08 Last updated: 2014-07-21Bibliographically approved
List of papers
1. An automaton constraint for local search
Open this publication in new window or tab >>An automaton constraint for local search
2011 (English)In: Fundamenta Informaticae, ISSN 0169-2968, E-ISSN 1875-8681, Vol. 107, 223-248 p.Article in journal (Refereed) Published
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-151745 (URN)10.3233/FI-2011-401 (DOI)000294729500006 ()
Available from: 2011-04-17 Created: 2011-04-17 Last updated: 2017-12-11Bibliographically approved
2. Solution neighbourhoods for constraint-directed local search
Open this publication in new window or tab >>Solution neighbourhoods for constraint-directed local search
2012 (English)In: Proc. 27th ACM Symposium on Applied Computing, New York: ACM Press, 2012, 74-79 p.Conference paper, Oral presentation only (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2012
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-186863 (URN)10.1145/2245276.2245294 (DOI)978-1-4503-0857-1 (ISBN)
Conference
SAC 2012, March 26-30, Riva del Garda, Italy
Available from: 2012-03-28 Created: 2012-11-29 Last updated: 2013-04-02Bibliographically approved
3. Underestimating the cost of a soft constraint is dangerous: Revisiting the edit-distance based soft regular constraint
Open this publication in new window or tab >>Underestimating the cost of a soft constraint is dangerous: Revisiting the edit-distance based soft regular constraint
2013 (English)In: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 19, no 5, 729-756 p.Article in journal (Refereed) Published
Abstract [en]

Many real-life problems are over-constrained, so that no solution satisfying all their constraints exists.  Soft constraints, with costs denoting how much the constraints are violated, are used to solve these problems.  We use the edit-distance based soft regular constraint as an example to show that a propagation algorithm that sometimes underestimates the cost may guide the search to incorrect (non-optimal) solutions to an over-constrained problem.  To compute correctly the cost for the edit-distance based soft regular constraint, we present a quadratic-time propagation algorithm based on dynamic programming and a proof of its correctness.  We also give an improved propagation algorithm using an idea of computing the edit distance between two strings, which may also be applied to other constraints with propagators based on dynamic programming.  The asymptotic time complexity of our improved propagator is always at least as good as the one of our quadratic-time propagator, but significantly better when the edit distance is small.  Our propagators achieve domain consistency on the problem variables and bounds consistency on the cost variable.  Our method can also be adapted for the violation measure of the edit-distance based regular constraint for constraint-based local search.

Keyword
constraint programming, soft regular constraint, edit distance, network flows, dynamic programming
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-195699 (URN)10.1007/s10732-013-9222-1 (DOI)000325021400001 ()
Funder
Swedish Research Council, 2007-6445Swedish Research Council, 2011-6133
Available from: 2013-02-26 Created: 2013-02-26 Last updated: 2017-12-06Bibliographically approved
4. Solving string constraints: The case for constraint programming
Open this publication in new window or tab >>Solving string constraints: The case for constraint programming
2013 (English)In: Principles and Practice of Constraint Programming: CP 2013, Springer Berlin/Heidelberg, 2013, 381-397 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, 8124
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-195702 (URN)10.1007/978-3-642-40627-0_31 (DOI)000329244000031 ()978-3-642-40626-3 (ISBN)
Conference
19th International Conference on Principles and Practice of Constraint Programming, Uppsala, Sweden, September 16-20, 2013
Funder
Swedish Research Council, 2007-6445Swedish Research Council, 2011-6133
Available from: 2013-09-18 Created: 2013-02-26 Last updated: 2014-02-06Bibliographically approved

Open Access in DiVA

fulltext(1190 kB)383 downloads
File information
File name FULLTEXT01.pdfFile size 1190 kBChecksum SHA-512
b45df7d5c84ec9e39f482ffd85e5b14953fc5c5b4dd0eb83743128e993aff644171c451f09f127c9be0e16ec7d50fc8794a345b155d508dac271f31bc0688337
Type fulltextMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
He, Jun
By organisation
Division of Computing ScienceComputing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 383 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: 1147 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