4.1 The formula-based approach

We start by analyzing the property which is a crux for the possibility that logical formulas represent functions in the traditional way: the value of a formula $\varphi$ according to some valuation v is determined only by the values associated to a finite set of propositional variables $\mathbf{X}$ such that $\mathrm{Var}(\varphi)\subset\mathbf{X}$ . Thus, if $\mathbf{X}$ is semantically identified to the domain of a function, formula $\varphi$ may semantically express all the values such function. Let us generalize this notion.

• For any $\langle{x_1,\ldots,x_n}\rangle\in[0,1]^n$ , there exists at least one valuation $v\in\mathbf{Val}_\Phi$ , such that $v(X_j)=x_j$ , for $j=1,\ldots,n$ ; and

• For any pair of valuations $v,v'\in\mathbf{Val}_\Phi$ such that $v(X_j)=v'(X_j)$ , for $j=1,\ldots,n$ , we have that $v(\varphi)=v'(\varphi)$ —i.e. valuations in $\mathbf{Val}_\Phi$ are truth-functional on variables in $\mathbf{X}_n$ .

For instance, for any formula $\varphi$ such that $\mathrm{Var}(\varphi)\subset\mathbf{X}_n$ , $\mathbf{X}_n$ determines $\varphi$ modulo $\emptyset$ -satisfiable, by truth-functionality and the fact that $\mathbf{Val}_\emptyset = \mathbf{Val}$ . Then, representation modulo satisfiability in the formula-based approach is defined in a way that retrieves property (3).

• $\mathbf{X}_n$ determines $\varphi$ modulo $\Phi$ -satisfiable; and

• $f(v(X_1),\ldots,v(X_n)) = v(\varphi)$ , for all $v\in\mathbf{Val}_\Phi$ .

The definition of representation modulo satisfiability in the formula-based approach adapts property (3) from unrestricted to restricted valuations, as required by the semantics modulo satisfiability. The next example should clarify the usage of such property.

4.2 The function-based approach

Finger and Preto (Reference Finger and Preto2020) proposed a function-based definition of representation modulo satisfiability that constained the domain of a traditionally represented function. We review such approach in the following.

We extend the notion of associating functions from formulas to a pair $\langle{\varphi,\Phi}\rangle$ , where $\varphi$ is a formula and $\Phi$ is a set of formulas, with $\textrm{Var}(\varphi) \cup \textrm{Var}(\Phi) \subset \mathbf{X}_m$ , as follows. First, let the function domain be

\begin{align*}D_{\langle{\varphi,\Phi}\rangle} = \Big\{ \langle{x_1,\ldots,x_m}\rangle \in [0,1]^m ~\Big|~ f_\psi(x_1,\ldots,x_m) = 1, \textrm{ for all } \psi\in\Phi \Big\}.\end{align*}

Then we inductively define function $f_{\langle{\varphi,\Phi}\rangle}:D_{\langle{\varphi,\Phi}\rangle}\to [0,1]$ by the following clauses in total analogy to (i)–(iii) in the beginning of Section 3:

1. (i) $f_{\langle{X_j,\Phi}\rangle}(x_1,\ldots,x_m) = x_j$ , for $j=1,\ldots,m$ ;

2. (ii) $f_{\langle{\lnot\varphi,\Phi}\rangle}(x_1,\ldots,x_m) = 1-f_{\langle{\varphi,\Phi}\rangle}(x_1,\ldots,x_m)$ ;

3. (iii) $f_{\langle{\varphi\oplus\psi,\Phi}\rangle}(x_1,\ldots,x_m) = \min\!\left(1,f_{\langle{\varphi,\Phi}\rangle}\left(x_1,\ldots,x_m\right) + f_{\langle{\psi,\Phi}\rangle}\left(x_1,\ldots,x_m\right)\right)$ .

The definitions of $D_{\langle{\varphi,\Phi}\rangle}$ and $f_{\langle{\varphi,\Phi}\rangle}$ depend on m. In the function-based approach, we have the following definition.

• For any $\langle{x_1,\ldots,x_m}\rangle\in D_{\langle{\varphi,\Phi}\rangle}$ , $x_{n+j} = z_j(x_1,\ldots,x_n)$ , $j=1,\ldots,m-n$ ;

• For any $\langle{x_1,\ldots,x_n}\rangle\in[0,1]^n$ , $f(x_1,\ldots,x_n) = f_{\langle{\varphi,\Phi}\rangle}(x_1,\ldots,x_n,z_1(x_1,\ldots,x_n),\ldots,z_{m-n}(x_1,\ldots,x_n))$ .

We write $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle$ and $\mathbf{z}=\langle{x_{n+1},\ldots,x_m}\rangle$ .

In the functional representation modulo satisfiability, a pair $\langle{\varphi,\Phi}\rangle$ functionally represents a function $f:[0,1]^n\to [0,1]$ when formula $\varphi$ is the traditional representation of another function $f_\varphi:[0,1]^m\to [0,1]$ whose domain $[0,1]^m$ has possibly higher dimension – $m\geq n$ – and can be constrained to $D_{\langle{\varphi,\Phi}\rangle}\subset [0,1]^m$ in order to be identified with the domain $[0,1]^n$ of the original function f; elements $\mathbf{x}\in[0,1]^n$ are identified with elements $\langle{\mathbf{x},\mathbf{z}}\rangle\in D_{\langle{\varphi,\Phi}\rangle}$ and it must hold that $f(\mathbf{x})=f_{\langle{\varphi,\Phi}\rangle}(\mathbf{x},\mathbf{z})$ . Note that the constraining from $[0,1]^m$ to $D_{\langle{\varphi,\Phi}\rangle}$ is a disguised application of semantics modulo satisfiability since $\langle{x_1,\ldots,x_m}\rangle\in D_{\langle{\varphi,\Phi}\rangle}$ if, and only if, there is a valuation $v\in\mathbf{Val}_\Phi$ such that $v(X_1)=x_1,\ldots,v(X_m)=x_m$ .

Example 2. The representation for function $f:[0,1]\to [0,1]$ , given by $f(x_1)=\frac{x_1}{2}$ , in Example 1 is almost a functional representation for it; we only need to replace $Z_1$ and $Z_{{1}/{2}}$ by $X_2$ and $X_3$ to fit the definition, which results in $\langle{X_2,\Phi}\rangle$ , where $\Phi = \{ X_2\oplus X_2 \leftrightarrow X_1, ~ X_3\leftrightarrow\lnot X_3, ~ X_2\to X_3 \}$ . In this case, we have $n=1$ , $m=3$ and

