# Relaxations of associativity and preassociativity for variadic functions

Miguel Couceiro, Jean-Luc Marichal, Bruno Teheux

► To cite this version:

Miguel Couceiro, Jean-Luc Marichal, Bruno Teheux. Relaxations of associativity and preassociativity for variadic functions. Fuzzy Sets and Systems, 2016, 229, pp.89-97. 10.1016/j.fss.2015.11.003. hal-01184334

HAL Id: hal-01184334

https://hal.science/hal-01184334

Submitted on 14 Aug 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
RELAXATIONS OF ASSOCIATIVITY AND PREASSOCIATIVITY
FOR VARIADIC FUNCTIONS

MIGUEL COUCEIRO, JEAN-LUC MARICHAL, AND BRUNO TEHEUX

ABSTRACT. In this paper we consider two properties of variadic functions, namely associativity and preassociativity, that are pertaining to several data and language processing tasks. We propose parameterized relaxations of these properties and provide their descriptions in terms of factorization results. We also give an example where these parameterized notions give rise to natural hierarchies of functions and indicate their potential use in measuring the degrees of associativeness and preassociativeness. We illustrate these results by several examples and constructions and discuss some open problems that lead to further directions of research.

# 1. INTRODUCTION

Let $X$ be an arbitrary nonempty set, called the *alphabet*, and its elements are called *letters*. The symbol $X^*$ stands for the set $\bigcup_{n \ge 0} X^n$ of all tuples on $X$, and its elements are called *strings*, where the empty string $\varepsilon$ is such that $X^0 = \{\varepsilon\}$. We denote the elements of $X^*$ by bold roman letters $\mathbf{x}$, $\mathbf{y}$, $\mathbf{z}$, ... If we want to stress that such an element is a letter of $X$, we use non-bold italic letters $x$, $y$, $z$, ... We assume that $X^*$ is endowed with the concatenation operation (the empty string $\varepsilon$ being the neutral element) for which we adopt the juxtaposition notation. For instance, if $\mathbf{x} \in X^m$ and $y \in X$, then $\mathbf{x}y\varepsilon = \mathbf{x}y \in X^{m+1}$. For every string $\mathbf{x}$ and every integer $n \ge 0$, the power $\mathbf{x}^n$ stands for the string obtained by concatenating $n$ copies of $\mathbf{x}$. In particular, we have $\mathbf{x}^0 = \varepsilon$. The *length* of a string $\mathbf{x}$ is denoted by $|\mathbf{x}|$. In particular, we have $|\varepsilon| = 0$.

Let $Y$ be a nonempty set. Recall that a function $F: X^* \to Y$ is said to be *variadic* and that, for every integer $n \ge 0$, a function $F: X^n \to Y$ is said to be *n-ary*. A unary operation on $X^*$ is a particular variadic function $F: X^* \to X^*$ called a *string function* over the alphabet $X$.

**Definition 1.1.** A function $F: X^* \to X^*$ is said to be *associative* [3] if for any $\mathbf{x}, \mathbf{y}, \mathbf{z} \in X^*$, we have

$$ (1) \qquad F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z}). $$

A function $F: X^* \to Y$ is said to be *preassociative* [5, 6] if for any $\mathbf{x}, \mathbf{y}, \mathbf{y}', \mathbf{z} \in X^*$, we have

$$ (2) \qquad F(\mathbf{y}) = F(\mathbf{y}') \quad \Rightarrow \quad F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}\mathbf{y}'\mathbf{z}). $$

<footnote>Date: August 4, 2015.</footnote>

<footnote n="2010">2010 Mathematics Subject Classification. 20M05, 20M32, 39B72, 68R99.</footnote>

<footnote>Key words and phrases. Associativity, Preassociativity, Variadic function, String function, Functional equation, Axiomatization.</footnote>
Associative string functions and preassociative variadic functions as well as some of their variants have been studied in [3–8]. For instance, it has been shown [3] that a function $F: X^* \to X^*$ is associative if and only if it is preassociative and satisfies the condition $F = F \circ F$. Also, under the Axiom of Choice, a function $F: X^* \to Y$ is preassociative if and only if it can be written as a composition of the form $F = f \circ H$, where $H: X^* \to X^*$ is associative and $f: \mathrm{ran}(H) \to Y$ is one-to-one.

It is noteworthy that several data processing tasks correspond to associative and preassociative functions. For instance, the function which corresponds to sorting the letters of every string in alphabetical order is associative. Similarly, the function that transforms a string of letters into upper case is also associative. Another natural example of a preassociative function is the mapping that outputs the length of strings.

In this paper we introduce and study certain relaxations of associativity and preassociativity. Let $\mathcal{A}$ denote the class of associative string functions on $X^*$ and let $\mathcal{P}$ denote the class of preassociative variadic functions on $X^*$. For a fixed nonempty subset $D$ of $X^*$, define the following classes of functions:

$$ \mathcal{A}_D = \{F: X^* \to \mathrm{ran}(F) \mid F(D) \subseteq X^* \text{ and (1) holds for all } \mathbf{x}, \mathbf{y}, \mathbf{z} \in X^* \text{ such that } \mathbf{y} \in D\}, $$

$$ \mathcal{A}'_D = \{F: X^* \to \mathrm{ran}(F) \mid F(D) \subseteq X^* \text{ and (1) holds for all } \mathbf{x}, \mathbf{y}, \mathbf{z} \in X^* \text{ such that } F(\mathbf{y}) \in F(D)\}, $$

$$ \mathcal{P}_D = \{F: X^* \to \mathrm{ran}(F) \mid (2) \text{ holds for all } \mathbf{x}, \mathbf{y}, \mathbf{y}', \mathbf{z} \in X^* \text{ such that } \mathbf{y}, \mathbf{y}' \in D\}, $$

$$ \mathcal{P}'_D = \{F: X^* \to \mathrm{ran}(F) \mid (2) \text{ holds for all } \mathbf{x}, \mathbf{y}, \mathbf{y}', \mathbf{z} \in X^* \text{ such that } \mathbf{y} \in D\}. $$

