Out-Of-Order Membership in Regular Languages

One first related topic is the query complexity of regular languages $L$, i.e., the asymptotic number of (interactively chosen) characters that need to be inspected in an input word $w$ to decide whether $w\in L$. This problem requires $\mathrm{\Omega }(n)$ on words of length $n$ for almost all regular languages $L$ (and in $O(1)$ for a narrow class); but it admits a more interesting classification in the quantum setting [1]. This question has been further extended to property testing [4] where we only need to discriminate between words in $L$ and words that are far from $L$ according to a certain distance. In this context, a trichotomy on the query complexity of property testing has been achieved [8]. However, all of these problems differ from out-of-order membership: they assume that we can freely choose positions to inspect, whereas in out-of-order membership the streaming order is arbitrary. They also focus on the number of queries needed, whereas with out-of-order membership we receive all positions and focus on the time and space complexity.

Another related line of work is sliding window membership, where we want to test membership to a fixed language $L$ for a sliding window over a stream. Works on this problem have investigated the complexity of various languages $L$, first in terms of time per character [13], and then in terms of memory usage, with again a recent trichotomy on space complexity for regular languages in several settings [12]. Other works extend sliding windows by considering possible arrival of out-of-order elements, in particular for aggregation [26, 23, 9]. However, one important general difference of the sliding window setting is that we must maintain membership to $L$ for the various states of the sliding window across the stream, with letters that leave the sliding window when they expire. By contrast, in our context, we only test membership of a single word, and revealed positions never expire; but the arrival order is arbitrary and not sequential. Hence, for instance, the language $a{\mathrm{\Sigma }}^{\ast }$ admits constant space out-of-order membership (by storing the first character) but requires linear space in the sliding window setting [12], and conversely one can show that out-of-order membership to the language ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$ requires linear space (see Proposition 2.3) but it can be tested in logarithmic space in the sliding window setting [12].

Another related setting is dynamic membership, where we must test whether a word $w$ belongs to a regular language $L$ and maintain this information under updates to $w$ (not just the push-right and pop-left updates of sliding windows). In particular, a conditional trichotomy has been shown under substitution updates [5], i.e., where we receive updates $(a,i)$ that change the $i$-th letter of the word to the letter $a$. Out-of-order membership is analogous to a special case of this setting where each position is set exactly once and never changed afterwards. However, [5] always assumes to have linear memory to store the current state of $w$ – their trichotomy is on time complexity and not space complexity. In fact, unlike their setting, we will show that all regular languages admit an out-of-order membership algorithm in $O(1)$ time per character.

Last, the setting closest to ours is the communication complexity of regular language membership, studied in particular by Tesson and Thérien [25] and then by Ada [2]. In this setting, we wish again to determine whether a word $w$ belongs to a regular language $L$, but $w$ is split across multiple players and we wish to minimize how much information they need to exchange to determine whether $w\in L$. Many communication complexity models are quite different from out-of-order membership, e.g., the multiparty setting of [20], along with randomized settings [25] and nondeterministic settings [2]. The most relevant model is the two-player setting of [25]: the word is split between Alice (for odd positions) and Bob (for even positions), and they can exchange information in arbitrarily many rounds to determine membership. Communication lower bounds in this model imply space complexity lower bounds in our setting: if we are first streamed the even positions, then the information that we remember gives a one-way protocol from Alice to Bob. However, upper bounds in their setting do not necessarily translate to ours, because our algorithms do not obey a fixed partition. As we show in the special case of languages featuring a neutral letter (i.e., the case of monoids), the complexity of out-of-order membership happens to coincide with the communication complexity for another model studied in [25], namely, the simultaneous setting in which Alice and Bob must each send information to a referee. This is surprising because, as far as we understand, there is no reduction from their model to ours or vice-versa. Nevertheless, as the tractability boundary is the same, our algebraic proofs in this specific setting relate to theirs, as we will explain. In any case, all results in [25] crucially assume the presence of a neutral letter (i.e., some of the letters of Alice and/or Bob may be $ϵ$): the issue is further discussed in [24, Section 5.2], and it has significant impact in our setting as well, as we will see when presenting our contributions below.

In this paper, we introduce the out-of-order membership problem for regular languages, and give first results on its complexity, including a complete space trichotomy classification for the case of monoids and a characterization of constant space for semigroups. We present these contributions in more detail below along with the structure of the paper.

We introduce formally the problem and our model in Section 2, and give some first complexity results. Specifically, in the unit-cost RAM model with logarithmic word size, we show that every fixed regular language admits an out-of-order membership algorithm with constant time per streamed character and linear memory usage (Theorem 2.1). For this reason we only focus on space complexity in the remainder of the paper. We close the section by adapting the classical technique of fooling sets for unconditional lower bounds, which we use throughout the paper; we exemplify it to show a linear space lower bound for ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$ (Proposition 2.3). By contrast, we show that better bounds are possible for some languages, namely, commutative languages admit constant space out-of-order membership (Lemma 2.4).

As classifying regular languages turns out to be challenging, we focus in the rest of the paper on algebraically defined variants of the problem. In Section 3, we introduce the simplest such problem: the out-of-order evaluation problem for a monoid $M$, where we are streamed a word $w$ of monoid elements in an out-of-order fashion and must compute the product of $w$ in $M$, while minimizing the space usage. The point of out-of-order evaluation is that it can provide algorithms for out-of-order membership to languages (via their syntactic monoid), and it intuitively amounts to assuming that languages have been closed under the addition of a neutral letter, simplifying the classification. Further, we show that the complexity regimes of out-of-order monoid evaluation form varieties of monoids, so the problem is amenable to algebraic tools. We accordingly study out-of-order monoid evaluation and prove (Theorem 3.2) that monoids admit three space complexity regimes, with matching upper and lower bounds: constant space for commutative monoids, logarithmic space for monoids in a class dubbed $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$, and linear space for all other monoids. The variety $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ intuitively extends commutative monoids with the ability to remember a constant number of leftmost and rightmost occurrences of each element. It turns out that the join variety $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ is the same as the variety $𝐖$ introduced in [25] (with a less informative characterization). Thus, the complexity of deterministic simultaneous communication complexity according to [25], in the specific case of monoids, happens to coincide with the space complexity of our out-of-order evaluation problem – even though neither problem seems to capture the other. Our classification is summarized in the first column of Table 1, with examples (as syntactic monoids of languages) in Table 2.

