One block of quantifiers, read off an algebra

A language that can name a set found two exact descriptions of what logic can say about words. With quantifiers over sets of positions, a sentence defines exactly the languages a finite automaton recognises — Büchi’s theorem. With quantifiers over single positions only, first-order logic with the order of positions defines exactly the star-free languages, and a language is star-free exactly when its syntactic monoid is aperiodic — a theorem of Schützenberger, McNaughton and Papert. The boundary at three variables ended its account of the game with a debt from the same story: within first-order logic there is a hierarchy, counted by how many times a sentence alternates between “there exists” and “for all”, and deciding which level a given language sits at is known only at the lowest levels.

This essay computes the lowest. A sentence that uses only existential quantifiers, followed by a quantifier-free statement about letters and order, says that certain letters occur in a certain order: “there are positions $x < y < z$ carrying $a$, $b$, $a$”. Boolean combinations of such sentences — and, or, not — make up the first level of the hierarchy. Imre Simon proved in 1975 that a regular language is at this level exactly when its syntactic monoid has a property called J-triviality, an algebraic condition that can be checked mechanically. The figures check it on every language a small automaton recognises, and check Simon’s theorem from the other side as well.

Subwords, and what one quantifier block can say #

A scattered subword of a word is any sequence of its letters read in order, not necessarily adjacent: $aba$ is a subword of $abba$ and of $babbbab$, and not of $baab$. An existential sentence “there are positions $x_1 < x_2 < \cdots < x_k$ carrying the letters $u_1, \ldots, u_k$” holds in a word exactly when $u_1 \cdots u_k$ is one of its scattered subwords, and every existential sentence is equivalent to a finite disjunction of such statements. So the languages at the first level are exactly those in which membership depends only on which words of length at most $k$ occur as scattered subwords, for some $k$. Simon called them piecewise testable.

The hero figure shows the distinction that matters. Words containing $a$, $b$, $a$ in that order, with anything between, form a piecewise testable language: membership is decided by whether the single subword $aba$ occurs. Words containing $aba$ as a factor, three adjacent letters, are first-order definable — “there are $x$, $y$, $z$ with $y$ immediately after $x$ and $z$ immediately after $y$”, and “immediately after” needs a universal quantifier to say that nothing lies between — but not piecewise testable. The figure finds the reason concretely: $abab$ contains the factor $aba$ and $abba$ does not, yet both have the same scattered subwords of length up to two, $a$, $b$, $aa$, $ab$, $ba$ and $bb$. No statement about short subwords can tell them apart, and the same is true at every length for suitably longer pairs.

The syntactic monoid #

Simon’s test lives in the algebra of the language. Every regular language has a smallest automaton, and the ways that words can move the automaton’s states form a monoid: each word acts as a function from states to states, two words acting the same way are identified, and composing actions is the multiplication. This is the syntactic monoid, the algebraic fingerprint the earlier essay used to test for first-order definability. For the subword language it has seven elements, and for the factor language twelve.

A monoid is J-trivial when no two different elements generate the same two-sided ideal: if $s$ can be obtained from $t$ by multiplying on both sides and $t$ from $s$, then $s = t$. In words, an element can never be undone. For the subword language this is visible in the automaton: reading letters can only move it forward through the stages “nothing yet”, “seen $a$”, “seen $ab$”, “seen $aba$”, never back. For the factor language a $b$ after $ab$ sends the automaton back to the start, so the action “$ab$ then $b$” can be followed by actions that lead back to where “$ab$” alone led, and the monoid has elements that generate each other’s ideals. Simon’s theorem: a regular language is piecewise testable if and only if its syntactic monoid is J-trivial.

Both directions are worth having. One gives an algorithm — compute the monoid and test the ideals — that decides the first level of the hierarchy for any regular language, which is what the earlier essay’s open question was asking for in general. The other gives the reason the algebra is the right one: a piecewise testable language is a Boolean combination of subword conditions, each of which can only become true and never false as a word is read, and that monotonicity is J-triviality.

The seven actions of the subword automaton #