It is clear that $\mathcal{A}_{X^*} = \mathcal{A}'_{X^*} = \mathcal{A}$ and $\mathcal{P}_{X^*} = \mathcal{P}'_{X^*} = \mathcal{P}$. When $D \not\subseteq X^*$, these classes of functions correspond to relaxations of associativity and preassociativity for which we have $\mathcal{A}'_D \subseteq \mathcal{A}_D$ and $\mathcal{P}'_D \subseteq \mathcal{P}_D$. For instance, functions $F: X^* \to X^*$ that are in $\mathcal{A}'_D$ are characterized by the fact that for any $\mathbf{x}, \mathbf{y}, \mathbf{z} \in X^*$ the value $F(\mathbf{x}\mathbf{y}\mathbf{z})$ can be replaced with $F(\mathbf{x}F(\mathbf{y})\mathbf{z})$ whenever $F(\mathbf{y}) = F(\mathbf{y}')$ for some $\mathbf{y}' \in D$.

Certain of these relaxations are particularly natural. For instance, consider the subset

$$ D = \{x^n \mid x \in X, n \in \mathbb{N}\}, $$

where $\mathbb{N}$ denotes the set of nonnegative integers. Any function $F: X^* \to X^*$ in $\mathcal{A}_D$ has the property that the value $F(\mathbf{x}\mathbf{y}\mathbf{z})$ can be replaced with $F(\mathbf{x}F(\mathbf{y})\mathbf{z})$ whenever $\mathbf{y}$ is a repeated letter. Further examples include:

* $D = \{\mathbf{x} \in X^* \mid |\mathbf{x}| \le m\}$ for some integer $m \ge 0$,

* $D = \{\mathbf{x} \in X^* \mid |\mathbf{x}| \ge m\}$ for some integer $m \ge 0$,

* $D = X^*\mathbf{w}X^* = \{\mathbf{x}\mathbf{w}\mathbf{x}' \mid \mathbf{x}, \mathbf{x}' \in X^*\}$ for a given $\mathbf{w} \in X^*$,

* $D = \{x \in \mathbb{R} \mid x \le s\}$ for some threshold $s \in \mathbb{R}$ (observe that $D \not\subseteq \mathbb{R} \not\subseteq \mathbb{R}^*$).

The function classes defined above can be motivated by indexation techniques in natural language processing (NLP) as they include noteworthy examples such as the Soundex encoding and its variants (see, e.g., [1, 2]).

**Example 1.2.** Let $X = \{a, b, \dots, z\}$, let $\mathbf{w} \in X^*$, and let $D = X^*\mathbf{w}X^*$. Consider also $F: X^* \to X^*$ defined by $F(\mathbf{x}) = \mathbf{w}$ if $\mathbf{x} \in X^*\mathbf{w}X^*$, and $F(\mathbf{x}) = \varepsilon$, otherwise. It is easy to see that $F$ is in $\mathcal{A}'_D$. However, it is not in $\mathcal{A}$ unless $|\mathbf{w}| \le 1$. For example, if $\mathbf{w} = ab$, then $F(ab) = ab \ne \varepsilon = F(F(a)b)$.
**Fact 1.3.** For any nonempty subsets $D_1$ and $D_2$ of $X^*$ such that $D_1 \subseteq D_2$, the following inclusions hold:

$$ \begin{aligned} A_{D_2} &\subseteq A_{D_1}, & A'_{D_2} &\subseteq A'_{D_1}, \\ P_{D_2} &\subseteq P_{D_1}, & P'_{D_2} &\subseteq P'_{D_1}. \end{aligned} $$

**Problem 1.4.** Give necessary and sufficient conditions on $D$ for the inclusions $A'_D \subseteq A_D$ and $P'_D \subseteq P_D$ to be strict, and similarly for the inclusions in Fact 1.3.

The outline of this paper is as follows. In Section 2 we focus on the special case when $D$ is the set of the strings over $X$ whose lengths are bounded above by a fixed integer $m \ge 0$. We describe a couple of examples (Examples 2.1, 2.3, 2.4), which show that in this case the inclusions given in Fact 1.3 are strict, thus giving rise to hierarchies of nested classes of functions. In Section 3 we present several factorization results. In particular, we identify associative functions within the class of preassociative functions, and extend these results to classes of ‘range-determined’ functions in Section 4. The potential use of hierarchies in measuring associativeness and preassociativeness is then illustrated in Section 5, together with some open problems that constitute topics of current research. Other noteworthy questions are mentioned throughout the paper.

We use the following notation. The set $\{0, 1, 2, \dots\}$ of nonnegative integers is denoted by $\mathbb{N}$. The domain and range of any function $f$ are denoted by $\text{dom}(f)$ and $\text{ran}(f)$, respectively. The identity function on any nonempty set $E$ is denoted by $\text{id}_E$. For any function $F: X^* \to Y$ and any integer $n \ge 0$, we denote by $F_n$ the $n$-ary part of $F$, i.e., the restriction $F|_{X^n}$ of $F$ to the set $X^n$.

Recall that a function $g$ is a quasi-inverse [9, Sect. 2.1] of a function $f$ if

$$ f \circ g|_{\text{ran}(f)} = \text{id}_{\text{ran}(f)} \quad \text{and} \quad \text{ran}(g|_{\text{ran}(f)}) = \text{ran}(g). $$

In this case we have $\text{ran}(g) \subseteq \text{dom}(f)$ and the function $g|_{\text{ran}(f)}$ is one-to-one. Denote the set of quasi-inverses of a function $f$ by $Q(f)$. Under the Axiom of Choice (AC), the set $Q(f)$ is nonempty for any function $f$. In fact, AC is just another form of the statement “every function has a quasi-inverse”. Note also that the relation of being quasi-inverse is symmetric: if $g \in Q(f)$ then $f \in Q(g)$.

## 2. THE CASE OF BOUNDED STRINGS

