### 6 Translation Procedure

The automated translation of a logical constraint to a linear mathematical constraint in LPL is
done in several steps applying various rules. Each rule is applied recursively on an (constraint)
expression tree. In the following transformation procedure, the index-set i ∈{1,…,n} is used for
indexed expressions, the names x and y or there indexed form x_{i} are used to denote arbitrary
expressions or just variables. The letter x or v_{i} denotes a single or indexed binary
variable.

To understand the transformation procedure, the concept of a “syntax tree” and the concept
of “cut-off” are introduced first. A syntax tree is a particular representation of an
arbitrary (constraint) expression. Figure 1 shows the syntax trees of the following three
expressions:

For binary operators like + (addition) or ∨ (or operator), the node (represented as a ellipse)
has a left and a right child connected by an arc, for unary operators like ¬ there is only a left
child (the right is a null pointer, see the node not.

Indexed operators as well as function calls are considered as unary operators: See Figure 2
which represents the three syntax trees of the expressions:

The concept of “cut-off” is the operation of cutting a subtree off the main syntax tree. In
mathematics, this operation is called “substitution”: a (sub-)expression is replaced by an
additional variable as in the following expression where yz is substituted by an additional
variable w :

Represented as a syntax tree, the original tree is decomposed into two (smaller) trees
as shown in Figure 3, the left trees is decomposed into the two expressions on the
right.

Boolean expressions can also be cut-off. In this case, the equality sign (=) must be replaced
by equivalence (↔). In most cases, however an implication (→) is sufficient. An example is
given as follows with x and y being Boolean propositions and p and q are numerical (real)
variables (the trees are shown in Figure 4) :

In the procedure below, a subtree containing real variables, numerical or relational operators
and where the root node is not a logical operator, is called R-subtree. For example, in
the left part of Figure 4, the subtree with the root of ≥ is a R-tree. The sequence
in which the following steps are applied has a large influence on on how efficient
the resulting expressions are. The sequence can somewhat change depending on the
expressions.