Norn, a solver for string constraints

Norn is a solver for string constraints, i.e. word equations over (unbounded length) string variables together with length and membership constraints.




The following examples demonstrate some features of Norn:


In this example, we assert that X belongs to two regular languages, and is of length 21. Norn constructs a length constraint from the intersection of the languages, and concludes that the problem is unsatisfiable. If the constant in the last assertion is changed to 20, the problem is satisfiable.

	    (set-logic QF_S)

	    (declare-fun X () String)

	    (assert ( X (re.++ (re.* ( "ab")) (re.* ( "dd")))))
	    (assert ( X (re.++ (re.* ( "abab")) (re.* ( "ddd")))))
	    (assert (= (str.len X) 21))



A simple example showing how the interaction between language, equality and length constraints can make a set of constraints unsatisfiable. If the last assertion is removed, the problem is satisfiable.

	    (set-logic QF_S)

	    (declare-fun A () String)
	    (declare-fun B () String)
	    (declare-fun C () String)
	    (declare-fun D () String)

	    (assert ( A (re.* ( "a"))))
	    (assert ( B (re.* ( "b"))))
	    (assert ( C (re.* ( "a"))))
	    (assert ( D (re.* ( "b"))))

	    (assert (= (str.++ A B) (str.++ C D)))

	    (assert (not (= (str.len A) (str.len C))))



We have evaluated Norn on two sets of benchmarks:

People Involved

For any questions or bug reports, please contact jari.stenman at