In this section we consider the special case when the set $D$ consists of strings whose lengths are bounded above by a given integer $m \ge 0$. Denote this set by $D_m$, i.e.,

$$ D_m = \{ \mathbf{x} \in X^* \mid |\mathbf{x}| \le m \}. $$

From Fact 1.3 we immediately derive the inclusions

$$ \begin{aligned} A_{D_{m+1}} &\subseteq A_{D_m}, & A'_{D_{m+1}} &\subseteq A'_{D_m} \subseteq A_{D_m}, \\ P_{D_{m+1}} &\subseteq P_{D_m}, & P'_{D_{m+1}} &\subseteq P'_{D_m} \subseteq P_{D_m}, \end{aligned} $$

as well as the equalities

$$ A = \bigcap_{m \ge 0} A'_{D_m} = \bigcap_{m \ge 0} A_{D_m} \quad \text{and} \quad P = \bigcap_{m \ge 0} P'_{D_m} = \bigcap_{m \ge 0} P_{D_m}. $$

We now prove that each of these inclusions is actually strict, thus showing that these classes give rise to hierarchies of supersets of associative and preassociative functions.
Let $m \ge 0$ be an integer. We observe that any function $F: X^* \to X^*$ such that $F_k = \text{id}_{X^k}$ for $k = 0, \dots, m$ is necessarily in $\mathcal{A}_{D_m}$. However, the converse does not hold. For instance, the function $F: N^* \to N \cup \{\varepsilon\}$ defined by $F(\varepsilon) = \varepsilon$ and $F(\mathbf{x}) = |\mathbf{x}|$ for every $\mathbf{x} \in N^* \setminus \{\varepsilon\}$ is in $\mathcal{A}_{D_1}$ and its unary part $F_1 = 1$ is constant.

More generally, we also observe that any function $F: X^* \to X^*$ such that $F_k = \text{id}_{X^k}$ for $k = 0, \dots, m$ and that satisfies the condition

$$ (3) \qquad F(\mathbf{y}) \in \bigcup_{k=0}^{m} \text{ran}(F_k) \iff |\mathbf{y}| \le m $$

is in $\mathcal{A}'_{D_m}$. As a particular case, take $F_k = \text{id}_{X^k}$ for $k = 0, \dots, m$ and $|F(\mathbf{x})| > m$ for every $\mathbf{x} \in X^*$ such that $|\mathbf{x}| > m$. The following example illustrates this case and shows that $\mathcal{A}_{D_{m+1}} \not\subseteq \mathcal{A}_{D_m}$ and $\mathcal{A}'_{D_{m+1}} \not\subseteq \mathcal{A}'_{D_m}$.

**Example 2.1.** Let $m \ge 0$ be an integer and consider the string function $F: X^* \to X^*$ that transforms a string of letter into its prefix of length $m$. That is, the $k$-ary part $F_k$ of $F$ is defined by

$$ F_k(\mathbf{x}) = F_k(x_1 \cdots x_k) = \begin{cases} \mathbf{x}, & \text{if } k \le m, \\ x_1 \cdots x_m, & \text{if } k > m. \end{cases} $$

It is easy to see that this function is associative. Now, assume $X = \{a, b, \dots, z\}$ and let $\alpha: X \to \{c, v\}$ be defined by $\alpha(x) = v$, if $x$ is a vowel, and $\alpha(x) = c$, if $x$ is a consonant. Let $G: X^* \to X^*$ be the “indexing” function whose $k$-ary part $G_k$ is defined by

$$ G_k(\mathbf{x}) = \begin{cases} \mathbf{x}, & \text{if } k \le m, \\ x_1 \cdots x_m \alpha(x_{m+1}) \cdots \alpha(x_k), & \text{if } k > m. \end{cases} $$

As mentioned above, $G$ is in $\mathcal{A}'_{D_m}$ and hence in $\mathcal{A}_{D_m}$. However, it is not in $\mathcal{A}_{D_{m+1}}$ and hence not in $\mathcal{A}'_{D_{m+1}}$. Indeed, we have $G(G(a^{m+1})) \ne G(a^{m+1})$.

**Proposition 2.2.** Let $m \ge 0$ be an integer. If $F: X^* \to X^*$ is in $\mathcal{A}_{D_m}$ and satisfies (3), then $F$ is in $\mathcal{A}'_{D_m}$.

*Proof.* Let $\mathbf{x}, \mathbf{y}, \mathbf{z} \in X^*$ such that $F(\mathbf{y}) \in \bigcup_{k=0}^{m} \text{ran}(F_k)$. By (3) we must have $|\mathbf{y}| \le m$. But then (1) holds (since $F$ is in $\mathcal{A}_{D_m}$). $\square$

The following example illustrates Proposition 2.2 and provides a string function in $\mathcal{A}'_{D_m}$ that does not satisfy (3).

**Example 2.3.** Assume $X = \mathbb{L} \cup \mathbb{N}$, where $\mathbb{L} = \{a, b, \dots, z\}$ and $\mathbb{N} = \{0, 1, 2, \dots\}$. For every $\mathbf{x} \in X^*$, let $|\mathbf{x}|_{\mathbb{L}}$ be the number of letters of $\mathbf{x}$ that are in $\mathbb{L}$. Let $m \ge 0$ be an integer and consider the functions $F, G: X^* \to X^*$ defined by

$$ F(\mathbf{x}) = \begin{cases} \mathbf{x}, & \text{if } |\mathbf{x}| < m, \\ x_1 \cdots x_{m-1} |\mathbf{x}|, & \text{if } |\mathbf{x}| \ge m, \end{cases} $$

and

$$ G(\mathbf{x}) = \begin{cases} \mathbf{x}, & \text{if } |\mathbf{x}| < m, \\ x_1 \cdots x_m |\mathbf{x}|_{\mathbb{L}}, & \text{if } |\mathbf{x}| \ge m. \end{cases} $$