We then turn in Section 4 to the more general problem of out-of-order evaluation for semigroups, i.e., monoids but without the requirement of having a neutral element. The problem turns out to be much more challenging in the semigroup setting, and thus we only focus on the constant space regime, which we are able to characterize (Theorem 4.4). Namely, we show a constant space algorithm for semigroups in $\mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$, i.e., intuitively extending commutative semigroups with the ability to test constant-length prefixes and suffixes of the word (see Table 2 for an example). We show a logarithmic lower bound for all other semigroups.

In Section 5, we show that classifying the higher complexity regimes appears much more intricate. For convenience we present results on the out-of-order membership problem, but the difficulties that we highlight already appear for out-of-order semigroup evaluation (for space complexities beyond the constant regime). We first give ad hoc logarithmic upper bounds for $a^{\ast }{b}^{\ast }{a}^{\ast }$ (Proposition 5.1) and for $a^{\ast }{b}^{\ast }{a}^{\ast }{b}^{\ast }{a}^{\ast }$ (Proposition 5.2) using completely different techniques. We then show (Proposition 5.3) an unexpected sublinear $O(\sqrt{n})$ space upper bound for $a^{\ast }{b}^{\ast }{a}^{\ast }{b}^{\ast }{a}^{\ast }{b}^{\ast }$ for which we have no better complexity upper bound and no superlogarithmic lower bound. See Table 1 for the overall complexity bounds achieved for out-of-order evaluation, and Table 2 for examples.

We conclude and propose further research directions in Section 6. For lack of space, most detailed proofs are deferred to the appendix.

Let $\mathrm{\Sigma }$ be an alphabet, let $n>0$ be a word length, let $w=w[1]\mathrm{\cdots }w[n]$ be a word over $\mathrm{\Sigma }$ of length $n$, and let ${\pi }_n$ be an $n$-permutation, i.e., a permutation of $\{1,\mathrm{\dots },n\}$. The out-of-order stream of the word $w$ defined by ${\pi }_n$ is the finite sequence $R$ of length $n$ whose successive elements are $(w[\pi (i)],\pi (i),n)$ for $i=1,\mathrm{\dots },n$. Intuitively, we receive the letters of $w$ together with their position in the order $\pi (1),\mathrm{\dots },\pi (n)$. Note that the length $n$ of the word is provided as the third component of each element: this is because we assume throughout the work that the length $n$ is always known and we do not want to account for it when measuring space complexity.

We only consider regular languages in this paper, and we omit their definition. A letter $a\in \mathrm{\Sigma }$ is neutral for a language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ if for any $s,t\in {\mathrm{\Sigma }}^{\ast }$ we have $sat\in L$ if and only if $st\in L$. For a fixed regular language $L$ over $\mathrm{\Sigma }$, the out-of-order membership problem for $L$ is the following task: letting $w$ be a word of length $n$ over $\mathrm{\Sigma }$, letting ${\pi }_n$ be an $n$-permutation, and letting $R$ be the out-of-order stream on $w$ defined by ${\pi }_n$, we receive the elements of $R$ one after the other and must decide at the end whether $w\in L$ or not.

Note that the standard membership test to a fixed language $L$ for a word $w$ streamed from left-to-right corresponds to the case where ${\pi }_n$ is the identity permutation. For left-to-right membership testing, we can simply use an automaton for $L$ and achieve constant space and constant time per character; but for out-of-order membership the challenge is that we must support arbitrary permutations. Further note that we can always solve the problem by storing the letters in an array $T$ as they arrive, i.e., whenever we receive $(a,i,n)$ we set $T[i]≔a$ and we test at the end whether the word stored in $T$ belongs to $L$. This gives a naive algorithm which uses linear space and runs in constant worst-case complexity per streamed character except that it spends linear time after the last character. Let us now present a more efficient algorithm that avoids this drawback.

We first study efficient algorithms for out-of-order membership to fixed regular languages in terms of time complexity per streamed character. For this result on time complexity, and only for this result, we need to be precise about the computational model that we assume; subsequent results will only focus on space complexity and will apply no matter which computations are allowed. We work in the standard unit-cost RAM model with logarithmic word size [11, 14]. Memory consists of cells of size $w=\mathrm{\Theta }(\log n)$ bits, and reading, writing, or performing standard operations on these cells takes constant time. Our set of allowed operations includes addition, subtraction, increment, comparisons, integer division with remainder, shifts, bitwise Boolean operations, and computing the most significant bit. We will also use the standard lazy array evaluation technique to assume when allocating arrays that they can be initialized in constant time [14]. The algorithm receives the successive triples $(a,i,n)$ of the out-of-order stream, with the values being stored in three $\mathrm{\Theta }(\log n)$-bit cells. Here, $a$ uses constant bits (as the alphabet is fixed), while $i$ and $n$ are integers represented on $\mathrm{\Theta }(\log n)$ bits.

In the computational model defined above, we can show that all regular languages admit an algorithm with $O(1)$ complexity per letter and a linear space usage of $O(n)$ bits (i.e., amounting to $O(n/\log n)$ memory cells).