\begin{equation*} D_{\langle{\varphi,\Phi}\rangle} = \Big\{ \langle{x_1,x_2,x_3}\rangle \in [0,1]^3 ~~\Big|~~ x_1\in [0,1], ~~ x_2=\frac{x_1}{2}, ~~ x_3=\frac{1}{2} \Big\}. \end{equation*}

Then, there are functions $z_1:[0,1]\to [0,1]$ and $z_2:[0,1]\to [0,1]$ given by $z_1(x_1) = \frac{x_1}{2}$ and $z_2(x_1) = \frac{1}{2}$ . And we have that

\begin{equation*} f(x_1) = \frac{x_1}{2} = z_1(x_1) = f_{\langle{\varphi,\Phi}\rangle}(x_1,z_1(x_1),z_2(x_1)). \end{equation*}

Note that function $f_\varphi:[0,1]^3\to [0,1]$ is given by $f_\varphi(x_1,x_2,x_3) = x_2$ . Figure 1 has graphs of the functions $f_\varphi$ and $f_{\langle{\varphi,\Phi}\rangle}$ and of the set $D_{\langle{\varphi,\Phi}\rangle}$ .

Figure 1.

Graphs of functions $f_\varphi$ and $f_{\langle{\varphi,\Phi}\rangle}$ and of set $D_{\langle{\varphi,\Phi}\rangle}$ in Example 2, for fixed $x_3=\frac{1}{2}$ .

4.3 Formula-based versus function-based approaches

We have seen two attempts to formalize a concept of representation modulo satisfiability. Each approach has the virtue of elucidating some different aspects of the technique that provides a pair $\langle{\varphi,\Phi}\rangle$ , where $\varphi$ is a representative formula and $\Phi$ is a set of constraining formulas. In this way, one might wonder whether they formalize the same concept. In fact, despite the similarity, the function-based presentation is a bit more restrictive than the formula-based one; the former constrains the values of $x_{n+j}$ , for $j=1,\ldots,m-n$ , to be functions $z_j(x_1,\ldots,x_n)$ , for any $\langle{x_1,\ldots,x_m}\rangle\in D_{\langle{\varphi,\Phi}\rangle}$ , so that the set $D_{\langle{\varphi,\Phi}\rangle}$ is minimal.

In order to make both presentations equivalent, we should restrict the formula-based one by adding to Definition 1 the following items:

• $\mathrm{Var}(\varphi)\cup\mathrm{Var}(\Phi) = \mathbf{X}_m$ , $m\geq n$ ;

• For any pair of valuations $v,v'\in\mathbf{Val}_\Phi$ such that $v(X_j)=v'(X_j)$ , for $j=1,\ldots,n$ , we have that $v(X_j)=v'(X_j)$ , for $j=n+1,\ldots,m$ .

The first item above only standardizes propositional variables to appear in $\varphi$ and $\Phi$ ; such standardization was intended to ease the inductive process of associating functions to formulas in the formula-based approach. The second item constrains, for valuations in $\mathbf{Val}_\Phi$ , the values of propositional variables in $\mathbf{X}_m\setminus\mathbf{X}_n$ as functions of the values of propositional variables in $\mathbf{X}_n$ ; this is stronger than the original definition which only constrains the value of $\varphi$ – indeed these new items yield that the value of $\varphi$ is invariant – and is the counterpart to the constraints to elements in $D_{\langle{\varphi,\Phi}\rangle}$ by functions $z_1,\ldots,z_{m-n}$ . We refer to the more restrictive form of Definition 1 as strong determination modulo satisfiability and to the consequent more restrictive form of Definition 2 as strong representation modulo satisfiability.

From now on, we choose to deal with the formula-based approach to represent functions modulo satisfiability, as we deem it a clearer and less restrictive definition. Moreover, we will only refer to the version presented in Section 4.1 (not the strong one) as fixing the value of $\varphi$ modulo $\Phi$ -satisfiable is enough for establishing a satisfactory concept of representation. However, all the constructions of representations to follow also fix the values of the additional propositional variables (other than the ones in $\mathbf{X}_n$ ) modulo $\Phi$ -satisfiable; thus, for them to be strong representations, only the standardization of the propositional variables is missing.

5.1 Regional format of rational McNaughton functions

The algorithm we present later uses a lattice representation of rational McNaughton functions; before that we employ an encoding as follows. A rational McNaughton function $f:[0,1]^n\to [0,1]$ is in regional format if it is given by m (not necessarily distinct) linear pieces

(4) \begin{align}p_i(\mathbf{x})= \gamma_{i0} + \gamma_{i1}x_1 + \cdots + \gamma_{in}x_n,\end{align}

for $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in [0,1]^n$ , $\gamma_{ij}\in\mathbb{Q}$ and $i=1,\ldots,m$ , with each linear piece $p_i$ identical to f over a convex set $\Omega_i\subset [0,1]^n$ called region such that:

• $\bigcup_{i=1}^m\Omega_i = [0,1]^n$ ;

• $\Omega_{i}^\circ\cap\Omega_{j}^\circ=\emptyset$ , for $i\neq j$ ;

• Regions $\Omega_i$ are given in such a way that there is a polynomial procedure to determine whether or not a linear piece $p_k$ is above other linear piece $p_i$ over region $\Omega_i$ , that is whether or not $p_k(\mathbf{x})\geq p_i(\mathbf{x})$ , for all $\mathbf{x}\in\Omega_i$ ;

• Linear pieces and regions satisfy the lattice property, that is, for $i\neq j$ , there is k such that linear piece $p_i$ is above linear piece $p_k$ over region $\Omega_i$ and linear piece $p_k$ is above linear piece $p_j$ over region $\Omega_j$ .

The regional format allows for the repetition of linear pieces so that there is a one-to-one correspondence between regions and pieces. In this format, the size of a function is the sum of the number of bits necessary to represent its linear pieces coefficients as fractions $\frac{a}{b}$ plus the space necessary for representing its regions in some encoding. We discuss the regional format further at the end of this section.

Example 4. Rational McNaughton function f with graph in Figure 2a may be given by the linear pieces $p_1(x_1,x_2) = \frac{4}{9} + \frac{2}{3}x_2$ , $p_2(x_1,x_2) = \frac{5}{6} - \frac{1}{2}x_2$ and $p_3(x_1,x_2) = \frac{4}{3} - x_1$ . Regions $\Omega_i$ associated to each linear piece are depicted in Figure 2b and described in Table 1; we soon tackle the problem of deciding if a linear piece is above another.

Figure 2.

Graph of rational McNaughton function in Example 4.

Table 1.

Regions $\Omega_i$ for function f in Example 4

Let us deal with the encoding of regions. First, we characterize them in next result.

Since the closure $\textrm{cl}(\Omega)$ of region $\Omega$ is a polyhedron, it may be entirely described as the finite intersection of half-spaces given by linear inequalities as