Clearly, $F$ satisfies (3). However, $G$ does not since $G(a^m) = G(a^{m1})$ for any $a \in \mathbb{L}$.
Let us now prove that both $F$ and $G$ are in $\mathcal{A}'_{D_m} \setminus \mathcal{A}_{D_{m+1}}$. By Proposition 2.2, to see that $F$ is in $\mathcal{A}'_{D_m}$ it suffices to show that it is in $\mathcal{A}_{D_m}$. Let $\mathbf{x}, \mathbf{y}, \mathbf{z} \in X^*$ such that $|\mathbf{y}| = m$. We then have

$$F(\mathbf{x}F(\mathbf{y})\mathbf{z}) = F(\mathbf{x}y_1\cdots y_{m-1}|\mathbf{y}|\mathbf{z}) = F(\mathbf{x}\mathbf{y}\mathbf{z}),$$

which shows that $F \in \mathcal{A}_{D_m}$. Now, $F \notin \mathcal{A}_{D_{m+1}}$ since $F(F(a^{m+1})) \neq F(a^{m+1})$ for any $a \in \mathbb{L}$. Let us show that $G \in \mathcal{A}'_{D_m}$. Let $\mathbf{x}, \mathbf{y}, \mathbf{z} \in X^*$ such that $G(\mathbf{y}) \in \bigcup_{k=0}^m \text{ran}(G_k)$. If $G(\mathbf{y}) \in \text{ran}(G_k)$ for some $k < m$, then $G(\mathbf{y}) = \mathbf{y}$ and hence Eq. (1) clearly holds. If $G(\mathbf{y}) \in \text{ran}(G_m)$, then $G(\mathbf{y}) = G(y_1\cdots y_m)$ and hence $|\mathbf{y}|_{\mathbb{L}} = |y_1\cdots y_m|_{\mathbb{L}}$. Moreover, $\mathbf{x}\mathbf{y}\mathbf{z}$ and $\mathbf{x}G(\mathbf{y})\mathbf{z}$ have the same prefix of length $m$. Therefore Eq. (1) holds. This shows that $G \in \mathcal{A}'_{D_m}$. However, we have $G \notin \mathcal{A}_{D_{m+1}}$ since $G(G(a^{m+1})) \neq G(a^{m+1})$ for any $a \in \mathbb{L}$.

One can easily show that $\mathcal{A}'_{D_0} \not\subseteq \mathcal{A}_{D_0}$. Indeed, take the function $F: X^* \to X^*$ defined by $F(\varepsilon) = F(a) = \varepsilon$ for some $a \in X$ and $F(\mathbf{x}) = \mathbf{x}$ if $\mathbf{x} \notin \{\varepsilon, a\}$. The following example shows that $\mathcal{A}'_{D_m} \not\subseteq \mathcal{A}_{D_m}$ for every integer $m \ge 1$.

**Example 2.4.** Let $m \ge 1$ be an integer and consider the function $F: X^* \to X^*$ defined by

$$F(\mathbf{x}) = \begin{cases} \mathbf{x}, & \text{if } |\mathbf{x}| \le m \text{ or } |\mathbf{x}| = m+2, \\ x_1 \cdots x_m, & \text{if } |\mathbf{x}| = m+1 \text{ or } |\mathbf{x}| > m+2. \end{cases}$$

Clearly $F$ is in $\mathcal{A}_{D_m}$. However, it is not in $\mathcal{A}'_{D_m}$ since, setting $\mathbf{y} = a^{m+1}$ and $\mathbf{z} = a$ for some $a \in X$, we have $F(\mathbf{y}) = a^m = F(a^m) \in \text{ran}(F_m)$ but $F(\mathbf{y}\mathbf{z}) = a^{m+2} \neq a^m = F(F(\mathbf{y})\mathbf{z})$.

Just as we have $\mathcal{A} \subseteq \mathcal{P}$, we also have $\mathcal{A}_{D_m} \subseteq \mathcal{P}_{D_m}$ and $\mathcal{A}'_{D_m} \subseteq \mathcal{P}'_{D_m}$ for every integer $m \ge 0$. This observation immediately follows from Propositions 3.2 and 3.3 below. Let us now show that these inclusions are strict. For $m = 0$, take $F: X^* \to X^*$ such that $F(\varepsilon) = a$ for some $a \in X$ and $F(\mathbf{x}) = \mathbf{x}$ for every $\mathbf{x} \neq \varepsilon$. Then $F$ is in $\mathcal{P}_{D_0} \setminus \mathcal{A}_{D_0}$. For $m \ge 1$, let $\sigma$ be a nontrivial permutation on $X$. The function $F: X^* \to X^*$ defined by $F(\varepsilon) = \varepsilon$ and $F(x_1\cdots x_n) = \sigma(x_1)\cdots\sigma(x_n)$ for every integer $n \ge 1$ is in $\mathcal{P} \setminus \mathcal{A}_{D_1}$. Consider for instance in Eq. (1) the strings $\mathbf{x} = \mathbf{z} = \varepsilon$ and $\mathbf{y} = \sigma^{-1}(a)$ for some $a \in X$ such that $\sigma(a) \neq a$.

Let us now show that the sets $\mathcal{P}_{D_m} \setminus \mathcal{P}_{D_{m+1}}$ and $\mathcal{P}'_{D_m} \setminus \mathcal{P}'_{D_{m+1}}$ are nonempty. Consider first the case $m = 0$. Take $X = \mathbb{R}$ and the function $F: \mathbb{R}^* \to \mathbb{R}^*$ defined by $F(\varepsilon) = \varepsilon$ and $F(x_1\cdots x_n) = \frac{1}{n}\sum_{i=1}^n x_i$ for every integer $n \ge 1$. Then $F$ is in $\mathcal{P}'_{D_0}$ (and hence in $\mathcal{P}_{D_0}$) but not in $\mathcal{P}_{D_1}$ (and hence not in $\mathcal{P}'_{D_1}$). Indeed, we have $F(0) = F(00)$ but $F(01) \neq F(001)$. For the case $m \ge 1$, take $F: X^* \to X^*$ defined as

