Browse Prior Art Database

Accurate projection of string constraints with concatentation

IP.com Disclosure Number: IPCOM000206738D
Publication Date: 2011-May-05
Document File: 4 page(s) / 44K

Publishing Venue

The IP.com Prior Art Database

Abstract

We address the problem of solving constraint satisfaction problems (CSP) with string constraints that include concatenation of strings. Our method offers accurate projections to string concatenation constraints. CSPs that include string constraints can be used in many applications and are incorporated in various constraints solvers. We address strings as regular expressions (RE) and represent the string variable domains using finite state machines (FSM) and perform the constraint projections using operations on FSMs.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 34% of the total text.

Page 01 of 4

Our method relates to a constraint with n string variables s1, ..., sn

with domains d

1,

..., dn and a regular expression R with domain dR and a constraint s1 || s2 || ... || sn LIKE R,

where

|| stands for concatenation.

Our method yields accurate projections of the domain d1, ..., dn,

where accurate

projections means that for all strings in any projected domain, there exist strings in the other domains such that the concatenation is in dR.

This is carried out in a "forward" phase where the variables s1, ..., sn are reduced in order but inaccurately. Then at a "backward" phase the variables are reduced in reverse order while correcting their domains so that they are accurate.

    We start the description of our method by demonstrating it on a simple concatenation constraint on two string vairables. Consider the constraint s1||s2 LIKE
R.

Let the FSM representing R be AR=<states=QR, initial-states=IR, final-states=FR,...>. Let the FSMs representing Si ,

where i

                         = 1,2 be Ai =<states=Qi, initial-states=Ii, final-states=Fi,...>. We build the projected FSMs A1' and A2' as follows:

A

will be based on a cross product of the A

1

and AR FSMs. The states in

A

1

'

1

'

are tuples of the form <q1,qR>

where q

1

in Q1, and qR in QR.

A

2

'

will be based on a cross product of the A

2

and AR FSMs. The states in

A

2

' are

tuples of the form <q2,qR>

where q

2

in Q1, and qR in QR.

A1' starts from initial states that combine initial states of both machines - I1 x I

R

.

We construct the transitions of A1' that exit a state-tuple <q1,qR> by looking for transitions with the same literals in the FSMs A1 and AR starting from q1, and qR respectively.

We start with a "pool" of tuple-states that contains the initial states of A1' as defined above.

We repeatedly compute the transitions from the states in the "pool", removing the source of the transitions from the pool and adding the (yet unvisited) targets of the transitions into the pool.

The final states of A1' are the tuples that combine final states of A1 (

with any state

of AR).

A

1' thus defines all the words from A1 that are prefixes of words from AR.

    A2' starts from initial state tuples that combine initial states of A2 and the AR states from the final state tuples of A1'.

We construct the transitions of A2' similarly to the way they were constructed for A1'
(i.e. by looking for transitions with the same literals). The state "pool" starts with the initial states of A2'.

The final states of A2' are the tuples that combine final states of A2 and final states of AR.

A

2' thus defines all the words from A2 that when preceded by some concatenation of

words from A

1' become words from AR.

After constructing

A

1' and A2',

we know that A

2' is an accurate projection,


Page 02 of 4

1' is a super set, since some final states of A1' do not lead to a final state

of R when continued by A2'. These states should be removed.
Now, consider the constraint of the form s1 || s2 || ... || sn LIKE R,

where s

however,

A

1, ...,

sn,...