(5) \begin{align}\textrm{cl}(\Omega) = \Big\{ \mathbf{x}\in [0,1]^n ~\Big|~ \omega_{i0} + \omega_{i1} x_1 + \cdots + \omega_{in} x_n \geq 0,~ i=1,\ldots,\lambda_\Omega \Big\}.\end{align}

We show a polynomial procedure for deciding if a linear piece $p_k$ is above another linear piece $p_i$ over region $\Omega_i$ that takes polyhedron $\textrm{cl}(\Omega_i)$ given by (5) as input. Let $p_k$ and $p_i$ be given by

\begin{align*}p_k(\mathbf{x}) &= \gamma_{k0} + \gamma_{k1}x_1 + \cdots + \gamma_{kn}x_n, \\p_i(\mathbf{x}) &= \gamma_{i0} + \gamma_{i1}x_1 + \cdots + \gamma_{in}x_n,\end{align*}

where $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle$ . In order to decide if $p_k$ is above $p_i$ over $\Omega_i$ , Algorithm 1 analyzes the optimal value of the maximization linear program:

\begin{align*}\begin{array}{lll}\max & p_i-p_k \\\mbox{subject to} & \textrm{cl}(\Omega_i)\end{array}\end{align*}

We call $\textrm{MAX}(f,P)$ the routine that computes maximum value of an objective function f over polyhedron P. It is known that such linear programming problem may be solved in polynomial time Bertsimas and Tsitsiklis (Reference Bertsimas and Tsitsiklis1997).

Algorithm 1

ABOVE-MAX: decides if a linear piece is above another one over a region

Proof. We have that $p_k(\mathbf{x})\geq p_i(\mathbf{x})$ , for $\mathbf{x}\in\Omega_i$ if, and only if,

(6) \begin{align} p_i(\mathbf{x})-p_k(\mathbf{x}) \leq 0, \end{align}

for $\mathbf{x}\in\Omega_i$ . Let M be the maximum value of the objective function $p_i(\mathbf{x})-p_k(\mathbf{x})$ in $\textrm{cl}(\Omega_i)$ and let $\mathbf{x}_M\in\textrm{cl}(\Omega_i)$ be an argument where the objective function has value M. In case $M\leq 0$ , then (6) is satisfied by all $\mathbf{x}\in\Omega_i\subset\textrm{cl}(\Omega_i)$ . In case $M>0$ , then, either $\mathbf{x}_M\in\Omega_i$ fails to fulfill (6) or, if $\mathbf{x}_M\in\partial\Omega_i$ , there is some $\mathbf{x}\in\Omega_i$ which fails to do so, by the continuity of the objective function. The correctness of Algorithm 1 follows from these remarks and, as MAX is a polynomial routine, it terminates in polynomial time.

In view of Theorem 6, it is enough to encode regions $\Omega$ in such a way that there is a polynomial procedure to compute $\textrm{cl}(\Omega)$ as in (5). Moreover, from continuity of rational McNaughton function f, we have that $f(\mathbf{x})=p_i(\mathbf{x})$ , for any $\mathbf{x}\in\textrm{cl}(\Omega_i)$ , so a natural standardization is to consider regions that are already polyhedra given by (5). We say that functions given this way are in closed regional format; this is the case in Example 4.

We should establish that any rational McNaughton function may be put in (closed) regional format. Let $f:[0,1]^n\to [0,1]$ be a rational McNaughton function with distinct linear pieces $p_1,\ldots,p_{\bar{m}}$ ; for each permutation $\rho$ of the set $\{1,\ldots,\bar{m}\}$ , we define the polyhedron

(7) \begin{align}P_\rho = \Big\{ \mathbf{x}\in [0,1]^n ~\Big|~ p_{\rho(1)}(\mathbf{x}) \geq \cdots \geq p_{\rho(\bar{m})}(\mathbf{x}) \Big\}.\end{align}

Let $\mathcal{C}$ be the set of n-dimensional polyhedra $P_\rho$ , for some permutation $\rho$ .

1. 1. $\bigcup\mathcal{C}=[0,1]^n$ .

2. 2. For polyhedron $P\in\mathcal{C}$ and indexes $i',i''\in\{1,\ldots,\bar{m}\}$ with $i'\neq i''$ , $p_{i'}(\mathbf{x})\neq p_{i''}(\mathbf{x})$ , for any $\mathbf{x}\in P^\circ$ .

3. 3. $P'^\circ\cap P''^\circ=\emptyset$ , for $P',P''\in\mathcal{C}$ such that $P'\neq P''$ .

4. 4. For each polyhedron $P\in\mathcal{C}$ , there is an index $i_P\in\{1,\ldots,\bar{m}\}$ such that $f(\mathbf{x})=p_{i_P}(\mathbf{x})$ , for $\mathbf{x}\in P$ .

5. 5. For polyhedra $P',P''\in\mathcal{C}$ , there is an index $k\in\{1,\ldots,\bar{m}\}$ such that $p_{i_{P'}}$ is above $p_k$ over P’ and $p_k$ is above $p_{i_{P''}}$ over P”.

Polyhedra in $\mathcal{C}$ may play the role of regions in regional format since they are convex sets with the properties above; note that the same linear piece $p_i$ may be f-associated to many distinct polyhedra. Determining whether a linear piece $p_k$ is above other linear piece $p_i$ over $P\in\mathcal{C}$ boils down to comparing their values for some point $\mathbf{x}\in P^\circ$ . Thus, any rational McNaughton function may be encoded in regional format. Figure 2c shows the permutation-based region configuration $\mathcal{C}$ for the function in Example 4.

The regional format assures sufficient conditions and information about the ordering of linear pieces over its region configuration which are required for a lattice representation, i.e. a representation that comes from the application of lattice operations to the linear pieces of a given continuous piecewise linear function. For instance, Mundici (Reference Mundici1994) uses a lattice representation for representing McNaughton functions in ${{\unicode{x0141}}_\infty}$ – which was adapted by Finger and Preto (Reference Finger and Preto2020) for representing rational McNaughton functions in ${{\unicode{x0141}}_\infty}$ -MODSAT – that requires conditions and information from the region configuration given by the decomposition in simplices of the polyhedra $P_\rho$ in $\mathcal{C}$ ; this path has also been followed in the literature for representing continuous piecewise linear functions in other ${{\unicode{x0141}}_\infty}$ -based logical systems; see Section 3.

