Characterizing NC¹ with Typed Monoids

A semigroup $(S,\cdot )$ is a set $S$ equipped with an associative binary operation. We call a semigroup finite if $S$ is finite. Context permitting, we may refer to a semigroup $(S,\cdot )$ simply by its underlying set $S$.

A monoid $(M,\cdot )$ is a semigroup with a distinguished element $1_M\in M$ such that for all $m\in M$, $1_M\cdot m=m\cdot 1_M=m$. We call $1_M$ the identity or neutral element of $M$. A group $(G,\cdot )$ is a monoid such that for every $g\in G$, there exists an element $g^{-1}\in G$ such that $g\cdot g^{-1}=g^{-1}\cdot g=1$. We call $g^{-1}$ the inverse of $g$.

Note that $(\mathbb{Z},+)$ is a group, $(\mathbb{N},+)$ is a monoid but not a group and $({\mathbb{Z}}^{+},+)$ is a semigroup but not a monoid. In the first two cases, the identity element is $0$. When we refer to the monoids $\mathbb{Z}$ or $\mathbb{N}$ we assume that the operation referred to is standard addition.

For a semigroup $(S,\cdot )$, we say that a set $G\subseteq S$ generates $S$ if $S$ is equal to the closure of $G$ under $\cdot$; we denote this by $S={⟨G⟩}_{\cdot }$, or, simply, $⟨G⟩$ if the operation is clear from context, and call $G$ a generating set of $S$. We say that $S$ is finitely generated if there exists a finite generating set of $S$. All semigroups we consider are finitely generated. Note that ${\mathbb{Z}}^{+}$ is generated by $\{1\}$, $\mathbb{N}$ by $\{0,1\}$ and $\mathbb{Z}$ by $\{1,-1\}$.

We write $U_1$ for the monoid $(\{0,1\},\cdot )$ where the binary operation is the standard multiplication. Note that $1$ is the identity element here. For any set $S$, we denote by $S^{+}$ the set of non-empty finite strings over $S$ and by $S^{\ast }$ the set of all finite strings over $S$. Equipped with the concatenation operation on strings, which we denote by either $\circ$ or simply juxtaposition, $S^{\ast }$ is a monoid and $S^{+}$ is a semigroup but not a monoid. We refer to these as the free monoid and free semigroup over $S$, respectively. Note that $S$ is a set of generators for $S^{+}$ and $S\cup \{ϵ\}$ is a set of generators for $S^{\ast }$.

A monoid homomorphism from a monoid $(S,{\cdot }_S)$ to a monoid $(T,{\cdot }_T)$ is a function $h:S\to T$ such that for all $s_1,s_2\in S$, $h(s_1{\cdot }_S{s}_2)=h(s_1){\cdot }_{T}h(s_2)$ and $h(1_S)=1_T$. A congruence on a monoid $(M,\cdot )$ is an equivalence relation $\sim$ on $M$ such that for all $a,b,c,d\in M$, if $a\sim b$ and $c\sim d$, then $a\cdot c\sim b\cdot d$. We denote by $M/\sim$ the set of equivalence classes of $\sim$ on $M$. We denote by ${[a]}_{\sim }$, or simply $[a]$, the equivalence class of $a\in M$ under $\sim$. Any congruence $\sim$ gives rise to the quotient monoid of $M$ by $\sim$, namely the monoid $(M/\sim ,\star )$ where for $[a],[b]\in M/\sim$, $[a]\star [b]=[a\cdot b]$. The map $\eta :M\to M/\sim$ defined by $\eta (a)=[a]$ is then a homomorphism, known as the canonical homomorphism of $M$ onto $M/\sim$.

Here we recall the definition of syntactic congruences and syntactic monoids.

For a language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ over an alphabet $\mathrm{\Sigma }$, we define the syntactic congruence of $L$ as the equivalence relation ${\sim }_L$ on ${\mathrm{\Sigma }}^{\ast }$ such that for all $x,y\in {\mathrm{\Sigma }}^{\ast }$, $x{\sim }_{L}y$ if, and only if, for all $w,v\in {\mathrm{\Sigma }}^{\ast }$, $wxv\in L$ if, and only if, $wyv\in L$.

It is easily seen that this relation is a congruence on the free monoid ${\mathrm{\Sigma }}^{\ast }$. The quotient monoid ${\mathrm{\Sigma }}^{\ast }/{\sim }_L$ is known as the syntactic monoid of $L$. More generally, we say that a monoid $M$ recognizes a language $L$ if there is a homomorphism $h:{\mathrm{\Sigma }}^{\ast }\to M$ and a set $A\subseteq M$ such that $L=h^{-1}(A)$. It is easily seen that the syntactic monoid of $L$ recognizes $L$. A language is regular if, and only if, its syntactic monoid is finite [19].