Let $M$ be the syntactic monoid of $L$ (see Section 3 for the formal definitions). We divide the input word into blocks of length $\lceil \log n\rceil$, so that each block can be represented in a constant number of RAM cells. The algorithm has two layers. The macro layer treats complete blocks as atomic symbols: for every maximal contiguous interval of complete blocks, it stores the interval length at both endpoints and the product in $M$ of the block values at the left endpoint. The micro layer maintains analogous information inside each block, using one bit vector to record which positions of the block have already been streamed and a packed vector of monoid elements to store the values in $M$ of maximal contiguous streamed intervals (which correspond to maximal contiguous intervals of 1’s in the bit vector), each value being stored at the left endpoint of its interval.

When a letter is streamed, we first update its block in the micro layer. To do this, we must compute the maximal contiguous interval of 1’s to which the streamed letter belongs. This is accomplished by creating a singleton interval of 1’s in the bit vector, and then trying to merge it with the interval of 1’s immediately to its right and the interval immediately to its left. If there is an interval to the right, then merging with this interval is immediate because the monoid value of the interval is stored at its left endpoint (i.e., immediately to the right of the new position). For the merge with the left interval, we must find the left endpoint of that interval, which we do in constant time by shifting the bit vector of the block and applying the most-significant-bit operation. Hence the micro update takes constant time, noting that multiplication in $M$ is constant-time since $L$ is fixed.

Now, if this update completes the block, we insert it into the macro structure. To do this, we first create the block as a singleton block interval in the macro layer, whose monoid value is the value of the newly computed block. Then we compute the maximal interval of complete blocks to which the block belongs, again by attempting to merge its singleton interval with the neighboring interval on the right and the neighboring interval on the left if they exist. These macro merges take constant time because the interval lengths and monoid values are stored at interval endpoints.

At the end of the stream, all blocks form a single macro interval. Its stored monoid value is $\mu (w)$, from which we can deduce whether $w\in L$.

The overall space bound is $O(n)$ bits: the macro arrays have $O(n/\log n)$ entries of one RAM cell each, while the packed micro bit vectors and monoid vectors use $O(\log n)$ bits per block. We use lazy array evaluation [14] to ensure that our data structures are initially zero without the need for running a preprocessing phase. $◀$

In light of Theorem 2.1, in the remainder of the paper we focus on space complexity. We only study deterministic space complexity. We always account for space complexity in terms of the number of bits used (not memory cells), and we only consider the space that must be memorized between any two elements of the out-of-order stream; we do not consider the computation time and interim memory needed when processing an element.

We now introduce fooling sets as a general technique to prove unconditional lower bounds, and showcase fooling sets to show a linear space lower bound on the specific language ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$. Our fooling sets are an out-of-order analogue of standard techniques (see, e.g., [18, Definition 2] for a similar notion) used for the state complexity of regular languages when reading words from left to right, e.g., to show that any deterministic automaton for the language $L_n={\mathrm{\Sigma }}^{\ast }a{\mathrm{\Sigma }}^n$ must have at least $2^{n+1}$ states (see [17, Example 2.13] which proceeds along similar lines).

Let $\mathrm{\_}$ be a fresh placeholder symbol, and write $\overline{X}≔X\cup \{\mathrm{\_}\}$ for a set extended by $\mathrm{\_}$. A partial word over an alphabet $\mathrm{\Sigma }$ is a word $w$ over the alphabet $\overline{\mathrm{\Sigma }}$. The domain of $w$ is the subset $\mathrm{dom}(w)$ of the positions where $w$ does not carry a placeholder, i.e., $\mathrm{dom}(w)≔\{i\in \{1,\mathrm{\dots },|w|\}\mid w[i]\in \mathrm{\Sigma }\}$. Two partial words $w_1,w_2$ are homogeneous if $|w_1|=|w_2|$ and $\mathrm{dom}(w_1)=\mathrm{dom}(w_2)$, and a set $S$ of partial words is homogeneous if all its partial words are pairwise homogeneous. Now, two partial words $w_1,w_2$ are compatible if they have the same length and if $\mathrm{dom}(w_1)\cap \mathrm{dom}(w_2)=\mathrm{\varnothing }$, i.e., for all $1\le i\le |w_1|$ at least one of $w_1$ and $w_2$ has a placeholder at position $i$. Their composition $w_1\circ w_2$ is then the partial word defined by $(w_1\circ w_2)[i]≔w_1[i]$ if $i\in \mathrm{dom}(w_1)$, and $(w_1\circ w_2)[i]≔w_2[i]$ otherwise. We further call two compatible words $w_1$ and $w_2$ complementary if $\mathrm{dom}(w_1)\cup \mathrm{dom}(w_2)=\{1,\mathrm{\dots },n\}$, equivalently, $w_1\circ w_2$ is a word of ${\mathrm{\Sigma }}^{\ast }$ without placeholders. Given a language $L\subseteq {\mathrm{\Sigma }}^{\ast }$, a word length $n$, and two homogeneous partial words $w_1,w_2\in {\overline{\mathrm{\Sigma }}}^n$, we call complementary witness of $w_1,w_2$ for $L$ a partial word $v\in {\overline{\mathrm{\Sigma }}}^{\ast }$ complementary to both $w_1$ and $w_2$, such that precisely one of $w_1\circ v$ and $w_2\circ v$ belongs to $L$.

For $L$ a language over $\mathrm{\Sigma }$ and $n,m\in \mathbb{N}$, an $(m,n)$-fooling set for $L$ is a homogeneous set $W=\{w_0,\mathrm{\dots },w_{m-1}\}$ of $m$ partial words $w_i\in {\overline{\mathrm{\Sigma }}}^n$ such that any two distinct partial words $w_i,w_j\in W$ have a complementary witness for $L$.

The proof of Lemma 2.2 is standard and deferred to the full version [6] : we simply argue that the algorithm must have enough memory to distinguish each partial word among those of the fooling set. Note that, in the result statement above and everywhere in the paper, we write $g=\mathrm{\Omega }(f)$ for two functions $f,g:{\mathbb{N}}_{>0}\to {\mathbb{N}}_{>0}$ to mean that ${lim\; sup}_{n\to \mathrm{\infty }}g(n)/f(n)>0$. This is the $\mathrm{\Omega }$ notation of Hardy and Littlewood [16] and not the one by Knuth [19] (which is defined as meaning $f=O(g)$). For instance, letting $g$ be the function defined by $g(n)≔n$ for odd $n$ and $g(n)≔1$ otherwise, we have $g=\mathrm{\Omega }(n)$. This is important, e.g., to show lower bounds on out-of-order membership for languages that are hard for words of odd length and trivial for words of even length.