The setback with describing a rational McNaughton function using the set $\mathcal{C}$ of polyhedra is that, in the worst case, $|\mathcal{C}|=\bar{m}!$ ; the situation may be even worse when decompositions in simplices are considered. However, in many cases, regional format is able to encompass sufficient conditions and information for lattice representation with a smaller set of regions; Figure 2 shows such contrast related to Example 4 and it may also be seen in the classes of functions in Section 6. This feature does not interfere with the complexity of the general algorithm in Section 5.3, since it only amounts to a possible reduction of the input size, but it might yield a gain in the complexity of the representation of inputs and, therefore, make some applications viable. Of course that if a more compact encoding of rational McNaughton functions is provided, a side effect might be an inefficient translation from such encoding to the regional format. However, we are unaware of methods that perform representations in a ${{\unicode{x0141}}_\infty}$ -based logical system which require less conditions or information than the provided by regional format or do not apply lattice representations.

5.2 A particular case: Truncated linear functions

Let us show the possibility of representing a rational McNaughton function in ${{\unicode{x0141}}_\infty}$ -MODSAT and develop a polynomial algorithm for computing such representation in the particular case that function is a truncated linear polynomial with rational coefficients, defined in the following.

Let $p:[0,1]^n\to\mathbb{R}$ be a nonzero linear polynomial given by

(8) \begin{align}p(\mathbf{x})= \frac{a_0}{b_0} + \frac{a_1}{b_1}x_1 + \cdots + \frac{a_n}{b_n}x_n,\end{align}

for $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in[0,1]^n$ , $a_j\in\mathbb{Z}$ and $b_j\in\mathbb{Z}^*_+$ . We want to build a representation for the function $p^\#:[0,1]^n\to [0,1]$ given by

(9) \begin{align}p^\#(\mathbf{x}) = \min\!\Big(1,\max\!\big(0,p(\mathbf{x})\big)\Big).\end{align}

We have that $p^\#(\mathbf{x})=0$ , if $p(\mathbf{x})<0$ ; $p^\#(\mathbf{x})=1$ , if $p(\mathbf{x})>1$ ; and $p^\#(\mathbf{x})=p(\mathbf{x})$ , otherwise.

In order to rewrite expression (8), we define:

\begin{align*}\alpha_j &= a_j, \text{ for $j\in P$;} \\\alpha_j &= -a_j, \text{ for $j\in N$;} \\\beta_j &= \beta\cdot b_j, \text{ for $j=0,\ldots,n$;}\end{align*}

where $j\in P$ , if $a_j>0$ , and $j\in N$ , if $a_j<0$ , with $P\cup N\subset\{0,\ldots,n\}$ , and $\beta$ is the least integer greater than or equal to

\begin{align*}\max\left\{ \sum_{j\in P} \frac{a_j}{b_j},~~-\sum_{j\in N} \frac{a_j}{b_j} \right\}.\end{align*}

We have that $\alpha_j\in\mathbb{Z}_+$ and $\beta_j\in\mathbb{Z}_+^*$ , for $j=0,\ldots,n$ . Let $x_0=1$ and define functions $p_P:[0,1]^n\to\mathbb{R}$ and $p_N:[0,1]^n\to\mathbb{R}$ , for $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in [0,1]^n$ , by

(10) \begin{align}p_P(\mathbf{x})=\sum_{j\in P} \frac{\alpha_j}{\beta_j}x_j;\,\,\,\,\,\,\,\,\,\,\, p_N(\mathbf{x})=\sum_{j\in N} \frac{\alpha_j}{\beta_j}x_j.\end{align}

Let $Z^p_j,Z_{{1}/{\beta_j}}\in\mathbb{P}$ ; for a set of indexes $J\in\{P,N\}$ , define:

\begin{equation*}\tilde{\varphi}_J = \bigoplus_{j\in J\setminus\{0\}} \alpha_j Z^p_j;\, \, \, \, \, \, \, \, \tilde{\Phi}_J = \bigcup_{j\in J\setminus\{0\}} \left\{ \varphi_\frac{1}{\beta_j},~~ \beta_jZ^p_j\leftrightarrow X_j,~~ Z^p_j\to Z_\frac{1}{\beta_j} \right\}.\end{equation*}

And then, define:

(11) \begin{align}\begin{array}{lll} \bar{\varphi}_J = \tilde{\varphi}_J, & \bar{\Phi}_J = \tilde{\Phi}_J, & \textrm{ if $0\notin J$;} \\ \bar{\varphi}_J = \alpha_0 Z_\frac{1}{\beta_0}\oplus\tilde{\varphi}_J, & \bar{\Phi}_J = \tilde{\Phi}_J\cup\{\varphi_{\frac{1}{\beta_0}}\}, & \textrm{ otherwise.} \end{array}\end{align}

For the final step toward a representation for $p^\#$ , we define:

(12) \begin{align}\bar{\varphi}_p = \beta[\lnot(\bar{\varphi}_P\to\bar{\varphi}_N)], \bar{\Phi}_p = \bar{\Phi}_P\cup\bar{\Phi}_N.\end{align}

In order to set up a polynomial algorithm for computing a representation $\langle{\varphi_p,\Phi_p}\rangle$ for $p^\#$ , we analyze more closely expressions $n\psi$ , which show up in $\bar{\varphi}_p$ and in formulas in $\bar{\Phi}_p$ . These expressions are exponential in the binary representation of n since they denote n-fold repetitions of a formula $\psi$ . We deviate from this situation by using $\lfloor\log n\rfloor+1$ new propositional variables $\xi^0_\psi,\xi^1_\psi,\ldots,\xi^{\lfloor\log n\rfloor}_\psi$ and replacing every occurrence of $n\psi$ , where $n\in\mathbb{N}\setminus\{0,1\}$ , with the formula

(13) \begin{align}\xi_{n\psi}=_\mathrm{def}\bigoplus_{\substack{k=0\\n_k=1}}^{\lfloor\log n\rfloor} \xi^k_\psi,\end{align}

where $n_k\in\{0,1\}$ comes from the binary representation $\sum_{k=0}^{\lfloor\log n\rfloor} 2^kn_k$ of n, and by adding the following formulas to $\bar{\Phi}_p$ :

(14) \begin{align} \begin{array}{ll} \xi^0_\psi &\leftrightarrow \psi; \\[4pt] \xi^k_\psi &\leftrightarrow \xi^{k-1}_\psi\oplus\xi^{k-1}_\psi, \text{ for $k=1,\ldots,\lfloor\log n\rfloor$}. \end{array}\end{align}

These formulas define the propositional variables $\xi^k_\psi$ and we call $\Xi_{n\psi}$ the set that comprehends them. In this way, we avoid exponential blow up as shown in Theorem 10.

We set $\langle{\varphi_p,\Phi_p}\rangle$ from $\langle{\bar{\varphi}_p,\bar{\Phi}_p}\rangle$ in (12) by properly replacing all occurrences of $n_l\psi_l$ as stated in the above theorem. By construction, $\langle{\varphi_p,\Phi_p}\rangle$ is given by