$$F(\mathbf{x}) = \begin{cases} \mathbf{x}, & \text{if } |\mathbf{x}| \le m, \\ x_1 \cdots x_m x_{k-1}, & \text{if } |\mathbf{x}| = k > m. \end{cases}$$

Then, $F$ is in $\mathcal{P}'_{D_m}$ but not in $\mathcal{P}_{D_{m+1}}$. Indeed, if $z \neq z'$, we have

$$F(y_1 \cdots y_m z) = F(y_1 \cdots y_m z')$$

but

$$F(y_1 \cdots y_m z a) \neq F(y_1 \cdots y_m z' a).$$
### 3. CHARACTERIZATION RESULTS

In this section we aim at localizing each of the parameterized classes $\mathcal{A}_D$ introduced above within its corresponding superclass $\mathcal{P}_D$. This goal is achieved in two ways: on the one hand, under the assumption that $F(D) \subseteq D$ we show that functions in $\mathcal{A}_D$ are exactly those in $\mathcal{P}_D$ that verify the condition $F|_D = F \circ F|_D$ and, on the other hand, we also show that functions in $\mathcal{P}_D$ admit factorizations in terms of functions in $\mathcal{A}_D$. Similar results are then established for $\mathcal{A}'_D$ and $\mathcal{P}'_D$.

As observed we have $\mathcal{A} \subseteq \mathcal{P}$ and this inclusion is actually strict. In fact, we have the following result.

**Proposition 3.1** ([5,6]). A function $F: X^* \to X^*$ is in $\mathcal{A}$ if and only if it is in $\mathcal{P}$ and satisfies $F = F \circ F$.

The following two propositions provide generalizations of Proposition 3.1 to the classes $\mathcal{A}_D$, $\mathcal{A}'_D$, $\mathcal{P}_D$, and $\mathcal{P}'_D$.

**Proposition 3.2.** Let $D$ be an nonempty subset of $X^*$ and consider a function $F: X^* \to \text{ran}(F)$. If $F$ is in $\mathcal{A}_D$, then it is in $\mathcal{P}_D$ and satisfies $F|_D = F \circ F|_D$. The converse also holds whenever $F(D) \subseteq D$.

*Proof.* Suppose $F \in \mathcal{A}_D$. Clearly, we have $F|_D = F \circ F|_D$. Now, let $\mathbf{y}, \mathbf{y}' \in D$ be such that $F(\mathbf{y}) = F(\mathbf{y}')$. Then, we have

$$F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z}) = F(\mathbf{x}F(\mathbf{y}')\mathbf{z}) = F(\mathbf{x}\mathbf{y}'\mathbf{z}),$$

which shows that $F \in \mathcal{P}_D$. For the converse statement, let $\mathbf{x}, \mathbf{z} \in X^*$ and $\mathbf{y} \in D$. We then have $F(\mathbf{y}) = F(F(\mathbf{y}))$ and hence, since $F$ is in $\mathcal{P}_D$, we also have $F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z})$, which shows that $F \in \mathcal{A}_D$. $\square$

**Proposition 3.3.** Let $D$ be a nonempty subset of $X^*$ and let $F: X^* \to \text{ran}(F)$ be such that $F(D) \subseteq X^*$. Then $F$ is in $\mathcal{A}'_D$ if and only if it is in $\mathcal{P}'_D$ and satisfies $F|_D = F \circ F|_D$.

*Proof.* (Necessity) Let $\mathbf{y} \in D$ and $\mathbf{y}' \in X^*$ be such that $F(\mathbf{y}) = F(\mathbf{y}')$. Since $F \in \mathcal{A}'_D$, for every $\mathbf{x}, \mathbf{z} \in X^*$ we have

$$F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z}) = F(\mathbf{x}F(\mathbf{y}')\mathbf{z}) = F(\mathbf{x}\mathbf{y}'\mathbf{z}),$$

which shows that $F \in \mathcal{P}'_D$. Also, we clearly have $F|_D = F \circ F|_D$.

(Sufficiency) Let $\mathbf{x}, \mathbf{z} \in X^*$ and $\mathbf{y} \in D$. As $F(\mathbf{y}) = F(F(\mathbf{y}))$ and $F \in \mathcal{P}'_D$, we also have $F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z})$.

Now, let $\mathbf{y}' \in X^*$ such that $F(\mathbf{y}') = F(\mathbf{y})$. Since $F \in \mathcal{P}'_D$ we have

$$F(\mathbf{x}\mathbf{y}'\mathbf{z}) = F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}F(\mathbf{y})\mathbf{z}) = F(\mathbf{x}F(\mathbf{y}')\mathbf{z}),$$

which shows that $F \in \mathcal{A}'_D$. $\square$

Let us recall the following factorization established in [3].

**Theorem 3.4** ([3]). Assume $AC$ and let $F: X^* \to Y$ be a function. The following assertions are equivalent.

(i) $F \in \mathcal{P}$.

(ii) There exist $H \in \mathcal{A}$ and a one-to-one function $f: \text{ran}(H) \to Y$ such that $F = f \circ H$.

For any $g \in Q(F)$, we can choose $H = g \circ F$ and $f = F|_{\text{ran}(H)}$ in assertion (ii).
We will now generalize Theorem 3.4 to the classes $\mathcal{P}_D$ and $\mathcal{P}'_D$ (see Theorems 3.7 and 3.8). For this purpose, we first present a more general factorization result (see Proposition 3.6).

Let $\mathcal{C}$ be any class of functions defined on a set $\Omega$ and satisfying the following property: if $F \in \mathcal{C}$, then $g \circ F \in \mathcal{C}$ for every one-to-one map $g$ defined on $\mathrm{ran}(F)$. For any nonempty set $D \subseteq \Omega$, define also the following subclasses:

$$ \mathcal{C}'_D = \{F \in \mathcal{C} \mid F(D) \subseteq D\}, $$