Let us showcase Lemma 2.2 and prove that some languages require linear space for out-of-order membership:

For each length $n$, we define a $(2^n,3n)$-fooling set $W_n$ for ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$ formed of the $2^n$ partial words defined by the regular expression ${(b(a+b)\mathrm{\_})}^n$. Note that they are all homogeneous and have length $3n$. Let $w_i,w_j$ be two distinct partial words of $W_n$. There must be a position such that $w_i[3p+2]\ne w_j[3p+2]$. Note that this means one is $a$ and the other is $b$; without loss of generality up to exchanging $w_i$ and $w_j$ we assume that $w_i[3p+2]=a$ and $w_j[3p+2]=b$. Now, we let $v_{ij}≔{(\mathrm{\_}\mathrm{\_}b)}^{p-1}(\mathrm{\_}\mathrm{\_}a){(\mathrm{\_}\mathrm{\_}b)}^{n-p}$. We see that $v_{ij}$ is complementary to both $w_i$ and $w_j$. Further, by construction $w_i\circ v_{ij}$ belongs to ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$ because there are two contiguous $a$’s at positions $3p+2$ and $3p+3$. By contrast, $w_j\circ v_{ij}$ does not belong to ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$. This establishes that $W_n$ is indeed a $(2^n,3n)$-fooling set for ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$ and concludes the proof. $◀$

We will use fooling sets to show all the lower bounds in this paper; in particular these bounds are all unconditional. Note that this also implies that all our lower bounds already hold for streaming orders that are chosen in advance, i.e., when we show a lower bound on a language for words of length $n$ then we show the existence of an $n$-permutation such that the space lower bound applies even on algorithms that work only for that specific permutation. We also note that lower bounds shown with this method can be understood as a lower bound on fixed-partition communication complexity for a one-way protocol, where Alice has access to the letters on the domain of the fooling set and Bob has access to the rest of the word.

We complement the previous result by noticing that the linear space complexity lower bound does not apply to all languages: we can sometimes solve out-of-order membership with better space complexity. We will show the easy fact that, for commutative regular languages, out-of-order membership can be solved with constant space. Here, a language is commutative if, for every word $w$, letting $n≔|w|$, for every $n$-permutation $\pi$, we have $w\in L$ if and only if $w[\pi (1)]\mathrm{\cdots }w[\pi (n)]\in L$. Then:

Fix a deterministic automaton $A$ that accepts $L$. Now, whenever we receive some tuple $(a,i,n)$, we feed $a$ to $A$. This takes constant time, and the memory of the algorithm stores the automaton state, which has constant size because $L$ is fixed. At the end of the stream, we accept if $A$ accepts. It is immediate that $A$ was fed a permutation of the word $w$: as $L$ is commutative, the algorithm is correct, which concludes. $◀$

The condition of being commutative is sufficient but is not necessary to have constant-space complexity, as illustrated below:

In summary, we have shown that out-of-order membership to fixed regular languages can always be solved in constant time per streamed character and linear memory, and this memory bound is optimal for some languages (e.g., ${\mathrm{\Sigma }}^{\ast }aa{\mathrm{\Sigma }}^{\ast }$) but suboptimal for others (e.g., commutative languages or ${(ab)}^{\ast }$ for which the bound is $O(1)$). Thus, our goal is to classify regular languages according to the space complexity in this sense. Towards this, we will present algebraic variants of the problem on which classifications are easier to show.

All monoids in this paper are implicitly finite. Let $M$ be a fixed monoid, let $n>0$ be the word length, and let $w=w[1]\mathrm{\cdots }w[n]$ be a word over $M$ of length $n$; its product is the value $w[1]\cdot \mathrm{\cdots }\cdot w[n]$ of $M$ obtained according to the composition law of $M$. We define out-of-order streams like in the previous section. The out-of-order evaluation problem for $M$ is the following task: letting $w$ be a word of length $n$, letting ${\pi }_n$ be an $n$-permutation, and letting $R$ be the out-of-order stream on $w$ defined by ${\pi }_n$, we receive the elements of $R$ one after the other and must compute at the end the product of $w$ in $M$.

We note that the out-of-order evaluation problem for a monoid $M$ can be expressed in terms of out-of-order membership problems. Indeed, for any $x\in M$, the language $L_x$ over $M$ defined as the words of $M^{\ast }$ having product $x$ is always a regular language. Likewise, the out-of-order membership problem for a language $L$ reduces to the out-of-order evaluation problem for the syntactic monoid of $L$, i.e., the finite monoid obtained by quotienting ${\mathrm{\Sigma }}^{\ast }$ by the syntactic congruence equivalence relation ${\sim }_L$ defined by $L$. Intuitively, ${\sim }_L$ equates words whose behavior relative to $L$ is the same, and formally we have $u{\sim }_{L}v$ for two words $u,v\in {\mathrm{\Sigma }}^{\ast }$ whenever for any $s,t\in {\mathrm{\Sigma }}^{\ast }$ we have $sut\in L$ if and only if $svt\in L$. It is well-known that for a regular language $L$ the syntactic congruence ${\sim }_L$ has indeed a finite number of equivalence classes, and in fact this property precisely characterizes the regular languages; see, e.g., [22] for more details.

Thus, algorithms for out-of-order evaluation for the syntactic monoid $M$ of a language $L$ imply an algorithm for out-of-order membership to $L$. However, there are cases where out-of-order membership for $L$ is easier than the same problem for $M$, e.g., because $L$ may not feature a neutral letter but $M$ always has a neutral element. For this reason, classifying the complexity of out-of-order evaluation for monoids is a coarser task than classifying the complexity of out-of-order membership for regular languages, and so it serves as a useful first step.