We assume familiarity with the basic syntax and semantics of first-order logic. In this paper, the logic is always interpreted in finite relational structures. We generally denote structures by Fraktur letters, $𝔄$, $𝔅$, etc., and the corresponding universe of the structure is denoted $|𝔄|$, $|𝔅|$, etc. We are almost exclusively interested in strings over a finite alphabet. Thus, fix an alphabet $\mathrm{\Sigma }$. A $\mathrm{\Sigma }$-string is then a structure $𝔄$ whose universe $|𝔄|$ is linearly ordered by a binary relation and which interprets a set of unary relation symbols ${(R_{\sigma })}_{\sigma \in \mathrm{\Sigma }}$ such that for each element $a\in |𝔄|$ there is a unique $\sigma \in \mathrm{\Sigma }$ such that $a$ is in the interpretation of $R_{\sigma }$.

More generally, let $\tau$ be any relational vocabulary consisting of a binary relation symbol and unary relation symbols $R_1,\mathrm{\dots },R_k$. We can associate with any $\tau$-structure in which is a linear order a string over an alphabet of size $2^k$ as formalized in the following definition.

For example, say $\tau =\{R_1,R_2,R_3\}$ and where , $R_1^{𝔄}=\{1,3\}$, $R_2^{𝔄}=\{2,4\}$, and $R_3^{𝔄}=\{1,2,3\}$. Then, the string $w_{𝔄}=(101)(011)(101)(010)$.

Using the above, we can associate a language with any isomorphism-closed class of structures over the vocabulary $\tau$. We formalize this definition for future use.

It is worth noting that the above operations are not inverses, in the sense that it is not the case that $S_{L_{𝒜}}=𝒜$. This is because while $𝒜$ is a class of structures using $k$ unary relation symbols, $S_{L_{𝒜}}$ is in a vocabulary using $2^k$ unary symbols.

As the elements of a string $𝔄$ are linearly ordered, we can identify them with an initial segment $\{1,\mathrm{\dots },n\}$ of the positive integers. In other words, we treat a string with universe $\{1,\mathrm{\dots },n\}$ and the standard order on these elements as a canonical representative of its isomorphism class. In addition to the order predicate, we may allow other numerical predicates to appear in formulas of our logics. These are predicates whose meaning is completely determined by the size $n$ of the structure and the ordering of its elements. In particular, we have ternary predicates $+$ and $\times$ for the partial addition and multiplication functions.

An insight due to Lindström allows us to define a quantifier from any isomorphism-closed class of structures (see [10]). We adopt the terminology of Ebbginhaus and Flum [9, Chapter 12] and provide a brief overview now. Consider a relational vocabulary $\tau =\{R_1,\mathrm{\dots },R_l\}$, where for each $i$, $R_i$ is a relation symbol of arity $r_i$. For any vocabulary $\sigma$ and positive integer $d$, an interpretation of $\tau$ in $\sigma$ of dimension $d$ is a tuple of formulas $I=({\varphi }_1({\overline{x}}_1),\mathrm{\dots },{\varphi }_l({\overline{x}}_l))$ of vocabulary $\sigma$ where ${\varphi }_i$ is associated with a tuple ${\overline{x}}_i$ of variables of length $|{\overline{x}}_i|=d{r}_i$. Suppose we are given a $\sigma$-structure $𝔄$ and an assignment $\alpha$ that takes variables to elements of $𝔄$. Then let ${\varphi }_i^{𝔄,\alpha }$ denote the relation of arity $d{r}_i$ consisting of the set of tuples $\{\overline{a}\in {|𝔄|}^{d{r}_i}\mid 𝔄\vDash {\varphi }_i[\alpha [{\overline{x}}_i/\overline{a}]]\}$. Then, the interpretation $I$ defines a map that takes a $\sigma$-structure $𝔄$, along with an assignment $\alpha$ to the $\tau$-structure $I(𝔄,\alpha )$ with universe ${|𝔄|}^d$ where the interpretation of $R_i$ is the set ${\varphi }_i^{𝔄,\alpha }$, seen as a relation of arity $r_i$ on ${|𝔄|}^d$.

Given a class of $\tau$-structures $Q$ and any positive integer $d$, we have a quantifier $Q_d$. In a logic with $Q_d$, we can form formulas of the form