$$ \mathcal{C}''_D = \{F \in \mathcal{C} \mid F(D) \subseteq D \text{ and } F \circ F|_D = F|_D\}. $$

**Example 3.5.** If $\mathcal{C}$ is the class $\mathcal{P}$ of preassociative functions on $X^*$, then $\mathcal{C}''_{X^*}$ is the class $\mathcal{A}$ of associative string functions on $X^*$ by Proposition 3.1.

We also observe that, assuming AC, for any subset $D$ of $\mathrm{dom}(f)$ the set

$$ Q_D(f) = \{g \in Q(f) \mid (g \circ f)(D) \subseteq D\} $$

is nonempty. Indeed, if $x \in D$, we can set $g(f(x)) = x$.

**Proposition 3.6.** Assume AC, let $D \subseteq \Omega$, and let $F$ be a function defined on $\Omega$. The following assertions are equivalent.

(i) $F \in \mathcal{C}$.

(ii) There exist $H \in \mathcal{C}'_D$ and a one-to-one function $f$ defined on $\mathrm{ran}(H)$ such that $F = f \circ H$.

(iii) There exist $H \in \mathcal{C}''_D$ and a one-to-one function $f$ defined on $\mathrm{ran}(H)$ such that $F = f \circ H$.

For any $g \in Q_D(F)$, we can choose $H = g \circ F$ and $f = F|_{\mathrm{ran}(H)}$ in assertions (ii) and (iii).

*Proof.* (iii) ⇒ (ii) Trivial.

(ii) ⇒ (i) Since $H \in \mathcal{C}'_D \subseteq \mathcal{C}$, we have $F \in \mathcal{C}$.

(i) ⇒ (iii) Let $g \in Q_D(F)$ and set $H = g \circ F$. Since $g|_{\mathrm{ran}(F)}$ is one-to-one, we have $H \in \mathcal{C}$. Also, we have $H(D) = (g \circ F)(D) \subseteq D$ and $H \circ H|_D = g \circ F \circ g \circ F|_D = g \circ F|_D = H|_D$. It follows that $H \in \mathcal{C}''_D$.

Now, let $f = F|_{\mathrm{ran}(H)}$. Since $\mathrm{ran}(H) = \mathrm{ran}(g \circ F) = \mathrm{ran}(g)$, the map $f$ is one-to-one. Finally, we have $f \circ H = F \circ H = F \circ g \circ F = F$. □

Using Proposition 3.6 we can now derive the following two generalizations of Theorem 3.4.

**Theorem 3.7.** Assume AC, let $D \subseteq X^*$, and let $F: X^* \to Y$ be a function. The following assertions are equivalent.

(i) $F \in \mathcal{P}_D$.

(ii) There exist $H \in \mathcal{A}_D$ and a one-to-one function $f: \mathrm{ran}(H) \to Y$ such that $F = f \circ H$.

(iii) There exist $H \in \mathcal{A}_D$ such that $H(D) \subseteq D$ and a one-to-one function $f: \mathrm{ran}(H) \to Y$ such that $F = f \circ H$.

For any $g \in Q_D(F)$, we can choose $H = g \circ F$ and $f = F|_{\mathrm{ran}(H)}$ in assertions (ii) and (iii).

*Proof.* (i) ⇔ (iii) Setting $\Omega = X^*$ and $\mathcal{C} = \mathcal{P}_D$, we have

$$ \mathcal{C}''_D = \{H: X^* \to \mathrm{ran}(H) \mid H \in \mathcal{P}_D, H(D) \subseteq D, \text{ and } H \circ H|_D = H|_D\}. $$
By Proposition 3.2, we also have

$$C_D'' = \{ H: X^* \to \mathrm{ran}(H) \mid H \in \mathcal{A}_D \text{ and } H(D) \subseteq D \}.$$

We conclude the proof by making use of the equivalence between (i) and (iii) of Proposition 3.6.

$$ (iii) \Rightarrow (ii) \Rightarrow (i) \text{ Straightforward.} \quad \square $$

**Theorem 3.8.** Assume $AC$, let $D \subseteq X^*$, and let $F: X^* \to Y$ be a function. The following assertions are equivalent.

(i) $F \in \mathcal{P}'_D$.

(ii) There exist $H \in \mathcal{A}'_D$ and a one-to-one function $f: \mathrm{ran}(H) \to Y$ such that $F = f \circ H$.

(iii) There exist $H \in \mathcal{A}'_D$ satisfying $H(D) \subseteq D$ and a one-to-one function $f: \mathrm{ran}(H) \to Y$ such that $F = f \circ H$.

(iv) There exist $H \in \mathcal{A}'_D$ satisfying $\mathrm{ran}(H) \subseteq X^*$ and $H \circ H = H$ and a one-to-one function $f: \mathrm{ran}(H) \to Y$ such that $F = f \circ H$.

For any $g \in Q(F)$ (resp. $g \in Q_D(F)$), we can choose $H = g \circ F$ and $f = F|_{\mathrm{ran}(H)}$ in assertions (ii) and (iv) (resp. assertions (ii) and (iii)).

*Proof.* (i) $\Leftrightarrow$ (iii) The proof follows from Propositions 3.3 and 3.6 with $C = \mathcal{P}'_D$ and considering $C_D''$.

(i) $\Leftrightarrow$ (iv) The proof follows from Propositions 3.3 and 3.6 with $C = \mathcal{P}'_D$ and considering $C_X''$.

$$ (iv) \Rightarrow (ii) \Rightarrow (i) \text{ Straightforward.} \quad \square $$

We observe that Theorem 3.4 is a consequence of Theorem 3.7 (or, equivalently, of Theorem 3.8) whenever $D = X^*$.

### 4. FUNCTIONS HAVING A D-DETERMINED RANGE