(15) \begin{align}\varphi_p = \beta[\lnot(\varphi_P\to\varphi_N)];\,\,\,\,\,\,\,\,\,\, \Phi_p = \Phi_P\cup\Phi_N;\end{align}

where $\varphi_P$ , $\varphi_N$ , $\Phi_P$ , and $\Phi_N$ are properly defined from their barred correspondents in (11). Table 2 shows how functions in Example 4 can be represented as in Theorem 10.

Table 2.

Representations as in (15) for functions $p_1^\#$ , $p_2^\#$ and $p_3^\#$ , where functions $p_1$ , $p_2$ , and $p_3$ are from Example 4

Algorithms 2 and 3 compute the representation of $n\psi$ in ${{\unicode{x0141}}_\infty}$ -MODSAT in time $O(\log n)$ assuming that propositional variables are all represented with a constant size. Algorithm 2 returns $\mathbf{0}$ and $\psi$ in the limit cases $n=0$ and $n=1$ (lines 1–5); when $n\in\mathbb{N}\setminus\{0,1\}$ , it returns formula $\xi_{n\psi}$ in (13) by building it in line 6 plus a $\lfloor\log n\rfloor+1$ iteration loop (lines 7–13) where the $n_k$ ’s in the binary representation of n are calculated by the routine in lines 8 and 9. Algorithm 3 returns $\emptyset$ in the limit cases $n=0$ and $n=1$ (lines 1–3); when $n\in\mathbb{N}\setminus\{0,1\}$ , it returns set $\Xi_{n\psi}$ that comprehends formulas (14) by building it in line 4 plus a $\lfloor\log n\rfloor$ iteration loop (lines 5–7). Algorithm 4 computes a representation of $p^\#$ in ${{\unicode{x0141}}_\infty}$ -MODSAT. It returns $\langle{\mathbf{0},\emptyset}\rangle$ in the limit case $a_0=\cdots=a_n=0$ (lines 1–3); otherwise it returns representation $\langle{\varphi_p,\Phi_p}\rangle$ given in (15). From lines 4 to 15, the algorithm sets all P, N, $\alpha_j$ , $\beta_j$ and $\beta$ , for $j=0,\ldots,n$ , which are used to rewrite function p in terms of $p_P$ and $p_N$ . From lines 16 to 26, it writes formulas $\varphi_P$ and $\varphi_N$ and adds formulas in $\Phi_P$ and $\Phi_N$ to $\Phi_p$ . For $J\in\{P,N\}$ , it works throughout a $|J|$ iteration loop where each iteration takes a coefficient $\frac{a_j}{b_j}$ into account, where it treats $\frac{a_0}{b_0}$ (lines 4–15) separately from the others (lines 22–25). In lines 27 and 28, it finally writes formula $\varphi_p$ and completes set $\Phi_p$ .

We call REPRESENT-TL-F and REPRESENT-TL-S the routines that separately compute $\varphi_p$ and $\Phi_p$ , respectively. Both may be easily derived from routine REPRESENT-TL in Algorithm 4.

5.3 The general case

We can finally tackle the general case by means of a lattice representation. Let $f:[0,1]^n\to [0,1]$ be a rational McNaughton function in regional format with linear pieces:

(16) \begin{align}p_i(\mathbf{x})= \frac{a_{i0}}{b_{i0}} + \frac{a_{i1}}{b_{i1}}x_1 + \cdots + \frac{a_{in}}{b_{in}}x_n,\end{align}

for $\mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in [0,1]^n$ , $a_{ij}\in\mathbb{Z}$ , $b_{ij}\in\mathbb{Z}^*_+$ and $i=1,\ldots,m$ , with each piece identical to f in region $\Omega_i$ , for $i=1,\ldots,m$ . We call ABOVE( $p_k$ , $p_i$ ) the polynomial time routine that decides if linear piece $p_k$ is above a different linear piece $p_i$ over $\Omega_i$ .

Algorithm 2

BINARY-F: computes formula $\xi_{n\psi}$ in (13) or $\mathbf{0}$ or $\psi$

Algorithm 3

BINARY-S: computes set $\Xi_{n\psi}$ in (14) or $\emptyset$

Algorithm 4

REPRESENT-TL: computing representations for truncated linear functions

Let $\langle{\varphi_{p_i},\Phi_{p_i}}\rangle$ be the representation for $p_i^\#$ given by Theorem 10, for $i=1,\ldots,m$ . We define

(17) \begin{align}\varphi &= \bigvee_{i=1}^m \varphi_{\Omega_i}, \text{ with } \varphi_{\Omega_i} = \bigwedge_{k\in K_{\Omega_i}} \varphi_{p_k}; \Phi = \bigcup_{i=1}^m \Phi_{p_i};\end{align}

where $k\in K_{\Omega_i}$ iff $p_k$ is above $p_i$ over $\Omega_i$ .

Table 3 shows how function f in Example 4 can be represented as in Theorem 13.

Table 3.

Representation as in (17) for function f from Example 4

Algorithm 5

REPRESENT: computing representations for rational McNaughton functions

Algorithm 5 returns representation $\langle{\varphi,\Phi}\rangle$ for function f with linear pieces given in (16). From lines 1 to 13, the algorithm writes formulas $\varphi_{\Omega_i}$ and the set $\Phi$ : it first computes formulas $\varphi_{p_i}$ (lines 2–5) by means of routine REPRESENT-TL-F and then it writes $\varphi_{\Omega_i}$ (lines 7–13) by means of routine ABOVE. It writes set $\Phi$ computing each $\Phi_{p_i}$ by means of routine REPRESENT-TL-S (line 12). In line 14, it writes formula $\varphi$ .

5.4 Pre-regional format and a literature review

The algorithm presented for building representations in ${{\unicode{x0141}}_\infty}$ -MODSAT comprehends two distinguished steps, the representation of the truncated version of linear pieces and the representation of the entire rational McNaughton function by means of a lattice representation. The second step is based on Lemma 12 and Theorem 13, where the encoding of the input function in regional format is required to comply with the lattice property. In the following, we discuss the necessity of such property for the correctness of the construction.

We say that a rational McNaughton function is in pre-regional format if it satisfies the first three items of the definition of regional format in Section 5.1, but it does not necessarily satisfy the lattice property; thus, functions in regional format are also in pre-regional format; however, the converse is not necessarily true. The following example shows that the encoding of a rational McNaughton function in pre-regional format is not enough to assure that an actual representation in ${{\unicode{x0141}}_\infty}$ -MODSAT is built by the algorithm proposed in the previous section.