whenever $I=({\varphi }_1({\overline{x}}_1),\mathrm{\dots },{\varphi }_l({\overline{x}}_l))$ is an interpretation of dimension $d$. In this formula, occurrences in the subformula ${\varphi }_i$ of variables among $x_i$ are bound. The semantics of this quantifier are given by the rule that $Q_d{\overline{x}}_1\mathrm{\cdots }{\overline{x}}_l({\varphi }_1,\mathrm{\dots },{\varphi }_l)$ is true in a structure $𝔄$ under some assignment $\alpha$ of values to the free variables if the $\tau$-structure $I(𝔄,\alpha )$ is in $Q$. We can understand $Q_d$ as the $d$th vectorization of the quantifier $Q$ (see [9, Def. 12.1.6]). When $d=1$, we may omit the subscript. A quantifier of the form $Q_1$ is called unary.

The standard first-order quantifiers: $\exists$ and $\forall$ can be seen as special cases of Lindström quantifiers in a vocabulary with one unary relation $U$. The existential quantifier consists of all structures $(A,U)$ where $U\subseteq A$ is non-empty and the universal quantifier consists of all structures $(A,U)$ where $U=A$.

We are particularly interested in interpretations $I$ where both $\sigma$ and $\tau$ are vocabularies of strings. These are also known in the literature as string-to-string transducers. (See [4] for an example of how transducers may have many representations.) Therefore, $I$ must define an interpretation of not only each $R_i\in \tau$ (using the formula ${\varphi }_i$) but also a $\sigma$-formula defining the linear order on the universe of the $\tau$-structure $I(𝔄,\alpha )$. We are particularly interested in the case where the order defined is the lexicographic order on $d$-tuples of $|𝔄|$ induced by the order in $𝔄$. This order is easily defined by a (quantifier-free) first-order formula, and we often omit it from the description of $I$.

When we consider interpretations that define a linear order other than the lexicographic order, we explicitly include the formula defining the order and thus the formula is , where the interpretation is of dimension $d$ and so $|\overline{x}|=2d$ and $|\overline{y}|=d$.

Finally, we now introduce some notation we use in the rest of the paper for various logics formed by combining particular choices of quantifiers and numerical predicates.

When $𝔔$ is just a singleton $\{Q\}$, we sometimes denote $(𝔔)[𝔑]$ by $(Q)[𝔑]$ or $(Q_1)[𝔑]$ to emphasise that it is the unary quantifier. We also write $\overline{Q}$ for the collection of all vectorizations of the quantifier $Q$. We use similar notation for the sets of numerical predicates. We use $ℒ((𝔔)[𝔑])$ to denote the languages expressible by the logic $(𝔔)[𝔑]$.

All the logics we consider are substitution closed in the sense of [10]. This means in particular that if a quantifier $Q$ is definable in a logic $(𝔔)[𝔑]$, then extending the logic with the quantifier $Q$ does not add to its expressive power. This is because we can replace occurrences of the quantifier $Q$ by its definition, with a suitable substitution of the interpretation for the relation symbols. Hence, if $Q$ is definable in $(𝔔)[𝔑]$, then $ℒ((𝔔)[𝔑])=ℒ((𝔔\cup \{Q\})[𝔑])$.

A remark is due on our notation for numerical predicates. All structures we consider are ordered, including those defining the quantifiers. Thus the order predicate is implicitly present in the collection of numerical predicates $𝔑$ and is used (implicitly) to define the interpretations to a quantifier. We sometimes write $(𝔔)[\mathrm{\varnothing }]$ to indicate a logic in which this is the only use of the order that is allowed; by our choice of notation, the order symbol then does not appear explicitly in the syntax of the formulas.

The definition of multiplication quantifier has its origin in Barrington, Immerman, and Straubing [1, Section 5] where they were referred to as monoid quantifiers; the authors proved that the languages in NC¹ are exactly those expressible by first-order logic with quantifiers whose truth-value is determined via multiplication in a finite monoid. The notion was extended by Lautemann et al. [16] to include quantifiers for the word problem over more general algebras with a binary operation. Multiplication quantifiers over a finite monoid $M$ can be understood as generalized quantifiers corresponding to languages recognized by $M$, and here we define them as such. We then see how this definition matches that of multiplication quantifiers à la Barrington et al. [1, 14].

Fix a monoid $M$, a set $B\subseteq M$, and a positive integer $k$. Let ${\mathrm{\Sigma }}_k$ denote the set ${\{0,1\}}^k$ which we think of as an alphabet of size $2^k$, and fix a function $\gamma :{\mathrm{\Sigma }}_k\to M$. We extend $\gamma$ to strings in ${\mathrm{\Sigma }}_k^{\ast }$ inductively in the standard way: $\gamma (ϵ)=1_M$ and $\gamma (wa)=\gamma (w)\gamma (a)$. Note that $\gamma$ is a monoid homomorphism. Together these define a language

We can now define a multiplication quantifier. In the following, ${𝒮}_L$ denotes the class of $\tau$ structures associated with a language $L$ in the sense of Definition 2.