To start our study of out-of-order evaluation for monoids, let us observe that the complexity classes of monoids for out-of-order evaluation are closed under the monoid variety operators.

The direct product of two monoids $M_1$ and $M_2$ is the monoid $(M_1\times M_2,\cdot )$ with the binary operator defined as $(x_1,x_2)\cdot (x_1^{\prime },x_2^{\prime })=(x_1\cdot x_1^{\prime },x_2\cdot x_2^{\prime })$ and identity $(e_1,e_2)$ for $e_1$ and $e_2$ the respective identities of $M_1$ and $M_2$. A sub-monoid of a monoid $M$ with neutral element $e$ is a subset $M^{\prime }\subseteq M$ of $M$ which is closed under the composition law of $M$ and which is also a monoid with neutral element $e$. A congruence over a monoid $M$ is an equivalence relation $\sim$ over $M$ which satisfies the following requirement: whenever $s\sim t$ and $s^{\prime }\sim t^{\prime }$ for $s,t,s^{\prime },t^{\prime }\in M$ then we have $s{s}^{\prime }\sim t{t}^{\prime }$. A quotient monoid $M/\sim$ is the quotient of a monoid $M$ by a congruence $\sim$ over $M$, i.e., it consists of the equivalence classes of $M$ under $\sim$, its composition law is lifted to these classes, and its neutral element is the equivalence class of the neutral element of $M$. Note that, thanks to the definition of a congruence, when applying the composition law the results do not depend on the choice of representatives.

A class of monoids is a pseudo-variety, only called variety throughout the paper, if it is closed under direct products, taking sub-monoids, and taking monoid quotients. Let $𝐕$ and $𝐖$ be two varieties of monoids. Their join, denoted $𝐕\vee 𝐖$, is the smallest variety containing both the monoids of $𝐕$ and those of $𝐖$.

We show that, for the problems that we study, each complexity class forms a variety:

Any data structure for the out-of-order evaluation problem for a monoid $M$ can in particular solve it for any submonoid, and it can also solve it for any quotient (simply by picking arbitrary representatives and returning the equivalence class of the result). Further, for any two monoids $M_1$ and $M_2$, we can solve out-of-order evaluation for $M_1\times M_2$ by simultaneously using one data structure for $M_1$ and one for $M_2$. $◀$

Our goal in this section is to classify all monoids $M$ according to the space needed by an algorithm to solve out-of-order evaluation for $M$. Our results will imply the existence of precisely three complexity regimes (constant, logarithmic, and linear), and characterize the corresponding monoids.

Let us first introduce the varieties that constitute the different regimes. The first one is $\mathrm{𝐂𝐨𝐦}$, the variety of commutative monoids. We can characterize it as those monoids $M$ satisfying the equation $xy=yx$ for all $x,y\in M$, i.e., we write $\mathrm{𝐂𝐨𝐦}=⟦xy=yx⟧$. In fact, by Reiterman’s theorem [21], we know that varieties of monoids always admit such equational descriptions (see [22] for more details), so we will define our other monoid varieties using equations in this fashion. Monoids from the variety $\mathrm{𝐂𝐨𝐦}$ admit a constant-space algorithm for the out-of-order evaluation problem, obtained by immediately lifting Lemma 2.4 to monoids. We will show that this in fact characterizes all constant-space monoids, with all other monoids having a logarithmic lower bound.

For the logarithmic space regime, we will characterize it as the join of $\mathrm{𝐂𝐨𝐦}$ together with another variety, called $\mathrm{𝐅𝐋}$ (for “first-last”). To give an equation for $\mathrm{𝐅𝐋}$, we need to define the idempotent power of a monoid $M$ as the smallest non-negative integer $\omega$ such that $x^{\omega }=x^{2\omega }$ for all $x\in M$. Then we can define $\mathrm{𝐅𝐋}=⟦{(xy)}^{\omega }st{(xz)}^{\omega }={(xy)}^{\omega }sxt{(xz)}^{\omega }⟧$. One example of a monoid in $\mathrm{𝐅𝐋}$ is the syntactic monoid of the language ${\mathrm{\Sigma }}^{\ast }a{\mathrm{\Sigma }}^{\ast }b{\mathrm{\Sigma }}^{\ast }$ over the alphabet $\{a,b,e\}$, intuitively because membership can be decided by remembering the position of the leftmost $a$ and of the rightmost $b$. We will show that monoids in $\mathrm{𝐅𝐋}$ admit a logarithmic-space algorithm for out-of-order evaluation, which will imply the same for $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ thanks to Proposition 3.1. It turns out that $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ precisely coincides with the class $𝐖$ in [25] that forms the tractability boundary of a similar but seemingly incomparable problem, namely, the monoids with logarithmic simultaneous deterministic communication complexity.

We will last characterize the linear space regime by showing, using an equational characterization of $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$, that monoids outside of this class require linear space.

All told, in this section, we show the following characterization, summarized in the first column of Table 1 (with all upper bounds matched by tight lower bounds) and examples (given as syntactic monoids of languages) in the first row of Table 2:

We prove this result in the rest of the section. Recall that the first point follows by the immediate analogue of Lemma 2.4 for monoids, for instance:

We give first the logarithmic lower bound for non-commutative monoids (for the lower bound of the second point), then the logarithmic upper bound (for the upper bound of the second point), and then the linear lower bound (for the lower bound of the third point). The upper bound of the third point is immediate by the monoid analogue of Theorem 2.1.