Example 5. Rational McNaughton function $f_{CE}$ with graph in Figure 3a may be given in pre-regional format by the linear pieces $p_1(x_1,x_2) = p_4(x_1,x_2) = x_2$ , $p_2(x_1,x_2) = 1 - x_1$ , $p_3(x_1,x_2) = x_1$ and $p_5(x_1,x_2) = \frac{1}{4} + \frac{1}{2}x_2$ . Regions $\Omega_i$ associated to each linear piece are depicted in Figure 3b and described in Table 4. The intersection of hyperplane given by $p_5$ with the hyperplanes given by $p_2$ and $p_3$ are depicted by the dotted lines in Figure 3b.

Figure 3.

Graph and region configuration of function $f_{CE}$ in Example 5.

Table 4.

Regions $\Omega_i$ for function f in Example 5

Note that such encoding of $f_{CE}$ does not have the lattice property since there is no linear piece $p_k$ such that $p_3$ is above $p_k$ over $\Omega_3$ and $p_k$ is above $p_5$ in $\Omega_5$ . Let $\langle{\varphi,\Phi}\rangle$ be a pair as in (17), intending to represent $f_{CE}$ , and let $\mathbf{x}_0 = \langle{0.6,0.9}\rangle\in\Omega_3^\circ$ ; we have $K_{\Omega_3} = \{1,3\}$ and $K_{\Omega_5} = \{5\}$ and, then, for $v\in\mathbf{Val}_\Phi$ such that $\mathbf{x}_0=\langle{v(X_1),v(X_2)}\rangle$ , we have $f_{CE}(\mathbf{x}_0) = p_3(\mathbf{x}_0) = 0.6 < 0.7 = v(\varphi_{\Omega_5}) \leq v(\varphi)$ . Therefore, $\langle{\varphi,\Phi}\rangle$ cannot be a representation for function $f_{CE}$ and the lattice property cannot be dropped from regional format in order to perform such representation.

Function $f_{CE}$ may be put in regional format by taking as regions the polyhedra $P_\rho\in\mathcal{C}$ in (7); in this case, we have a representation with $|\mathcal{C}| = 9$ regions. On the other hand, it may be put in regional format from the encoding above by only splitting region $\Omega_5$ in two regions $\Omega'_5 = \Omega_5\cap\{ p_i \geq 0 \}$ and $\Omega''_5 = \Omega_5\cap\{ p_i \leq 0 \}$ , for some $i\in\{ 2,3 \}$ , adding only one more region to the encoding.

The results in Tarela et al. (Reference Tarela, Alonso and Martínez1990), Theorem 7, Tarela and Martínez (Reference Tarela and Martínez1999), Theorem 4.2 and, more recently, in Xu and Wang (Reference Xu and Wang2019), Theorem 1 propose a lattice representation of piecewise linear functions analogous to the one we derived in Lemma 12 and Theorem 13, where $\varphi$ is a $(\bigvee\bigwedge)$ -combination of formulas $\varphi_{p_k}$ ; they are presented in a more general context of piecewise linear functions over more general domains and codomains and do not refer to a specific formal language. However, those results do not require that the configuration of regions and linear pieces in the function description have the lattice property; thus, rational McNaughton functions only in pre-regional format would be enough for applying such results in our context. Unfortunately, despite being a less restrictive hypothesis, it is not actually suitable for our kind of representation, as Example 3 demonstrates. Nevertheless, this less restrictive approach is suitable for one-variable piecewise linear functions in pre-regional format due to the fact that functions in such encoding already have the lattice property.

6.1 Classes of rational McNaughton functions and experiments

Following, we describe the classes of functions we used in each battery of experiments and the specifications according to which random functions in these classes were generated. Before that, we state a result on continuous piecewise linear functions which we assume in the constructions in the latter classes.

Theorem 16. Let $f:\mathbb{R}^n\to\mathbb{R}$ be a continuous piecewise linear function identical to $p_1:\mathbb{R}^n\to\mathbb{R}$ and $p_2:\mathbb{R}^n\to\mathbb{R}$ over $R_1\subset\mathbb{R}^n$ and $R_2\subset\mathbb{R}^n$ , respectively. If $p_1$ and $p_2$ have rational coefficients and

\begin{equation*} R_1\cap R_2 = \Big\{ \langle{x_1,\ldots,x_n}\rangle\in\mathbb{R}^n ~\Big|~ x_{j_0}=\xi, ~ \alpha_j \leq x_j \leq \beta_j, ~ \textrm{for $j=1,\ldots,j_0-1,j_0+1,\ldots,n$} \Big\}, \end{equation*}

for $\xi,\alpha_j,\beta_j\in\mathbb{Q}$ , with $\xi\neq 0$ and $\alpha_j<\beta_j$ , for $j=1,\ldots,j_0-1,j_0+1,\ldots,n$ , then, there is $q\in\mathbb{Q}$ , such that $p_1(\mathbf{x}) - p_2(\mathbf{x}) = q\cdot\left( x_{j_0}-\xi \right)$ , for $\mathbf{x}\in\mathbb{R}^n$ .

Truncated linear functions. A function $p^\#:[0,1]^n\to [0,1]$ in this class is a truncated linear function in (9) defined from a linear function p in (8). Function $p^\#$ has range in [0,1] and is continuous over $[0,1]^n$ .

In the experiments, for each dimension $n=1,\ldots,50$ , one hundred functions $p^\#$ were generated from functions p for which, for each coefficient $\frac{a_j}{b_j}$ , $a_j$ was randomly chosen among integers from $-100$ to 100 and $b_j$ was randomly chosen among integers from 1 to 100. The execution time for building the representations in ${{\unicode{x0141}}_\infty}$ -MODSAT was up to $0.03$ second. In Figure 4a, we see the results of the representation builder running on truncated linear functions.

Figure 4.

Representation builder performance, randomly gen. instances: $n=1$ to $n=50$ .

Normalized linear functions. A function $p':[0,1]^n\to[0,1]$ in this class is defined from a linear function p in (8) by the following normalization process performed over $D=[0,1]^n$ by

(18) \begin{align}p'(\mathbf{x}) = \frac{p(\mathbf{x})+\frac{A}{b_0}}{B},\end{align}

for $\mathbf{x}\in [0,1]^n$ , where A is the least positive integer such that $\frac{A}{b_0}\geq|\min_{\mathbf{x}\in D}p(\mathbf{x})|$ , if $\min_{\mathbf{x}\in D}p(\mathbf{x})<0$ , and $A = 0$ , otherwise; and B is the least integer greater than or equal to $\max_{\mathbf{x}\in D} p(\mathbf{x})+\frac{A}{b_0}$ , if $\max_{\mathbf{x}\in D}p(\mathbf{x})+\frac{A}{b_0}>1$ , and $B=1$ , otherwise. Function p’ has range in [0,1] and is continuous over $[0,1]^n$ .

