Difference between revisions of "Strings"
(→Example) |
(→Options) |
||
| Line 13: | Line 13: | ||
==Options== | ==Options== | ||
| − | |||
| − | |||
| − | |||
To use finite model finding mode (false by default): | To use finite model finding mode (false by default): | ||
(set-option :strings-fmf true) | (set-option :strings-fmf true) | ||
| Line 27: | Line 24: | ||
To use the experimental functions (disabled by default): | To use the experimental functions (disabled by default): | ||
(set-option :strings-exp true) | (set-option :strings-exp true) | ||
| + | |||
| + | To set up string alphabet cardinality (256 by default, in progress): | ||
| + | (set-option :strings-alphabet-card n) | ||
==Strings== | ==Strings== | ||
Revision as of 09:08, 12 February 2014
This page is about strings in CVC4
Syntax
The Theory of Strings (Quantifier-Free) logic symbol:
(set-logic QF_S)
The logic symbol is IMPORTANT to the Theory of String, and it has to be set up. The default symbol (no symbol), or ALL_SUPPORTED symbol, does NOT work for Strings.
If the constraints contain more theories, please add them accordingly, e.g. if it contains BitVector, the symbol should be QF_SBV.
We are also developing an experimental version quantified string solver, please contact developers(tianyi-liang@uiowa.edu) for more information with quantifiers in Strings.
Options
To use finite model finding mode (false by default):
(set-option :strings-fmf true)
To set up depth of unrolling regular expression used by the theory of strings (10 by default):
(set-option :strings-regexp-depth 20)
To select the strategy of LB rule application: 0-lazy, 1-eager, 2-no (0 by default):
(set-option :strings-lb 1)
To use the experimental functions (disabled by default):
(set-option :strings-exp true)
To set up string alphabet cardinality (256 by default, in progress):
(set-option :strings-alphabet-card n)
Strings
To define a string variable:
(def-fun x () String)
String Concatenation:
(str.++ s t)
where s, t are string terms.
String Length:
(str.len s)
where s is a string term.
Regular Expression
Membership Constraint:
(str.in.re s r)
where s is a string term and r is a regular expression.
String to Regular Expression Conversion:
(str.to.re s)
where s is a string term. The statement turns a regular expression that only contains a string s.
Regular Expression Concatenation:
(re.++ r_1 r_2 ... r_n)
where r_1, r_2, ..., r_n are regular expressions.
Regular Expression Alternation:
(re.or r_1 r_2 ... r_n)
where r_1, r_2, ..., r_n are regular expressions.
Regular Expression Intersection:
(re.itr r_1 r_2 ... r_n)
where r_1, r_2, ..., r_n are regular expressions.
Regular Expression Kleene-Star:
(re.* r)
where r is a regular expression.
Regular Expression Kleene-Cross:
(re.+ r)
where r is a regular expression.
Regular Expression Option:
(re.opt r)
where r is a regular expression.
Regular Expression Range:
(re.range s t)
where s, t are single characters in double quotes, e.g. "a", "b". It returns a regular expression that contains any character between s and t.
Extension
Together with other engine in CVC4, we can extend new functionality in the theory of strings. For example,
(define-fun fun1 ((?x String) (?s String)) Bool
(or (= ?x ?s)
(> (str.len ?x) (str.len ?s))
))
Limitation
The decidability of this theory is unknown. For satisfiable problems (without extensions), our solver is sound, complete and terminating in the FMF mode. For unsatisfiable problems, the termination is not guaranteed; however, user can tune the options for termination.
Example
Find an assignment for x, where x."ab"="ba".x and the length of x equals to 7.
(set-logic QF_S) (declare-fun x () String) (assert (= (str.++ x "ab") (str.++ "ba" x))) (assert (= (str.len x) 7)) (check-sat)
Find assignments for x and y, where x and y are distinct and their lengths are equal.
(set-logic QF_S) (declare-fun x () String) (declare-fun y () String) (assert (not (= x y))) (assert (= (str.len x) (str.len y))) (check-sat)
Find assignments for x and y, where x.y != y.x.
(set-logic QF_S) (declare-fun x () String) (declare-fun y () String) (assert (not (= (str.++ x y) (str.++ y x)))) (check-sat)
Find a model for x, y and z, where x."ab".y=y."ba".z and z=x.y and x."a"!="a".x.
(set-logic QF_S) (declare-fun x () String) (declare-fun y () String) (declare-fun z () String) (assert (= (str.++ x "ab" y) (str.++ y "ba" z))) (assert (= z (str.++ x y))) (assert (not (= (str.++ x "a") (str.++ "a" x)))) (check-sat)
Find a model for x and y, where both x and y are in the RegEx (a*b)* and they are different but have the same length.
(set-logic QF_S)
(set-option :strings-fmf true)
(declare-fun x () String)
(declare-fun y () String)
(assert
(str.in.re x
(re.* (re.++ (re.* (str.to.re "a") ) (str.to.re "b") ))))
(assert (str.in.re y
(re.* (re.++ (re.* (str.to.re "a") ) (str.to.re "b") ))))
(assert (not (= x y)))
(assert (= (str.len x) (str.len y)))
(check-sat)