For our two lower bounds in this section, we immediately lift the definitions of fooling sets to the out-of-order monoid evaluation problem in the expected way: the words are defined over the alphabet $\overline{M}$ featuring the monoid elements and the placeholder, and the only new stipulation is that any two words $w_i\ne w_j$ of the fooling set have a complementary witness $v_{ij}$ that ensures that $w_i\circ v_{ij}$ and $w_j\circ v_{ij}$ evaluate to different monoid elements (instead of saying that precisely one belongs to the target language).

We then show the first lower bound, establishing that non-commutative monoids need at least logarithmic space complexity:

Let $x,y\in M$ be two elements such that $xy\ne yx$, and let $e$ be the neutral element. We use Lemma 2.2 (lifted to the setting of monoids) and define for each $n>0$ the fooling set $W_n$ formed of the words $w_i≔{(e\mathrm{\_})}^{i-1}(x\mathrm{\_}){(e\mathrm{\_})}^{n-i}$ for each $1\le i\le n$. The complementary witnesses for are defined as: $v_{ij}≔{(\mathrm{\_}e)}^{i-1}(\mathrm{\_}y){(\mathrm{\_}e)}^{n-i}$, ensuring that $w_i\circ v_{ij}$ evaluates to $xy$ and $w_j\circ v_{ij}$ to $yx$. $◀$

We now show the logarithmic upper bound for languages in $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$. Thanks to the closure under variety operations (Proposition 3.1), using again the constant upper bound for commutative monoids (Lemma 2.4), it suffices to show an upper bound for $\mathrm{𝐅𝐋}$.

Remember our equational definition of $\mathrm{𝐅𝐋}$ using the equation $\mathrm{𝐅𝐋}=⟦{(xy)}^{\omega }st{(xz)}^{\omega }={(xy)}^{\omega }sxt{(xz)}^{\omega }⟧$. We will now show that, whenever a monoid $M$ satisfies this equation, then computing the product of elements of $M$ can be achieved simply by looking at a constant number of leftmost and rightmost occurrences of each element. Let us introduce the requisite definitions on words over $M$:

We note that the first-last subword defined above also occurs in [25], where it is called ${\text{RED}}_k$. Their work then extends this definition to correspond to their variety $𝐖$, which will correspond to $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ as we explain later. By contrast, we will use first-last subwords directly for the simpler variety $\mathrm{𝐅𝐋}$ for our upper bound, and the extension to $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ is for free thanks to Proposition 3.1 and Lemma 2.4. We claim the following property on monoids in $\mathrm{𝐅𝐋}$:

To show this, let us point out how to use the $\mathrm{𝐅𝐋}$ equation on words of elements of $M$. Using standard pumping arguments, we can show:

This claim allows us to show ˜3.6:

We do an induction on the number of elements of $M$ that occur more than $2k$ times in $u$. If there are none, then $v=u$ are equal and the claim is immediate. Otherwise, we pick an element $m$ occurring more than $2k$ times, we isolate its first and last $k$ occurrences, we use ˜3.7 to argue that all other occurrences can be eliminated without changing the product in $M$, and we conclude using the induction hypothesis on the resulting word which has one less element occurring more than $2k$ times. $◀$

We can now state our upper bound on out-of-order evaluation for monoids in $\mathrm{𝐅𝐋}$:

The algorithm remembers the $k$ minimal and the $k$ maximal positions of each element of $M$ during the stream. This allows it to construct ${\mathrm{FL}}^k(u)$ for $u$ the streamed word, and thanks to ˜3.6 the product of ${\mathrm{FL}}^k(u)$ in $M$ is identical to the desired answer, namely, the product of $u$ in $M$. $◀$

The only remaining piece to show Theorem 3.2 is the linear lower bound on monoids not in $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$. Formally:

To show this result, we need an equation characterizing the variety $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$, which we will then use to obtain witnessing elements to build fooling sets. It turns out that $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$ coincides with the class $𝐖$ in [25], so we will reuse part of their proof; however our approach has the merit of proposing a simpler equation for the class, and of giving a presentation of $𝐖$ as a join involving a simpler variety $\mathrm{𝐅𝐋}$ with an equational characterization. We also remind the reader that the results of [25] pertain to communication complexity; as far as we understand, it is a coincidence that tractability boundaries of our problem coincides with one of theirs, because there does not appear to be reductions from one problem to the other.

We accordingly give the following characterization of $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$:

We show $1\to 2\to 3\to 1$. The $1\to 2$ direction follows from the equations of $\mathrm{𝐅𝐋}$ and $\mathrm{𝐂𝐨𝐦}$. The $2\to 3$ direction is easy by equation manipulation. For $3\to 1$ we use the $RE{D}_{t,p}$ congruence defined in [25]. We reuse their proof [25, Theorem 3] which shows that any monoid satisfying the equations of $𝐖$ is refined by a $RE{D}_{t,p}$-congruence: this is the analogue of the result we showed for $\mathrm{𝐅𝐋}$ in ˜3.6. We can then conclude because $RE{D}_{t,p}$ is the intersection of an $\mathrm{𝐅𝐋}$ congruence and of a $\mathrm{𝐂𝐨𝐦}$ congruence. $◀$

With this characterization, we can now prove the linear lower bound (Lemma 3.10):

Let $M$ be a monoid not in $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$. By Lemma 3.11, there are elements in $M$ witnessing a violation of the equation: ${(xa)}^{\omega }sxtu{(xb)}^{\omega }\ne {(xa)}^{\omega }stxu{(xb)}^{\omega }$. We use Lemma 2.2 and build a $(2^n,5n+2)$-fooling set for any $n>0$. For each $\alpha \in {\{0,1\}}^n$ we define $w_{{\alpha }_i}$ by either $\mathrm{\_}x\mathrm{\_}e\mathrm{\_}$ or $\mathrm{\_}e\mathrm{\_}x\mathrm{\_}$ depending on the bit ${\alpha }_i$, let $w_{\alpha }≔\mathrm{\_}{w}_{\alpha ,1}{w}_{\alpha ,2}\mathrm{\dots }{w}_{\alpha ,n}\mathrm{\_}$, and let $W_n≔\{w_{\alpha }\mid \alpha \in {\{0,1\}}^n\}$ be the fooling set.