In the experiments, for each dimension $n=1,\ldots,50$ , one hundred functions p’ were generated from functions p for which, for each coefficient $\frac{a_j}{b_j}$ , $a_j$ was randomly chosen among integers from $-100$ to 100 and $b_j$ was randomly chosen among integers from 1 to 100. The execution time for building the representations in ${{\unicode{x0141}}_\infty}$ -MODSAT was up to $0.04$ second. In Figure 4b, we see the results of the representation builder running on normalized linear functions.

Simple-region piecewise linear functions. A function $f:[0,1]^n\to [0,1]$ in this class is defined to be identical to linear pieces $p_i$ over (simple-)regions

\begin{equation*} \Omega_i = \Big\{ \mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in[0,1]^n ~\Big|~ \frac{i-1}{r} \leq x_1 \leq \frac{i}{r}, ~ 0 \leq x_j \leq 1, ~ \textrm{for $j=2,\ldots,n$} \Big\}, \end{equation*}

for $i=1,\ldots,r$ . Figure 5a depicts a simple-region configuration with four regions for $n=3$ and $r=4$ .

Figure 5.

Simple-region and cubic-region configurations in dimension $n=3$ .

Linear piece $p_1$ is defined by p’ from a linear function p in (8) by the normalization process in (18) performed over $D=\Omega_1$ .

The other linear pieces $p_i$ , for $i=2,\ldots,r$ , are defined by

\begin{equation*} p_i(\mathbf{x}) = p_{i-1}(\mathbf{x}) + q_i\cdot\left(x_1-\frac{i-1}{r}\right), \end{equation*}

with $q_i\in[{-}m_i\cdot r,(1-M_i)\cdot r]$ , for

\begin{equation*} m_i=\min_{\substack{\mathbf{x}\in\Omega_i \\ \textrm{s.t. } x_1=\frac{i}{r}}} p_{i-1}(\mathbf{x}) \textrm{and} M_i=\max_{\substack{\mathbf{x}\in\Omega_i \\ \textrm{s.t. } x_1=\frac{i}{r}}} p_{i-1}(\mathbf{x}). \end{equation*}

These linear pieces and, therefore, function f have range in [0,1]; also, function f is continuous over $[0,1]^n$ . Theorem 6 below states that such encoding of function f has the lattice property.

In the experiments, for each dimension $n=1,\ldots,50$ and each number of regions $r=1,\ldots,20$ , one function f was generated with linear piece $p_1$ defined from a function p for which, for each coefficient $\frac{a_j}{b_j}$ , $a_j$ was randomly chosen among integers from $-100$ to 100 and $b_j$ was randomly chosen among integers from 1 to 100; and with linear pieces $p_i$ defined from linear pieces $p_{i-1}$ and values $q_i$ uniformly chosen over the intervals $[{-}m_i\cdot r,(1-M_i)\cdot r]$ , for $i=2,\ldots,r$ . The execution time for building the representations in ${{\unicode{x0141}}_\infty}$ -MODSAT was up to 1 second. In Figure 6, we see the results of the representation builder running on simple-region piecewise linear functions with dimensions $n=25$ and $n=50$ .

Figure 6.

Representation builder performance running on simple-region piecewise linear functions, randomly gen. instances: $r=1$ to $r=20$ .

Cubic-region piecewise linear functions. A function $f':[0,1]^n\to [0,1]$ in this class is defined from a function $f:[0,1]^n\to\mathbb{R}$ by the following normalization process performed by

\begin{equation*} f'(\mathbf{x}) = \frac{f(\mathbf{x})+\gamma}{\Gamma}, \end{equation*}

for $\mathbf{x}\in [0,1]^n$ , where $\gamma=|\min_{\mathbf{x}\in [0,1]^n}f(\mathbf{x})|$ , if $\min_{\mathbf{x}\in [0,1]^n}f(\mathbf{x})<0$ , and $\gamma = 0$ , otherwise; and $\Gamma$ is the least integer greater than or equal to $\max_{\mathbf{x}\in [0,1]^n} f(\mathbf{x})+\gamma$ , if $\max_{\mathbf{x}\in [0,1]^n}f(\mathbf{x})+\gamma>1$ , and $\Gamma=1$ , otherwise. Function f’ has range in [0,1].

Function $f:[0,1]^n\to\mathbb{R}$ is defined to be identical to linear pieces $p_{\langle{i_1,\ldots, i_n}\rangle}$ over (cubic-)regions

\begin{equation*} \Omega_{\langle{i_1,\ldots,i_n}\rangle} = \Big\{ \mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in[0,1]^n ~\Big|~ \frac{i_j-1}{r} \leq x_j \leq \frac{i_j}{r}, ~ \textrm{for $j=1,\ldots,n$} \Big\}, \end{equation*}

for $i_j=1,\ldots,r$ , for $j=1,\ldots,n$ . Figure 5b depicts a cubic-region configuration with eight regions for $n=3$ and $r=2$ .

Linear piece $p_{\langle{1,\ldots,1}\rangle}$ is defined by p’ from a linear function p in (8) by the normalization process in (18) performed over $D=\Omega_{\langle{1,\ldots,1}\rangle}$ .

The linear pieces $p_{\langle{i_1,\ldots,i_n}\rangle}$ , for which $i_1=\cdots=i_{j-1}=i_{j+1}=\cdots=i_n=1$ and $i_j\neq 1$ , are defined by

(19) \begin{align} p_{\langle{i_1,\ldots,i_n}\rangle}(\mathbf{x}) = p_{\langle{i_1,\ldots, i_{j-1},i_j-1,i_{j+1},\ldots,i_n}\rangle}(\mathbf{x}) + q_j^{i_j}\cdot\left(x_j-\frac{i_j-1}{r}\right),\end{align}

with $q_j^{i_j}\in[{-}m_{\langle{i_1,\ldots,i_n}\rangle}\cdot r,(1-M_{\langle{i_1,\ldots,i_n}\rangle})\cdot r]$ , for

\begin{equation*} m_{\langle{i_1,\ldots,i_n}\rangle}=\min_{\mathbf{x}\in\Omega} p_{\langle{i_1,\ldots,i_{j-1},i_j-1,i_{j+1},\ldots, i_n}\rangle}(\mathbf{x}) \textrm{and} M_{\langle{i_1,\ldots,i_n}\rangle}=\max_{\mathbf{x}\in\Omega} p_{\langle{i_1,\ldots,i_{j-1},i_j-1,i_{j+1},\ldots, i_n}\rangle}(\mathbf{x}), \end{equation*}

where

\begin{equation*} \Omega = \Big\{ \mathbf{x}=\langle{x_1,\ldots,x_n}\rangle\in\Omega_{\langle{i_1,\ldots,i_n}\rangle} ~\Big|~ x_j = \frac{i_j}{r} \Big\}. \end{equation*}