The monoid of the subword language can be listed by hand, and doing so shows what J-triviality looks like. The automaton has four states, 0 to 3, meaning “nothing yet”, “seen $a$”, “seen $ab$” and “seen $aba$”. A word acts on the states by moving each to where the automaton would be after reading the word from it. The empty word does nothing. The letter $a$ moves 0 to 1 and 2 to 3 and leaves 1 and 3 alone; $b$ moves 1 to 2 and leaves the rest. Then $ab$ sends 0 and 1 to 2 and 2 to 3; $ba$ sends 0 to 1 and 1 and 2 to 3; $bab$ sends 0 to 2 and 1 and 2 to 3; and $aba$ sends every state to 3, the action that ends everything. Every longer word acts like one of these — $abab$, for instance, also sends everything to 3 — so there are seven distinct actions in all, matching the figure.

Every action moves states forward or leaves them where they are, and that is the whole reason the monoid is J-trivial: if one action can be obtained from another by multiplying on both sides, it moves states at least as far, and if each can be obtained from the other they move them equally far, so they are the same action. The factor automaton breaks this, because reading $b$ in the state “seen $ab$” sends it back to the start: the actions “$ab$” and “$abb$” can each be extended into the other, so they generate the same ideal while acting differently on the states. Sixteen of five hundred and seventy-six met monoids and groups as multiplication tables of Latin squares; here the tables are the actions of words, and the property that matters is not associativity, which every monoid has, but whether any element can be reversed.

Every small language, sorted #

The census in the next figure enumerates every deterministic automaton over $\{a, b\}$ with at most four states, every choice of transitions and accepting states, minimises each one and puts it in a canonical form, and so counts each language once.

There are 57,068 such languages: two with one state, everything and nothing; 24 with two; 1,028 with three; and 56,014 whose smallest automaton has four states. Of them, 848 have J-trivial monoids and are piecewise testable; 3,250 more are aperiodic, first-order definable but needing an alternation of quantifiers; and the remaining 52,970 are not aperiodic at all, because they count something — the parity of the number of letters $a$, say — that no first-order sentence can express. The shares shift with size: among the two-state languages a quarter are piecewise testable, among the four-state ones fewer than one in seventy. Most languages a small automaton can recognise count modulo something, and the logic of a single quantifier block captures a small and shrinking corner of them. That is the opposite of the situation nearly always, or nearly never found for random graphs, where every first-order property is almost certainly true or almost certainly false: among small automata, first-order definable languages are themselves the rare case.

Simon’s theorem, checked from the other side #

The census classified languages by their monoids. The next figure checks the classification against the definition, by computing for each J-trivial language the length of subwords its membership actually depends on.

For every one of the 848 J-trivial languages there is such a $k$, and it is at most three: two languages need $k = 0$ (everything and nothing), fourteen need $k = 1$, 232 need $k = 2$ and 600 need $k = 3$. The check runs over every word of up to ten letters, 2,047 words, and for each language and each candidate $k$ looks for two words with the same subwords of length at most $k$ on opposite sides; for the J-trivial languages it finds none at the stated $k$. In the other direction, among the first-order languages with at most three states that are not J-trivial — 110 of them — every one shows two words with the same subwords up to length four on opposite sides, within ten letters. So on everything small enough to check exhaustively, the algebra and the definition agree completely.

A finite check cannot prove the theorem, and it has a particular blind spot: on words of bounded length, long subwords determine a word almost completely, so any language looks piecewise testable if $k$ is allowed to approach the word length. The checks therefore cap $k$ well below the length of the words used — three and four against ten — where the separation is meaningful.

Finitely many classes for each length #

Why piecewise testable languages are regular at all is itself a counting fact. For a fixed $k$, two words are equivalent when they have the same scattered subwords of length at most $k$, and there are only finitely many sets of short words, so only finitely many classes.

With $k = 1$ there are four classes, according to which of $a$ and $b$ occur, and every class is met by words of two letters. With $k = 2$ there are sixteen, all met by words of four letters. With $k = 3$ there are sixty-eight, all met by words of seven letters, and longer words never produce a new one. Each piecewise testable language is a union of classes, so it is recognised by an automaton that tracks the class, which is finite. The numbers 4, 16, 68 grow quickly with $k$, and this is the price of the first level’s simplicity: membership is easy to describe and the description can be long.