Now, for any $\alpha \ne \beta$, let $\iota (\alpha ,\beta )$ be a position of $\{1,\mathrm{\dots },n\}$ such that ${\alpha }_{\iota (\alpha ,\beta )}\ne {\beta }_{\iota (\alpha ,\beta )}$. The complementary witness is then:

where the first and last groups in parentheses correspond to a single element.

We can then see that one of $w_{\alpha }\circ v_{\alpha \beta }$ and $w_{\beta }\circ v_{\alpha \beta }$ is ${(xa)}^{n\omega }(sxtu){(xb)}^{n\omega }={(xa)}^{\omega }sxtu{(xb)}^{\omega }$ and the other is ${(xa)}^{n\omega }(stxu){(xb)}^{n\omega }={(xa)}^{\omega }stxu{(xb)}^{\omega }$, so by assumption they are indeed different, showing that $W_n$ is a fooling set. This implies that the out-of-order monoid evaluation problem for $M$ has $\mathrm{\Omega }(n)$ space complexity. $◀$

We illustrate the lower bound of Lemma 3.10 with the following example:

All semigroups in this paper are implicitly finite. The definition of out-of-order evaluation for semigroups is defined exactly like for monoids, but with a semigroup. By the immediate analogue of Proposition 3.1, the complexity regimes of out-of-order semigroup evaluation form varieties of semigroups. Further, the definitions of fooling sets and the corresponding lower bound (Lemma 2.2) also immediately adapt. The syntactic semigroup of a language $L$ is defined like the syntactic monoid but as a quotient of ${\mathrm{\Sigma }}^{+}$, i.e., without including the empty word. (However, it may have a neutral element nevertheless, for instance if $L$ features a neutral letter.)

Like monoid evaluation, the out-of-order semigroup evaluation problem is a coarsening of out-of-order membership, but it is less coarse, in particular it does not require the presence of a neutral letter. We note that our results on monoids already imply lower bounds on some semigroups. For instance, semigroups that are not locally commutative, i.e., which admit a subsemigroup which is a non-commutative monoid, directly inherit the logarithmic space lower bound on monoids (Lemma 3.4) from the previous section:

Let $S$ be a semigroup and $s,x,y\in S$ such that $s^{\omega }x{s}^{\omega }y{s}^{\omega }\ne s^{\omega }y{s}^{\omega }x{s}^{\omega }$. Let $x^{\prime }=s^{\omega }x{s}^{\omega }$ and $y^{\prime }=s^{\omega }y{s}^{\omega }$. We remark that the sub-semigroup generated by $\{s^{\omega },x^{\prime },y^{\prime }\}$ is a monoid with $s^{\omega }$ as its neutral element. Further, it is non-commutative because $x^{\prime }{y}^{\prime }\ne y^{\prime }{x}^{\prime }$. Hence, its evaluation problem has $\mathrm{\Omega }(\log n)$ space complexity, and thus the evaluation problem of $S$ also has $\mathrm{\Omega }(\log n)$ space complexity by closure under sub-semigroups (Proposition 3.1). $◀$

However, the space complexity of out-of-order evaluation for semigroups does not exactly follow the classification on monoids, and new phenomena can arise. For instance:

We just memorize the element at position 1 and the element at position $n$ for $n$ the word length, using constant space; and we return their product. $◀$

This example shows that, for out-of-order semigroup evaluation, it may be useful to remember the first and last positions of the overall word of semigroup elements. This is not helpful for monoids, intuitively because the first and last positions can always contain the neutral element. The class of semigroups whose evaluation only depends on the leftmost and rightmost elements is a well-studied variety called $\mathrm{𝐋𝐢}$ and defined by the equation $⟦x^{\omega }y{x}^{\omega }=x^{\omega }⟧$, or equivalently $\mathrm{𝐋𝐢}=⟦x^{\omega }y{z}^{\omega }=x^{\omega }{z}^{\omega }⟧$.

The main result which we show in this section is the following:

We prove this result in the rest of the section. We first show the first point (the upper bound), before showing the second point (the lower bound). We note that the second point only gives a lower bound, which is not tight relative to our linear space upper bound (Theorem 2.1); we come back to this issue in Section 5.

We first prove the upper bound for the semigroups in $\mathrm{𝐋𝐢}$ by relying on its equational description and a simple pumping argument.

Let $k=|S|$, store the first $k+1$ and last $k+1$ letters. At the end return the product in order of all the stored elements. This algorithm is in constant space. The correctness follows by using a pumping technique on the first and last $k+1$ elements to construct idempotent elements and then using the equation $\mathrm{𝐋𝐢}=⟦x^{\omega }y{z}^{\omega }=x^{\omega }{z}^{\omega }⟧$ to conclude that the product of the stored elements is equal to the entire product. $◀$

Together with the upper bound on commutative semigroups that follows from the immediate generalization to semigroups of Lemma 2.4, and thanks to the closure under semigroup operations by the analogue of Proposition 3.1 for semigroups, we deduce that semigroups in $\mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$ have $O(1)$ space out-of-order semigroup evaluation. This establishes the upper bound of Theorem 4.4.

We now show that all other semigroups require logarithmic space, which completes the proof of Theorem 4.4 by showing the second point.

For this, we first give an equational characterization of the variety $\mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$. This relates to the general study of semigroups of the form $𝐕\vee \mathrm{𝐋𝐢}$, with a general methodology to understand these varieties given in [15]. We will prove the equation $s^{\omega }xy{t}^{\omega }=s^{\omega }yx{t}^{\omega }$, and will in fact give an alternative characterization via three equations. Each of these equations will then be used to give a separate lower bound using fooling set constructions.