These linear pieces already have range in [0,1] and function f is continuous over $\Omega_{\langle{i_1,\ldots,i_n}\rangle}\cap\Omega_{\langle{i_1,\ldots,i_{j-1},i_j-1,i_{j+1},\ldots,i_n}\rangle}$ .

The other linear pieces $p_{\langle{i_1,\ldots,i_n}\rangle}$ , for which $i_1=\cdots= i_{j-1}=i_{j+1}=\cdots=i_{k-1}=1$ and $i_j\neq 1\neq i_k$ , are also defined by (19) with the same $q_j^{i_j}$ . These linear pieces are not guaranteed to have range in [0,1]; however, function f is continuous over $\Omega_{\langle{i_1,\ldots,i_n}\rangle}\cap\Omega_{\langle{i_1,\ldots,i_{j-1},i_j-1,i_{j+1},\ldots,i_n}\rangle}$ . It is also continuous over $\Omega_{\langle{i_1,\ldots,i_n}\rangle}\cap\Omega_{\langle{i_1,\ldots,i_{l-1},i_l-1,i_{l+1},\ldots,i_n}\rangle}$ , for $l\geq k$ ; indeed, there is a value q such that

\begin{align*} p_{\langle{i_1,\ldots,i_n}\rangle}(\mathbf{x}) = p_{\langle{i_1,\ldots, i_{j-1},i_j-1,i_{j+1},\ldots,i_{l-1},i_l-1,i_{l+1},\ldots,i_n}\rangle}(\mathbf{x}) + q \cdot \left( x_l - \frac{i_l-1}{r} \right) + q_j^{i_j} \cdot \left( x_j - \frac{i_j-1}{r} \right)\end{align*}

and we are able to write

\begin{align*} p_{\langle{i_1,\ldots,i_n}\rangle}(\mathbf{x}) = p_{\langle{i_1,\ldots,i_{l-1},i_l-1,i_{l+1},\ldots,i_n}\rangle}(\mathbf{x}) + q \cdot \left( x_l - \frac{i_l-1}{r} \right).\end{align*}

Thus, functions f and f’ are continuous over $[0,1]^n$ . Theorem 17 below states that such encoding of function f’ has the lattice property.

In the experiments, for each dimension $n=1,\ldots,9$ and each regional parameter $r=1,\ldots,7-(n-1)$ , if $n\leq 5$ , and $r=1,2$ , otherwise, thirty functions f’ were generated from functions f with linear piece $p_{\langle{1,\ldots,1}\rangle}$ defined from a function p for which, for each coefficient $\frac{a_j}{b_j}$ , $a_j$ was randomly chosen among integers from $-30$ to 30 and $b_j$ was randomly chosen among integers from 1 to 30; and with linear pieces $p_{\langle{i_1,\ldots,i_n}\rangle}$ , for which $i_1=\cdots=i_{j-1}=i_{j+1}=\cdots=i_n=1$ and only $i_j\neq 1$ , defined from linear pieces $p_{\langle{i_1,\ldots, i_{j-1},i_j-1,i_{j+1},\ldots,i_n}\rangle}$ and values $q_{\langle{i_1,\ldots,i_n}\rangle}$ uniformly chosen over the intervals $[{-}m_{\langle{i_1,\ldots,i_n}\rangle}\cdot r,(1-M_{\langle{i_1,\ldots, i_n}\rangle})\cdot r]$ . In Table 6, we see the results of the representation builder running on cubic-region piecewise linear functions.

Table 6.

Representation builder performance running on cubic-region piecewise linear functions

Proof. Let $\Omega_i$ and $\Omega_j$ be simple regions of a simple-region piecewise linear function f. Fixing $x_2 = \xi_2\in [0,1], \ldots, x_n = \xi_n\in [0,1]$ , we define the restriction of f to $g:[0,1]\to [0,1]$ given by $g(x_1) = f(x_1,\xi_2,\ldots,\xi_n)$ , which is a piecewise liner function with the lattice property by Theorem 15. Since, by Theorem 16, linear pieces of simple-region piecewise linear functions intercept each other over domain points in some set $\{ \mathbf{x}\in [0,1]^n ~|~ x_1 = K\in\mathbb{R} \}$ , f also has the lattice property. Now, let $\Omega_{\langle{i_1,\ldots,i_n}\rangle}$ and $\Omega_{\langle{I_1,\ldots,I_n}\rangle}$ be cubic-regions of a cubic-region piecewise linear function f’; since the normalization process from f to f’ does not interfere with the lattice property, we only need to show that f has the lattice property. Analogous to the previous argument for simple-regions, for $j=1,\ldots,n$ , there is $k_j$ , for which $\min\{ i_j,I_j \} \leq k_j \leq \max\{ i_j,I_j \}$ , such that $p_{\langle{i_1,\ldots,i_n}\rangle}(\mathbf{x}) \geq p_{\langle{i_1,\ldots,i_{j-1},k_j,i_{j+1},\ldots,i_n}\rangle}(\mathbf{x})$ , for $\mathbf{x}\in\Omega_{\langle{i_1,\ldots,i_n}\rangle}$ , and $p_{\langle{i_1,\ldots,i_{j-1},k_j,i_{j+1},\ldots,i_n}\rangle}(\mathbf{x}) \geq p_{\langle{i_1,\ldots,i_{j-1},I_j,i_{j+1},\ldots,i_n}\rangle}(\mathbf{x})$ , for $\mathbf{x} \in \Omega_{\langle{i_1,\ldots,i_{j-1},I_j,i_{j+1},\ldots,i_n}\rangle}$ . Then, from the general formula for linear pieces

\begin{equation*} p_{\langle{i_1\ldots,i_n}\rangle}(\mathbf{x}) = p_{\langle{1,\ldots,1}\rangle}(\mathbf{x}) + \sum_{j=1}^n \sum_{\iota=2}^{i_j} q_j^\iota \left( x_j - \frac{\iota-1}{r} \right), \end{equation*}

it follows that $p_{\langle{i_1,\ldots,i_n}\rangle}(\mathbf{x}) \geq p_{\langle{k_1,\ldots,k_n}\rangle}(\mathbf{x})$ , for $\mathbf{x}\in\Omega_{\langle{i_1,\ldots,i_n}\rangle}$ , and $p_{\langle{k_1,\ldots,k_n}\rangle}(\mathbf{x}) \geq p_{\langle{I_1,\ldots,I_n}\rangle}(\mathbf{x})$ , for $\mathbf{x} \in \Omega_{\langle{I_1,\ldots,I_n}\rangle}$ . Therefore, f has the lattice property.