Interactive Configuration by Regular String Constraints

Details Interactive Configuration by Regular String Constraints Interactive Configuration by Regular String Constraints

2006-12-12

arxiv.org/abs/cs/0612068v1

Computer Science

Artificial Intelligence

Tech Report

Scientific paper

A product configurator which is complete, backtrack free and able to compute the valid domains at any state of the configuration can be constructed by building a Binary Decision Diagram (BDD). Despite the fact that the size of the BDD is exponential in the number of variables in the worst case, BDDs have proved to work very well in practice. Current BDD-based techniques can only handle interactive configuration with small finite domains. In this paper we extend the approach to handle string variables constrained by regular expressions. The user is allowed to change the strings by adding letters at the end of the string. We show how to make a data structure that can perform fast valid domain computations given some assignment on the set of string variables. We first show how to do this by using one large DFA. Since this approach is too space consuming to be of practical use, we construct a data structure that simulates the large DFA and in most practical cases are much more space efficient. As an example a configuration problem on $n$ string variables with only one solution in which each string variable is assigned to a value of length of $k$ the former structure will use $\Omega(k^n)$ space whereas the latter only need $O(kn)$. We also show how this framework easily can be combined with the recent BDD techniques to allow both boolean, integer and string variables in the configuration problem.

Affiliated with

Also associated with

No associations

Rating

Interactive Configuration by Regular String Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Interactive Configuration by Regular String Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive Configuration by Regular String Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-117645