We can show the equivalence between points 2 and 3 simply by equation manipulation, so the key point is to show the equivalence of points 1 and 2. For the easy $1\to 2$ direction we see that the equations for $\mathrm{𝐋𝐢}$ and $\mathrm{𝐂𝐨𝐦}$ both imply the equation of point 2. For the $2\to 1$ direction, similarly to Lemma 3.11, taking a semigroup $S$ satisfying the equation, we define one congruence of $\mathrm{𝐋𝐢}$ and one congruence of $\mathrm{𝐂𝐨𝐦}$ and we show that their intersection refines the congruence defined by $S$. For this, we use pumping to construct idempotents in the common prefixes and suffixes (thanks to the $\mathrm{𝐋𝐢}$ congruence), then using the equation between the idempotents to argue that all letters can be reordered and that we can conclude simply from the $\mathrm{𝐂𝐨𝐦}$ congruence. $◀$

The lemma above gives an equational characterization of $\mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$ with the equation $s^{\omega }xy{t}^{\omega }=s^{\omega }yx{t}^{\omega }$, intuitively implying that everything commutes between two (possibly different) idempotents. However, to show the lower bound part of Theorem 4.4, we will use the three equations of the third point. Namely, for any semigroup not in $\mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$, we will see which equation among the three is violated, and use a different proof in each case.

We first notice that the case of a violation of the third equation $s^{\omega }x{s}^{\omega }y{s}^{\omega }=s^{\omega }y{s}^{\omega }x{s}^{\omega }$ in fact precisely corresponds to the case of a non-commutative semigroup, and the corresponding lower bound was already proven as Lemma 4.1. Hence, only the first and second equations remain. We give the construction for the first equation:

We invoke Lemma 2.2 using the following $(n-2,2n)$-fooling set for any $n>0$. For each pair of indices $i,j\in \{2,\mathrm{\dots },n-1\}$ define

Thus the out-of-order evaluation problem for $S$ has $\mathrm{\Omega }(\log (n))$ complexity. $◀$

We then give the construction for the second equation:

We invoke Lemma 2.2 using the following $(n-2,2n)$-fooling set for any $n>0$. For each pair of indices $i,j\in \{2,\mathrm{\dots },n-1\}$ define

Thus the out-of-order evaluation problem for $S$ has $\mathrm{\Omega }(\log (n))$ space complexity. $◀$

We can now conclude the proof of Theorem 4.4: by combining Lemma 4.6, Lemma 4.7, Lemma 4.9, and Lemma 4.1, we conclude that any semigroup $S\notin \mathrm{𝐋𝐢}\vee \mathrm{𝐂𝐨𝐦}$ must have $\mathrm{\Omega }(\log (n))$ space complexity.

We have illustrated that there are novel algorithms for the case of semigroups which did not exist in the case of monoids. Yet, the case of out-of-order evaluation for semigroups is still coarser than out-of-order membership problem for regular languages. For instance, we can show the following linear semigroup lower bound, which is in contrast to the $O(1)$ space upper bound for the corresponding language in Example 2.5.

The first example that we present is the language $L=a^{\ast }{b}^{\ast }{a}^{\ast }$. First note that the syntactic monoid of $L$ is not in $\mathrm{𝐅𝐋}\vee \mathrm{𝐂𝐨𝐦}$: intuitively, there is no $k>0$ for which we can solve out-of-order membership (or evaluation) by remembering the $k$ first and last occurrences of each letter along with commutative information. More precisely, the first and last $a$’s are uninformative, and the first and last $b$’s do not allow us to know whether there could be some $a$’s surrounded by two $b$’s. So, the out-of-order monoid evaluation problem for the syntactic monoid of $L$ has linear space complexity by Theorem 3.2. By contrast, we can show that out-of-order membership for $L$ can be done in logarithmic space, with an ad-hoc algorithm:

We memorize the minimal position $b_{\min }$ and maximal position $b_{\max }$ where a $b$ occurs, along with the number of $b$’s. A word belongs to the language precisely when the $b$’s form a contiguous interval, which amounts to verifying whether the number of $b$’s is equal to the difference between the minimal and maximal positions of $b$ (plus 1).

Now, for the lower bound, we construct the following $(n-1,2n)$-fooling set for any $n\in \mathbb{N}$. For any $1\le i\le n-1$, define $w_i≔{(a\mathrm{\_})}^i{(b\mathrm{\_})}^{n-i}$. Now, for any $i,j\in \{1,\mathrm{\dots },n-1\}$ with define $v_{ij}≔{(\mathrm{\_}a)}^j{(\mathrm{\_}b)}^{n-j}$. This ensures that $w_i\circ v_{ij}$ is in $a^{\ast }{(ba)}^{+}{b}^{+}$, i.e., it is not in $L$; whereas $w_j\circ v_{ij}$ is in $a^{\ast }{b}^{+}$, i.e., it is in $L$. By Lemma 2.2, the out-of-order membership problem for $a^{\ast }{b}^{\ast }{a}^{\ast }$ then has $\mathrm{\Omega }(\log (n))$ complexity. $◀$

Note that this algorithm does not work for the syntactic monoid of $a^{\ast }{b}^{\ast }{a}^{\ast }$, because we cannot count the neutral elements between $b_{\min }$ and $b_{\max }$, rendering the technique useless. The result generalizes to languages such as $a^{\ast }{b}^{\ast }{c}^{\ast }{b}^{\ast }{a}^{\ast }$, by maintaining the counts and minima and maxima of each letter and checking first that the $c$’s form a contiguous interval, and then that the $b$’s form a contiguous interval around the $c$’s (offsetting the count of the $b$’s by that of the $c$’s).

One can wonder whether the result also generalizes to languages of the form $a^{\ast }{b}^{\ast }{a}^{\ast }{b}^{\ast }{a}^{\ast }$. This is not immediate, because now we cannot easily identify the $a$’s in the middle interval, or the $b$’s in the left interval versus the right interval. However, it turns out that logarithmic space complexity can be shown using a more intricate approach (which also could have been used to show Proposition 5.1):