The classes are also the positions of an Ehrenfeucht–Fraïssé game restricted to existential moves. A game that decides what can be said played the full game, where a player may move in either structure; when the first player must always move in the same word, as an existential sentence’s quantifiers do, the second player can answer $k$ rounds exactly when every subword of length $k$ of that word is also a subword of the other. Two words in the same class are those where neither player can win a one-sided game of $k$ rounds starting from either side.

The algebra of one quantifier block is small #

The last figure compares the sizes of the syntactic monoids in the three classes, among the four-state languages.

The J-trivial monoids are the smallest, averaging 6.3 elements with at most ten; the other aperiodic monoids average 10.7, at most twenty; and monoids containing a group — the counting languages — average 44.5 and reach 176. J-triviality forces this: since no element can return to an earlier ideal, words can only push the automaton’s states forward in a fixed partial order, and few distinct actions are possible. A group, at the other extreme, lets words permute states freely, and the actions multiply. The syntactic monoid’s size is a rough measure of a language’s complexity, and the first level of the quantifier hierarchy is, measured this way, the simplest class of languages that is not trivial.

What the census cannot show #

The census is exhaustive for automata of up to four states and says nothing about larger ones, though Simon’s theorem covers all of them. Its checks against the definition are exhaustive only up to words of ten letters, and the separations they find for non-J-trivial languages are evidence that the theorem’s hard direction is working, not a proof of it. The figures also say nothing about the efficiency of the test: computing the syntactic monoid can take time exponential in the automaton’s size, since the monoid can be exponentially large, and later work found ways of testing J-triviality directly on the automaton, in polynomial time, without building the monoid.

The census is also restricted to two letters. Over larger alphabets every count grows, and the proportion of piecewise testable languages among all regular ones falls further; the structure of the classification is unchanged.

Where the hierarchy came from #

The hierarchy was first defined without logic. Janusz Brzozowski introduced the dot-depth of a star-free language in 1971, counting how many times concatenation and Boolean operations must alternate to build it from single letters. Ehrenfeucht–Fraïssé games entered when Wolfgang Thomas showed in 1982 that dot-depth is the number of quantifier alternations in a first-order sentence defining the language, with the order and the first and last positions available; Howard Straubing and Denis Thérien gave the variant without them. So the levels of the hierarchy can be read three ways: by alternations of quantifiers, by alternations of concatenation and Boolean operations, and by algebraic conditions on the syntactic monoid, of which J-triviality is the first.

The quantifier reading is the one these essays have followed. Six sentences from two quantifiers counted the meanings that two quantifiers of different kinds produce in different orders, and every row or one column showed that swapping a “for all” and a “there exists” changes what a sentence says. The alternation hierarchy is the systematic version: each new alternation lets a sentence say something its predecessors could not, and Brzozowski and Robert Knast proved in 1978 that the dot-depth hierarchy never collapses. Simon’s theorem was the first level at which the infinite hierarchy acquired an algorithm.

Still open: the levels above #

Simon’s theorem decides the first level of the hierarchy of quantifier alternations. The level above, sentences with an existential block followed by a universal block, was decided by Jean-Éric Pin and Pascal Weil and then by Thomas Place and Marc Zeitoun, who between 2014 and 2019 decided several further levels with new techniques based on separating languages rather than characterising them. Whether every level of the quantifier alternation hierarchy is decidable is open. The full first-order class is decidable by aperiodicity, and the levels below it are known to be strictly increasing — each alternation lets a sentence say more — but no general algorithm determines the least number of alternations a given star-free language needs.

The same question arises with the order replaced by the successor relation, the logic of a machine that carries one bit and of locally testable languages, where Brzozowski, Simon, McNaughton and Thérien found algebraic characterisations of the lowest levels, and where the higher levels are equally open.

Monotone reading #

The properties that a single block of existential quantifiers can state are exactly those that are decided once certain patterns have been seen, and never undone by what follows. That monotonicity has an algebraic shadow: a monoid in which no element can be undone, J-trivial. Simon’s theorem says the shadow is exact, and the census confirms it on every language a four-state automaton can recognise: 848 J-trivial languages, each decided by subwords of length at most three, and every other first-order language small enough to check showing two words that agree on their short subwords and disagree on membership. The factor $aba$ and the subword $aba$ differ by one word of quantifier — “immediately” — and that word is the difference between the first level of the hierarchy and the second.