We now turn our attention to classes of functions with a prescribed range. Recall that, for every integer $m \ge 0$, a function $F: X^* \to X^*$ is said to be *m-bounded* if $|F(x)| \le m$ for every $x \in X^*$. A function $F: X^* \to Y$ is said to have an *m-determined range* if $\mathrm{ran}(F) = \bigcup_{k=0}^m \mathrm{ran}(F_k)$ (see [3]). These concepts can be generalized in the following way.

**Definition 4.1.** Let $D$ be a nonempty subset of $X^*$. We say that a map $F: X^* \to Y$

• is *D-valued* if $\mathrm{ran}(F) \subseteq D$.

• has a *D-determined range* if $\mathrm{ran}(F) = F(D)$.

Note that the property of having a *D-determined range* is preserved under left composition with unary maps: if $F: X^* \to Y$ has a *D-determined range*, then so has $g \circ F$ for any map $g: Y \to Y'$, where $Y'$ is an nonempty set.

**Lemma 4.2.** Let $D$ be a nonempty subset of $X^*$.

(a) If $F: X^* \to X^*$ is *D-valued* and satisfies $F = F \circ F$, then $F$ has a *D-determined range*.

(b) If $F: X^* \to Y$ has a *D-determined range* and satisfies $F(D) \subseteq X^*$ and $F|_D = F \circ F|_D$, then it satisfies $\mathrm{ran}(F) \subseteq X^*$ and $F = F \circ F$.

(c) If $F: X^* \to Y$ satisfies $F = F \circ H$, where $H: X^* \to X^*$ is *D-valued*, then it has a *D-determined range*.
(d) If $F: X^* \to X^*$ is in $\mathcal{A}'_D$, $D$-valued, and satisfies $F = F \circ F$, then it is associative.

(e) If $F: X^* \to Y$ is in $\mathcal{A}'_D$ and has a $D$-determined range, then it is associative.

(f) If $F: X^* \to Y$ is in $\mathcal{P}'_D$ and has a $D$-determined range, then it is preassociative.