Recall that $U_1$ denotes the two-element monoid $\{0,1\}$ with standard multiplication. Then, it is easily seen that ${\mathrm{\Gamma }}_{1,\gamma }^{U_1,0}$, where $\gamma :\{0,1\}\to U_1$ such that $\gamma (0)=1$ and $\gamma (1)=0$, is the standard existential quantifier. The universal quantifier can be defined similarly.

Another way of describing the semantics of the multiplication quantifier (which relates it directly to the form described in Barrington et al. [1]) is as follows. For a monoid $M$, a set $B\subseteq M$, a positive integer $k$ and a function $\gamma :{\{0,1\}}^k\to M$, consider the formula

where $|\overline{x}|=2d$ and $|\overline{y}|=d$; and defines an interpretation of dimension $d$ from some vocabulary $\tau$ to a vocabulary with binary relation $⊏$ and $k$ unary relations. Then, for a $\tau$-structure $𝔄$ and assignment $\alpha$, we have that

if, and only if, defines a linear order $⊏$ on the $d$-tuples of $𝔄$ and

Here, multiplication is in the monoid $M$ and, since multiplication is not necessarily commutative, the order of $d$-tuples is specified to be the one given by $⊏$, which is defined by .

As stated above, when $𝔄$ is itself ordered and the order $⊏$ is the lexicographic order on $d$-tuples, we simply omit the formula .

The study of the expressive power of multiplication quantifiers has generally been in relation to logics which restrict the application of multiplication quantifiers to interpretations with a lexicographic order. For this purpose, we introduce a piece of notation: we write $\text{lex-}(𝔔\cup {\mathrm{\Gamma }}^M)[𝔑]$ to mean the fragment of the logic $(𝔔\cup {\mathrm{\Gamma }}^M)[𝔑]$ in which all applications of quantifiers from ${\mathrm{\Gamma }}^M$ are to interpretations with a lexicographic order. Likewise, we write $\text{fo-}(𝔔\cup {\mathrm{\Gamma }}^M)[𝔑]$ to mean the fragment of the logic $(𝔔\cup {\mathrm{\Gamma }}^M)[𝔑]$ in which all applications of quantifiers from ${\mathrm{\Gamma }}^M$ are to interpretations in which the order is defined by a formula of .

From [1, Corollary 9.1], we know that ${\mathrm{NC}}^1$ is characterized by $(\text{FO})[+,\times ]$ equipped with finite multiplication quantifiers over lexicographic orders:

In the absence of the arithmetic predicates for addition and multiplication, the logic of multiplication quantifiers over finite monoids only allows us to define regular languages. Specifically, Barrington et al. [1, Theorem 11.1] established that the regular languages are characterized by the logic using such quantifiers with only unary interpretations.

Later, Lautemann et al. [16, Theorem 5.1] showed that allowing interpretations of higher dimension to the quantifiers does not increase the expressive power when order is the only numerical predicate.

In Theorem 14 we show that this is true even in the presence of other numerical predicates and, therefore, ${\mathrm{\Gamma }}^{\mathrm{fin}}$ can be replaced by ${\mathrm{\Gamma }}_1^{\mathrm{fin}}$ even in Theorem 6. For our intended application, we need this technical result only in the case when the quantifier in ${\mathrm{\Gamma }}^{\mathrm{fin}}$ is applied to interpretations where the order defined is lexicographic, and we give the proof in this special case. However, the result holds more generally for cases in which the quantifier in ${\mathrm{\Gamma }}^{\mathrm{fin}}$ is applied to interpretations where the order is defined by a -formula, and this may be of independent interest so we state the more general Theorem 19.

Our results build on the theory of typed monoids as developed in the work of Krebs and collaborators [2, 3, 14, 13, 6]. We recapitulate the main definitions in Appendix A for ease of reference. In particular, we need the notions of division of typed monoids (Definition 29), syntactic typed monoid (Definition 32), and language recognition with typed monoids (Definition 27). Here, we turn to discussing the relationship between the expressive power of logics with multiplication quantifiers and typed monoids. A formal association is defined through the definition below.

We also state the formal connection between the languages expressible in a logic with a collection of quantifiers and the corresponding class of typed monoids which recognizes the exact same language. For this we need the notion of the ordered strong block product of a pair of monoids. The definition is technical and can be found in [13] and is also reproduced in the linked full version of this paper. For a set of typed monoids $T$, we denote by its closure under ordered strong block products.

From [13, Theorem 4.14], we then get the following relationship between logics and algebras:³³3The theorem in [13] is actually more general as it allows for more predicates than just order; however, for our purposes, order alone suffices.

Recall that the subscript in ${𝔔}_1$ means we are restricting the logic to only use the quantifiers in $𝔔$ on unary interpretations and the prefix “lex-” means that the quantifiers are only applied to interpretations with a lexicographic order.