**Proof.** The proofs of statements (a)–(e) are straightforward. To see that (f) holds, let $\mathbf{y}, \mathbf{y}' \in X^*$ such that $F(\mathbf{y}) = F(\mathbf{y}')$. Since $F$ has a $D$-determined range, there exists $\mathbf{u} \in D$ such that $F(\mathbf{y}) = F(\mathbf{u}) = F(\mathbf{y}')$. Since $F \in \mathcal{P}'_D$, we thus have $F(\mathbf{x}\mathbf{y}\mathbf{z}) = F(\mathbf{x}\mathbf{u}\mathbf{z}) = F(\mathbf{x}\mathbf{y}'\mathbf{z})$, which shows that $F$ is preassociative. $\square$

**Theorem 4.3.** Assume $AC$, let $D \subseteq X^*$, and let $F: X^* \to Y$ be a function. The following assertions are equivalent.

(i) $F$ is preassociative and has a $D$-determined range.

(ii) $F$ is in $\mathcal{P}'_D$ and has a $D$-determined range.

(iii) There exist an associative and $D$-valued function $H: X^* \to X^*$ and a one-to-one function $f: \text{ran}(H) \to Y$ such that $F = f \circ H$.

(iv) There exist a function $H \in \mathcal{A}'_D$ with a $D$-determined range and a one-to-one function $f: \text{ran}(H) \to Y$ such that $F = f \circ H$.

(v) There exist an associative function $H: X^* \to X^*$ with a $D$-determined range and a one-to-one function $f: \text{ran}(H) \to Y$ such that $F = f \circ H$.

**Proof.** The equivalence between (i) and (iii) follows from Proposition 3.6, where $C$ is the class of preassociative functions on $X^*$ that have a $D$-determined range. Indeed, by Lemma 4.2(a), Lemma 4.2(b) and Proposition 3.1 the class $C''_D$ then consists of the $D$-valued associative functions on $X^*$. The equivalence between (i) and (ii) follows from Lemma 4.2(f). The equivalence between (ii) and (iv) follows from Theorem 3.8 and the fact that the property of having a $D$-determined range is preserved under left composition. The implication (iv) $\Rightarrow$ (v) follows from Lemma 4.2(e). The implication (v) $\Rightarrow$ (iv) is trivial. $\square$

As far as the sets $D_m$ ($m \ge 0$) are concerned, we also have the following result, which provides an alternative condition for a function in $\mathcal{P}'_{D_m}$ to have an $m$-determined range.

**Proposition 4.4.** Let $F: X^* \to Y$ be in $\mathcal{P}'_{D_m}$. The following assertions are equivalent:

(i) $\text{ran}(F_{m+1}) \subseteq \bigcup_{k=0}^m \text{ran}(F_k)$

(ii) $\text{ran}(F) = \bigcup_{k=0}^m \text{ran}(F_k)$ ($F$ has an $m$-determined range).

**Proof.** (ii) $\Rightarrow$ (i) Trivial (preassociativity is not needed).

(i) $\Rightarrow$ (ii) We only need to show that $\text{ran}(F) \subseteq \bigcup_{k=0}^m \text{ran}(F_k)$. Let $F(\mathbf{x}) \in \text{ran}(F)$. We have to consider the following mutually exclusive cases:

(a) If $|\mathbf{x}| \le m$, then we are done since $F(\mathbf{x}) \in \bigcup_{k=0}^m \text{ran}(F_k)$.

(b) If $|\mathbf{x}| = k \ge m+1$, then by (i) there exists $\mathbf{u} \in X^*$, with $|\mathbf{u}| \le m$, such that $F(x_1 \cdots x_{m+1}) = F(\mathbf{u})$. Since $f \in \mathcal{P}'_{D_m}$, we have $F(\mathbf{x}) = F(\mathbf{y})$, where $\mathbf{y} = \mathbf{u}x_{m+2} \cdots x_k$. Since $|\mathbf{y}| < |\mathbf{x}|$, we can iterate the process and then we are done after at most $|\mathbf{x}| - m$ iterations. $\square$
5. CONCLUSION AND FURTHER RESEARCH

The properties of associativity and preassociativity for functions defined over
strings are given in terms of a functional equation and a logical implication, respec-
tively. In this paper we relaxed these properties by imposing restrictions on the
variables of these defining conditions.

In particular, in Section 2 we showed that certain restrictions on the length of
the string variables induce strict hierarchies of nested classes whose intersections
reduce to the classes of associative and preassociative functions, respectively. Apart
from the theoretical interest, such hierarchies can be used to measure degrees of
associativeness (resp. preassociativeness). Indeed, by setting $d(f) = 2^{-k}$ where $k$ is
the minimum positive integer $m$ such that $f \in \mathcal{A}_{D_m} \setminus \mathcal{A}_{D_{m+1}}$ (resp. $f \in \mathcal{P}_{D_m} \setminus \mathcal{P}_{D_{m+1}}$),
we see that $d$ measures how distant $f$ is from being associative (resp. preassociative).

In Section 3, for each nonempty $D \subseteq X^*$, we provided additional conditions
that reduce classes $\mathcal{P}_D$ and $\mathcal{P}'_D$ to $\mathcal{A}_D$ and $\mathcal{A}'_D$, respectively. These results were
then complemented by factorizations of $\mathcal{P}_D$ and $\mathcal{P}'_D$ into composites $\mathcal{I} \circ \mathcal{A}_D$ and
$\mathcal{I} \circ \mathcal{A}'_D$, where $\mathcal{I}$ is a class of one-to-one functions. These factorization results may
be particularly useful. Indeed, they enable us to construct functions in $\mathcal{P}_D$ (resp.
$\mathcal{P}'_D$) from known functions in $\mathcal{A}_D$ (resp. $\mathcal{A}'_D$). Also, they may enable us to obtain
new axiomatizations of subclasses of $\mathcal{P}_D$ (resp. $\mathcal{P}'_D$) from existing axiomatizations
of subclasses of $\mathcal{A}_D$ (resp. $\mathcal{A}'_D$). This observation was already fruitfully used for
$D = X^*$ (see [7]).

Regarding the idea of restricting the variables, alternative natural variants of as-
sociativity and preassociativity are to be considered. For instance, for any nonempty
subset $D$ of $X^*$, consider the class of functions

$$
\mathcal{A}_D^0 = \{ F: D \to X^* \mid (1) \text{ holds for all } \mathbf{x}, \mathbf{y}, \mathbf{z} \in X^* \text{ such that } \mathbf{x}yz, \mathbf{y}, \mathbf{x}F(\mathbf{y})\mathbf{z} \in D \}.
$$

It is clear that if $F \in \mathcal{A}_D$, then $F|_D \in \mathcal{A}_D^0$. However, the converse is an open question of interest: give necessary and sufficient conditions on a nonempty subset $D \subseteq X^*$ and a function $F \in \mathcal{A}_D^0$ for the existence of an extension $G \in \mathcal{A}_D$ (i.e., $G|_D = F$). For example, if $\mathbf{x}D\mathbf{z} \subseteq D$ for all $\mathbf{x}, \mathbf{z} \in X^*$ and $F(D) \subseteq D$, then the function $G$ defined by $G|_D = F$ and $G|_{X^* \setminus D} = \text{id}_{X^* \setminus D}$ is in $\mathcal{A}_D$.

The same question can be addressed for the class

$$
\mathcal{P}_D^0 = \{ F: D \to \text{ran}(F) \mid (2) \text{ holds for all } \mathbf{x}, \mathbf{y}, \mathbf{y}', \mathbf{z} \in X^* \text{ such that } \mathbf{x}yz, \mathbf{xy}z, \mathbf{y}, \mathbf{y}' \in D \}.
$$

These questions constitute topics of ongoing research work.

REFERENCES

[1] D. Jurafsky, J. H. Martin. Speech and Language Processing. 2nd Edition. Prentice Hall, 2008.

[2] D. E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd Edition. Addison-Wesley Professional, New York, 1998.

[3] E. Lehtonen, J.-L. Marichal, B. Teheux. Associative string functions. *Asian-European Journal of Mathematics*, 7(4):1450059 (18 pages), 2014.

[4] J.-L. Marichal, P. Mathonet, and J. Tomaschek. A classification of barycentrically associative polynomial functions. *Aequat. Math.*, in press, 2015. DOI: 10.1007/s00010-014-0332-0

[5] J.-L. Marichal and B. Teheux. Associative and preassociative functions. *Semigroup Forum*, 89(2):431–442, 2014.

[6] J.-L. Marichal and B. Teheux. Associative and preassociative functions (improved version). Working paper (arXiv:1309.7303v3).

[7] J.-L. Marichal and B. Teheux. Preassociative aggregation functions. *Fuzzy Sets and Systems*, 268:15–26, 2015.
[8] J.-L. Marichal and B. Teheux. Barycentrically associative and preassociative functions. *Acta Mathematica Hungarica*, 145(2):468–488, 2015.

[9] B. Schweizer and A. Sklar. *Probabilistic metric spaces*. North-Holland Series in Probability and Applied Mathematics. North-Holland Publishing Co., New York, 1983. (New edition in: Dover Publications, New York, 2005).

LORIA, (CNRS - INRIA NANCY GRAND EST - UNIVERSITÉ DE LORRAINE), BP239 - 54506
VANDOEUVRE-LÈS-NANCY, FRANCE

*E-mail address: miguel.couceiro[at]inria.fr*

MATHEMATICS RESEARCH UNIT, FSTC, UNIVERSITY OF LUXEMBOURG, 6, RUE COUDENHOVE-KALERGI, L-1359 LUXEMBOURG, LUXEMBOURG

*E-mail address: jean-luc.marichal[at]uni.lu*

MATHEMATICS RESEARCH UNIT, FSTC, UNIVERSITY OF LUXEMBOURG, 6, RUE COUDENHOVE-KALERGI, L-1359 LUXEMBOURG, LUXEMBOURG

*E-mail address: bruno.teheux[at]uni.lu*