Measuring Power of Locally Testable Languages
Ryoma Sin’ya
Akita University
ryoma@math.akita-u.ac.jp

Abstract. A language L is said to be C-measurable, where C is a classof languages, if there is an infinite sequence of languages in C that converges to L. In this paper we investigate the measuring power of LT
the class of all locally testable languages. Although each locally testablelanguage only can check some local property (prefix, suffix, and infix ofsome bounded length), it is shown that many non-locally-testable languages are LT-measurable. In particular, we show that the measuring
power of locally testable languages coincides with the measuring powerof unambiguous polynomials. We also examine the measuring power ofsome fragments of unambiguous polynomials.

1

Introduction

A language L is called star-free if it can be represented as a finite combination of Boolean operations and concatenation of finite languages, and L is called
locally testable if it is a finite Boolean combination of languages of the formuA∗ , A∗ v and A∗ wA∗ . After the celebrated Schützenberger’s theorem giving an
algebraic characterisation [18] and McNaughton–Papert theorem giving a logicalcharacterisation [10] of star-free languages, both algebraic and logical counterparts of many fragments of star-free languages are deeply well-investigated: seea survey [6] or [11] for example. In particular, McNaughton [9], Zalcstein [24],and Brzozowski–Simon [4] showed that it is decidable whether a given regular
language is locally testable by giving an algebraic counterpart. Although thedefinition of locally testable languages is quite simple, this result is non-trivial
and a proof relies on a deep algebraic decomposition theory.
In this paper, we shed new light on the fragments of star-free languages byusing measurability which is a measure theoretic notion on formal languages.
C-measurability for a class C of languages is introduced by [21] and it was used
for classifying non-regular languages by using regular languages. A language L
is said to be C-measurable if there is an infinite sequence of languages in C
that converges to L. Roughly speaking, L is C-measurable means that it canbe approximated by a language in C with arbitrary high precision: the notionof “precision” is formally defined by the density of formal languages. Hence
that a language L is not REG-measurable, where REG is the class of all regular
languages, means that L has a complex shape so that it can not be approximatedby regular languages. While the membership problem for a given language L
and a class C asks the existence of single language K ∈ C such that L = K,the C-measurability asks the existence of an infinite sequence of languages inC that converges to L. In this sense, measurability is much more difficult thanthe membership problem and its analysis is a challenging task. For example, theauthor [22] showed that, for the class SF of all star-free languages, the class of
all SF-measurable regular languages strictly contains SF but does not containsome regular languages. However, the decidability of SF-measurability is still
unknown.
Instead of the class of all regular languages or star-free languages, in thispaper we consider LT-measurability where LT is the class of all locally testablelanguages and also consider measuring power of three other fragments of starfree languages: the class UPol of all unambiguous polynomials, the class PT of allpiecewise testable languages and the class AT of all alphabet testable languages.
The main results of this paper are briefly summarised as follows.
(1) LT-measurability and UPol-measurability are equivalent (Theorem 6 andTheorem 7).
(2) AT- and PT-measurability are strictly weaker than LT-measurability anddecidable for regular languages (Theorem 8, Theorem 9–11).
The result (1) is the first example of two incomparable subclasses of regular
languages with the same measuring power. The result (2) (PT-measurability, inparticular) is the first non-trivial examples of subclasses of regular languages
with decidable measurability. Historically, locally testable languages [10] and unambiguous polynomials [17] are originally introduced with two different motivations: “locality” versus “unambiguity”. But interestingly, they have thesame measuring power.
The structure of this paper is as follows. Section 2 provides preliminaries including density, measurability and definitions of fragments of star-free languages.
The measuring power of LT, UPol and AT, PT are investigated in Section 3 andSection 4, respectively. A summary of all results and future work are describedin Section 5.

2

Preliminaries

This section provides the precise definitions of density, measurability and local
varieties of regular languages. REGA denotes the family of all regular languages
over an alphabet A. We assume that the reader has a standard knowledge of
automata theory including the concept of syntactic monoids (cf. [8]).
2.1

Density of formal languages

For a set X, we denote by #(X) the cardinality of X. We denote by N and Z theset of natural numbers including 0 and the set of integers, respectively. For analphabet A, we denote the set of all words (all non-empty words, respectively)
over A by A∗ (A+ , respectively). We write |w| for the length of w and A≤n forthe set of all words of length less than or equal to n. For a word w ∈ A∗ and aletter a ∈ A, |w|a denotes the number of occurrences of a in w. We denote byalph(w) = {a | |w|a > 0} the set of all letters contained in w. A word v is said tobe a subword of a word w if w = xvy for some x, y ∈ A∗ . For a language L ⊆ A∗ ,we denote by L = A∗ \ L the complement of L. A language L is said to be dense
if L ∩ A∗ wA∗ 6= ∅ holds for any w ∈ A∗ . L is not dense means L ∩ A∗ wA∗ = ∅for some word w by definition, and such word w is called a forbidden word of L.
Definition 1 (cf. [2]). The density δA (L) of L ⊆ A∗ is defined asn−1
1 X # L ∩ Ak
δA (L) = limn→∞ n#(Ak )
k=0

if its exists, otherwise we write δA (L) = ⊥. L is called null if δA (L) = 0, andconversely L is called co-null if δA (L) = 1.
Example 1. It is known that every regular language has a rational density (cf. [16])and it is computable. Here we explain two examples of (co-)null languages.
(1) For each word w, the language A∗ wA∗ , the set of all words that contain w
as a subword, is of density 1 (co-null). This fact is sometimes called infinitemonkey theorem. A language L having a forbidden word w is always null:
this means A∗ wA∗ ⊆ L and δA (A∗ wA∗ ) ≤ δA (L) which implies δA (L) = 1
by infinite monkey theorem.
(2) The semi-Dyck language D = {ε, ab, aabb, abab, aaabbb, . . .} over
 A = {a, b}
is dense but null. This follows from the fact that # D ∩ A2n equals then-th Catalan number whose asymptotic formula is Θ(4n /n3/2 ).
As explained above, “dense” does not imply “not null”. But these two notions
are equivalent for regular languages as the following theorem says. We denote
by ZOA the family of all null or co-null regular languages over A (ZO stands for“zero-one”).
Theorem 1 (cf. [16]). A regular language L is not null if and only if L is dense.
2.2

Measurability of formal languages

The notion of “measurability” on formal languages is defined by a standard
measure theoretic approach as follows.
Definition 2 ([21]). Let CA be a family of languages over A. For a language
L ⊆ A∗ , we define its CA -inner-density µC (L) and CA -outer-density µCA (L)Aover A asµC (L) = sup{δA (K) | K ⊆ L, K ∈ CA , δA (K) 6= ⊥} andAµCA (L) = inf{δA (K) | L ⊆ K, K ∈ CA , δA (K) 6= ⊥}, respectively.
A language L is said to be CA -measurable if µC (L) = µCA (L) holds. We sayAthat an infinite sequence (Ln )n of languages over A converges to L from inner(from outer, respectively) if Ln ⊆ L (Ln ⊇ L, respectively) for each n andlimn→∞ δA (Ln ) = δA (L).

Example 2 ([21]). The semi-Dyck language D = {ε, ab, aabb, abab, aaabbb, . . .}over A = {a, b} is REG-measurable. We notice that there is no regular language
L such that δA (L) = 0 and D ⊆ L, since any null regular language has aforbidden word but D has no forbidden word. Hence we should construct an
infinite sequence (Lk )k of different regular languages that converges to D fromouter. This can be done by letting Lk = {w ∈ A∗ | |w|a = |w|b mod k}. Clearly,
D ⊆ Lk holds and it can be shown that δA (Lk ) = 1/k holds. Hence δA (Lk ) tends
to zero if k tends to infinity. We will see this type of languages Lk again in thenext section.
For a family CA of languages over A, we define its Carathéodory extension
and regular extension as ExtA (CA ) = {L ⊆ A∗ | L is CA -measurable} andRExtA (CA ) = ExtA (CA ) ∩ REGA , respectively. We say that “CA has a stronger
measuring power than DA ” if ExtA (CA ) ⊇ ExtA (DA ) holds.
Theorem 2 ([22]). Let CA ⊆ REGA be a family of regular languages overA. Then L ∈ REGA is CA -measurable if and only if L satisfies the following
Carathéodory’s condition:∀X ⊆ A∗µCA (X) = µCA (X ∩ L) + µCA (X ∩ L).

Moreover, this is equivalent to µCA (L) + µCA (L) = 1 (the case X = A∗ in theabove condition).
2.3

Fragments of Star-Free Languages

In this paper we examine measuring power of several subclasses of star-freelanguages equipping rich closure properties. For a family CA of languages overA, we denote by BCA the Boolean closure of CA . Then the class LTA of all locallytestable languages can be defined as LTA = B{wA∗ , A∗ w, A∗ wA∗ | w ∈ A∗ }. A
family of regular languages over A is called local variety [1] over A if it is closed
under Boolean operations and left-and-right quotients. The reason why we focus
on this type of families is that, the notion of measurability is well-behaved on
Boolean operations and quotients as the following theorem says.
Theorem 3 ([22]). ExtA is a closure operator, i.e., it satisfies the following∗
three properties for each C ⊆ D ⊆ 2A : (extensive) C ⊆ ExtA (C), (monotone)
ExtA (C) ⊆ ExtA (D), and (idempotent) ExtA (ExtA (C)) = ExtA (C). Moreover,
RExtA is a closure operator over the class of all local varieties of regular languages over A, i.e., CA -measurability is preserved under Boolean operations andquotients for any local variety CA .
Example 3. By Theorem 1, for any regular language L in ZOA , L or its complement has a forbidden word, which implies ∅ ⊆ L ⊆ A∗ wA∗ or A∗ wA∗ ⊆ L ⊆ A∗ .
This fact and infinite monkey theorem implies that ZOA ⊆ RExtA (B{A∗ wA∗ |w ∈ A∗ }) holds. On the other hand, B{A∗ wA∗ | w ∈ A∗ } ⊆ ZOA holds because
ZOA forms a local variety (cf. [20]). Moreover, it was shown that RExtA (ZOA ) =ZOA in [22]. By combining these facts with Theorem 3 we have the following
chain of inclusion: ZOA ⊆ RExtA (B{A∗ wA∗ | w ∈ A∗ }) ⊆ RExtA (ZOA ) = ZOA
where the second inclusion ⊆ follows from the monotonicity of RExtA .
The corresponding notion of a family of finite monoids is called local pseudovariety [1], and there is a natural one-to-one correspondence between the classof all local varieties and the class of all local pseudovarieties [7]. The class SFA
of all star-free languages over A forms a local variety and its corresponding local
pseudovariety is the class of all aperiodic monoids [18]. Thanks to Theorem 3,
the regular extension RExtA (SFA ) of star-free languages is also a local variety.
The following theorem says that RExtA extends SFA non-trivially, while it does
not for ZOA .
Theorem 4 ([22]). SFA ( RExtA (SFA ) ( REGA if #(A) ≥ 2.
The class LTA of all locally testable languages over A is also a local variety.
We use this algebraic characterisation of LTA in the next section, hence we givea precise definition here. An element e of a monoid M is called idempotent if
e2 = e holds. For each idempotent e ∈ M , eM e is a submonoid of M with
the identity e and it is called local monoid in M (cf. [8]). A monoid M is said
to be locally idempotent and commutative if, for each idempotent e ∈ M , thelocal monoid eM e only contains idempotents and the multiplication on eM e iscommutative (x, y ∈ eM e ⇒ x2 = x and xy = yx). The characterisation given
in [9,24,4] says that L is locally testable if and only if its syntactic semigroup islocally idempotent and commutative (see the full version [23] for more details).
We end this section by giving precise definitions of three additional subclasses of star-free languages. We denote by ATA the Boolean combination of
languages of the form B ∗ where B ⊆ A (AT stands for “alphabet testable”,
cf. [15]). This class also can be represented as ATA = B{A∗ aA∗ | a ∈ A} andhence ATA ( LTA . ATA forms a (finite) local variety, and its corresponding local pseudovariety is idempotent and commutative monoids (cf. [6]). Clearly, thedensity of every language in ATA is either zero or one, thus we have ATA ⊆ ZOA .
A language L is called monomial if it is of the form A∗0 a1 A∗1 a2 A∗2 · · · A∗n−1 an A∗nwhere each ai ∈ A, Ai ⊆ A and n ≥ 0. A monomial defined above is said tobe simple if Ai = A for each i. For w = a1 a2 · · · an we denote by Lw the simple monomial A∗ a1 A∗ a2 A∗ · · · A∗ an A∗ . A language is called piecewise testable
if it can be represented as a finite Boolean combination of simple monomials.
The class PTA of all piecewise testable languages over A forms a local variety. The corresponding local pseudovariety of PTA is the class of all J -trivial
monoids [19]. A monomial L = A∗0 a1 A∗1 · · · an A∗n is unambiguous if for all w ∈ L
there exists exactly one factorisation w = w0 a1 w1 · · · an wn where each i satisfies wi ∈ A∗i . A language is an unambiguous polynomial if it is a finite disjoint
union of unambiguous monomials. The family UPolA of all unambiguous polynomials over A forms a local variety [17]. In particular, the complement of an
unambiguous polynomial is also an unambiguous polynomial. This fact plays a
key role in the next section. By definition we have the following chain of inclusion ATA ( PTA ( UPolA ( SFA and every inclusion is strict. We also

notice that PTA (UPolA , respectively) and LTA are incomparable. For example,A∗ abaA∗ ∈ LTA \ PTA (because the syntactic monoid of A∗ abaA∗ is not J trivial) and Laba = A∗ aA∗ bA∗ aA∗ ∈ PTA \ LTA (because the syntactic monoidof Laba is not locally idempotent). Every J -trivial finite monoid has a zero element, and a language whose syntactic monoid has a zero is of density zero orone (cf. [20]), thus we have PTA ( ZOA .

3

Measuring Power of Locally Testable Languages

In this section we examine the measuring power of locally testable languages:
what kind of languages are LTA -measurable and what are not? First we show
there are “many” LTA -measurable languages.
Proposition 1. For any language L ⊆ A∗ , A∗ LA∗ is LTA -measurable.
Proof. If L = ∅ then A∗ LA∗ = ∅ is in LTA . If L 6= ∅, we can choose w ∈ L
and the ideal language A∗ wA∗ ⊆ A∗ LA∗ is co-null by infinite monkey theorem.
tuHence µLT (A∗ LA∗ ) = 1 i.e., A∗ LA∗ ∈ ExtA (LTA ).
A

If A contains two distinct letters a and b, then the subword relation x v y (⇔“x is a subword of y”) has an infinite antichain in A∗ , e.g., {abn a | n ≥ 0}.
Two different subsets L1 and L2 of this infinite antichain produce two different
languages A∗ L1 A∗ and A∗ L2 A∗ . Hence the above theorem implies there are uncountably many LTA -measurable languages. In fact, in [22], a stronger statement
was shown as follows1 .
Theorem 5 ([22]). For any real number α ∈ [0, 1] there is a LTA -measurable
language with density α if #(A) ≥ 2.
Next we show that languages with modulo counting, which were used forthe convergent sequence to the semi-Dyck language in Example 2, are LTA immeasurable.
Proposition 2. The language Lk = {w ∈ A∗ | |w|a = |w|b mod k} over A ={a, b} is LTA -immeasurable for any k ≥ 2.
Proof. We show that any non-null locally testable language contains some words
in Lk and Lk . Suppose L ∈ LTA is non-null (δA (L) > 0) and let ML andη : A∗ → ML be its syntactic monoid and morphism, and let S = η(L).
Let K ⊆ ML be the minimal ideal of ML . We can easily obtain δA (η −1 (K)) =1 as a corollary of the infinite monkey theorem. Hence the assumption δA (L) > 0
implies that there is some t ∈ K ∩ S.
Let e be an idempotent in ML (since ML is finite, there is at least one
idempotent) and we ∈ η −1 (e) be a word of e. Without loss of generality, we
1[22] considered REGA -measurability instead of LTA -measurability, but the convergent sequence constructed in the proof of Theorem 5 is actually a sequence of locallytestable languages

can assume |we |a ≥ |we |b . Let n = |we |a − |we |b ≥ 0, u = we b2n awe and v =we b2n+1 we . By construction, |u|a − |u|b = 1 and |v|b − |v|a = 1 holds. By theminimality of K, there exist x and y such that η(xuvy) = t. Because ML is
locally idempotent, η(u), η(v) ∈ eML e are both idempotent. This fact implies
that, for any i, j ≥ 1, xui v j y is in L because
η(xui v j y) = η(x)η(u)i η(v)j η(y) = η(x)η(u)η(v)η(y) = η(xuvy) = t
holds. Thus for any m ∈ Z, we can choose i, j ≥ 1 such that |xui v j y|a −|xui v j y|b = m. Hence L contains words in Lk and Lk simultaneously, whichtuimplies µLT (Lk ) = 0 and µLTA (Lk ) = 1, i.e., Lk is LTA -immeasurable.
A

The next theorem says that LTA has a stronger measuring power than UPolA .
Theorem 6. ExtA (LTA ) ⊇ ExtA (UPolA ) for any A.
We use the following simple lemma for proving this theorem.
Lemma 1. The concatenation LK of two null regular languages L and K is
also null.
Proof. By Theorem 1, L and K have some forbidden words u, v ∈ A∗ , i.e.,
L ⊆ A∗ uA∗ and K ⊆ A∗ vA∗ . Then uv is a forbidden word of LK as follows. For
any word w ∈ A∗ uvA∗ and any factorisation w = xy, either x contains u or ycontains v as a subword. This means x ∈/ L or y ∈/ K, thus w is not in LK. t
u
One might think that the above lemma is also true for non-regular languages,
but it is false. Consider a language Lsq = {w ∈ A∗ | |w| = n2 for some n ≥ 0}.
This language Lsq is null, because almost every natural number is not square.
However, by Lagrange’s four square theorem stating that every natural number
can be represented as the sum of four integer squares, we have L4sq = A∗ which
is clearly co-null.
Proof (of Theorem 6). By the monotonicity and idempotency of ExtA (Theorem 3), it is enough to show UPolA ⊆ ExtA (LTA ): this implies ExtA (UPolA ) ⊆Uk
ExtA (ExtA (LTA )) = ExtA (LTA ). Let L = i=1 Mi be an unambiguous polynomial where each Mi is an unambiguous monomial and ] represents the disjoint
union.
We show that, for each monomial Mi , µLT (Mi ) = δA (Mi ) holds, i.e., weA
can construct a convergent sequence (Li,j )j of locally testable languages to Mi
from inner : Li,j ⊆ Mi for each j and limj→∞ δA (Li,j ) = δA (Mi ). If Mi is null,then clearly we can take Li,j = ∅ for each j. Hence we assume Mi is not null.
In this case, Mi should be of the form Mi = A∗0 a1 A∗1 · · · A∗n−1 an A∗n and (F)there is a unique ` satisfying A` = A. We show (F). Notice that at least one `satisfies A` = A, because if not every A∗` and every a` is clearly null and hence
these concatenation Mi is also null by Lemma 1. Suppose there are two ` < `0with A` = A`0 = A. In this case the word (a1 · · · an )2 ∈ Mi has two different
factorisations:
ε , a`0 +1 , . . . , an , ε)(ε, a1 , . . . , a` , a`+1 · · · an a1 · · · a` , a`+1 , . . . , a`0 , |{z}
|
{z
}
∗
A `0

A∗
`

(ε, a1 , . . . , a` , |{z}ε , a`+1 , . . . , a`0 , a`0 +1 · · · an a1 · · · a`0 , a`0 +1 , . . . , an , ε)
{z
}
|
∗
A`

A∗
`0

This contradicts with the unambiguity of Mi . Hence (F) is true and we can write
Mi = P A∗ S where P = A∗0 a1 A∗1 · · · A∗`−1 a` and S = a`+1 A∗`+1 · · · A∗n−1 an A∗n .
Because Mi is unambiguous, for each word w ∈ Mi , there is a unique factorisationw = xyz where x ∈ P , y ∈ A∗ and z ∈ S, respectively. Hence, for any n ≥ 0, we
have

U
∗
n
xA
z
∩
A
#
∗
n
(x,z)∈Un#({(x, y, z) ∈ P × A × S | |xyz| = n})#(Mi ∩ A )==#(An )#(An )#(An )
P∗nX(x,z)∈Un #(xA z ∩ A )
−|xz|
=
=
#(A)
(1)
#(An )(x,z)∈Un
holds where Un = (x, z) ∈ P × S | |x| + |z| ≤ n . Because the sequence(#(Mi ∩ An ) /#(An ))n is bounded above by 1 and non-decreasing, the limit of(1) exists, say limn→∞ (1) = α. In general, if a sequence converges to some value,then its average also converges to theSsame value. Hence we have δA (Mi ) = α.
For each j ∈ N, the language Li,j = (x,z)∈Uj xA∗ z is locally testable, because(i) for each x, z ∈ A∗ , xA∗ z = (xA∗ ∩ A∗ z) \ {w ∈ A∗ | |w| < |x| + |z|}is locally testable, and (ii) Uj is finite. Moreover, Li,j ⊆ Mi for each j andP−|xz|δA (Li,j ) =. Hence limj→∞ δA (Li,j ) = α = δA (Mi ), i.e.,(x,z)∈Uj #(A)µLT (Mi ) = δA (Mi ). This fact implies that µLT (L) = δA (L) because we haveAA
the following equality:
!
k
k
k
X
]
X
µLT (Mi ) =Mi =δA (Mi ) = δA (L).
µLT (L) = µLT
A

A

A

i=1

i=1

i=1

Next we show µLT (L) = δA (L). Notice that the complement of L is also anA
Uk 0unambiguous polynomial since UPolA is a local variety. Thus L = i=1 Mi0 holds
for some unambiguous monomials Mi0 . Hence we can conclude that µLT (L) =A

δA (L) = 1 − δA (L) which implies µLT (L) + µLT (L) = 1. Because LTA is closedAA

under complementation, we have µLT (K) = 1 − µLTA (K) for any K. ThusAµLTA (L) + µLTA (L) = 1, i.e., L is LTA -measurable by Theorem 2.

tu

Next we show the reverse inclusion of Theorem 6. This direction is more easy.

Theorem 7. ExtA (UPolA ) ⊇ ExtA (LTA ) for any A.
Proof. By the monotonicity and idempotency of ExtA (Theorem 3), this is equivalent to LTA ⊆ ExtA (UPolA ). Moreover, UPolA -measurability is preserved under Boolean operations by Theorem 3, we only have to show that wA∗ , A∗ w andA∗ wA∗ are all UPolA -measurable for each w ∈ A∗ . Let w = a1 · · · an where eachai ∈ A.
First we show wA∗ ∈ ExtA (UPolA ). This is easy because the language wA∗ =∗∅ a1 ∅∗ a2 ∅∗ · · · ∅∗ an A∗ itself is actually an unambiguous polynomial. Similarly,
we also have A∗ w ∈ UPolA .
Next we show A∗ wA∗ ∈ ExtA (UPolA ). This language is not in UPolA in
general. For example, A∗ abA∗ is not an unambiguous polynomial if A = {a, b, c}(cf. [6]). Since the case w = ε is trivial, we assume w = a1 · · · an where ai ∈ A andn ≥ 1. Define Wk = (Ak \Kk )wA∗ where Kk = {u ∈ Ak | ua1 · · · an−1 ∈ A∗ wA∗ }for each k ≥ 0. Intuitively, Wk is the set of all words in which w firstly appears
at the position k + 1 as
U a subword. Wk is in UPolA for each k, because it canbe written as Wk = v∈(Ak \Kk ) vwA∗ , where each vwA∗ is an unambiguous
polynomial as shown above, which means that this disjoint finite union Wk is
also an unambiguous polynomial. Clearly, Wi ∩ Wj = ∅ and δA (Wi ) > 0 for each
U
U
n
∗
∗
i 6= j, thus we have k≥0 Wk = A wA and hence limn→∞ δAk≥0 Wk = 1
i.e., µUPol (A∗ wA∗ ) = 1. Thus A∗ wA∗ ∈ ExtA (UPolA ).

tuACombining Theorem 6 and Theorem 7, we have the following equivalence.
Corollary 1. ExtA (LTA ) = ExtA (UPolA ) for each A.
We showed that LTA has a certain measuring power, but yet we do not knowwhether LTA -measurability on REGA is decidable or not. We only know that
RExtA (LTA ) forms a local variety thanks to Theorem 3.

4

Measuring Power of Alphabet and Piecewise Testable
Languages

For any alphabet A, ATA is a finite family of regular languages, hence we candecide, for a given regular language L ⊆ A∗ , whether L is ATA -measurable ornot: enumerate every pair (L1 , L2 ) of languages in ATA and check L1 ⊆ L ⊆ L2and δA (L1 ) = δA (L2 ) = δA (L) holds. But the next theorem gives us a more
simpler way to check ATA -measurability than this naı̈ve approach.
Theoremlanguage L ⊆ A∗ is ATA -measurable if and only if L
T 8. A ∗co-null∗contains a∈A A aA .
T
T
∗
∗
∗
∗
Proof. Clearly, a∈A
Thus
T A aA∗ ∈∗ ATA and δA ( a∈A A aA ) T= 1 holds.
any language L ⊇ a∈A A aA is ATA -measurable. If L 6⊇ a∈A A∗ aA∗ , thenanyof L in ATA is null,every language in ATA not containing
T subset
S because
∗
∗
∗
A
aA
is
a
subsetofB
andhence it is clearly null.
t
u
a∈A
B(A

We notice that the above theorem also gives a characterisation of null ATA measurable languages: because ATA is closed under complementation, L is ATA measurable if and only if L is ATA -measurable by TheoremT 2. Hence a nulllanguage L ⊆ A∗ is ATA -measurable if and only if L contains a∈A A∗ aA∗ . The
latter condition is equivalent to the following: alph(w) 6= A for any w ∈ L.
Next we give a simple different characterisation of PT-measurability. The
following lemma can be considered as a specialised version of Theorem 1 (aregular language is co-null if and only if it contains an ideal language A∗ wA∗ )to piecewise testable languages. Notice that A∗ wA∗ ⊆ Lw always holds hence
Lw is more “larger” than A∗ wA∗ .
Lemma 2. A piecewise testable language L ∈ PTA is co-null if and only if it
contains a simple monomial.
Proof. (⇐:) this is trivial: every simple monomial Lw is co-null by infinite monkey theorem.
(⇒:) Let L ∈ PTA be a co-null piecewise testable language. By definition of
PTA , L can be written as a finite Boolean combination of simple monomials,
hence it can be written as a disjunctive normal form L = I1 ∪ · · · ∪ In wheren ≥ 1 and each Ii is the intersection of some simple monomials or complementsof simple monomials. δA (L) = 1 implies that, at least one Ii is the intersection ofsome simple monomials (otherwise δA (L) = 0), say Ii = Lw1 ∩ · · · ∩ Lwk . Hence
we can conclude that L contains a simple monomial Lw1 ···wk ⊆ Ii ⊆ L.
tu
Theorem 9. A co-null language L ⊆ A∗ is PTA -measurable if and only if Lw ⊆L holds for some w ∈ A∗ .
Proof. (⇐): trivial.
(⇒): L is PTA -measurable means there is a convergent sequence (Lk )k of piecewise testable languages to L from inner. This means that, for some i ≥ 0,
δA (Lj ) = 1 holds for any j ≥ i because the density of each Lk is either zero orone. By Lemma 2, Lj contains a simple monomial Lwj for each j ≥ i. Hence
Lwi ⊆ Li ⊆ L, in particular.
tu
We notice that the above theorem also gives a characterisation of null PTA measurable languages: because PTA is closed under complementation, L is PTA measurable if and only if L is PTA -measurable by Theorem 2. By using Lemma 2,
we can also show that the measuring power of PTA is strictly weaker than ZOA
as follows.
Theorem 10. PTA ( RExtA (PTA ) ( ZOA if #(A) ≥ 2.
Proof. PTA ( RExtA (PTA ) follows from the fact that any regular language L ⊆B ∗ is in RExtA (PTA ) for B ( A. Also, we have RExtA (PTA ) ⊆ RExtA (ZOA ) =ZOA because PTA ⊆ ZOA holds. Hence it is enough to show RExtA (PTA ) 6=
ZOA .
We show A∗ wA∗ 6∈ ExtA (PTA ) for any w ∈ A∗ with |w| ≥ 3. Let L ∈ PTA
be a co-null piecewise testable language. By Lemma 2, there exists some word usuch that Lu ⊆ L. We now show that there exits v ∈ Lu such that v ∈/ A∗ wA∗∗∗
which implies L 6⊆ A wA . Let u = a1 · · · a` where ai ∈ A for each i, andlet w = w0 b1 b2 b3 where w0 ∈ A∗ , bj ∈ A for each j. If ` ≤ 2, it is clear thatLu 3 a1 · · · a` 6∈ A∗ wA∗ because |w| ≥ 3. Hence we consider the case ` ≥ 3. We
perform case analysis of #(A).
(Case #(A) ≥ 3): Let v1 = a1 . We choose vi in order from i = 2 to ` as follows:(1) if |v1 v2 · · · vi−1 | ≥ |w| and the suffix of v1 v2 · · · vi−1 ai of length |w| equals w(ai = b3 in this case), then put vi = aai where a ∈ (A \ {b2 , b3 }). (2) otherwise,
put vi = ai .
(Case #(A) = 2): This case is a bit more involved. Let A = {a, b} and let
v1 = ab. We choose vi in order from i = 2 to ` as follows: (1) if b1 b2 b3 ∈
{aaa, aab, abb, baa, bba, bbb}, then put vi = ab. (2) if b1 b2 b3 ∈ {aba, bab}, then put
vi = baab. Observe that the each suffix of vi of length 2 is ab, hence v1 · · · v` ∈ Lu0
for any u0 ∈ A` . Also, one can easily observe that no subword of vi vi+1 equals
to b1 b2 b3 for each 1 ≤ i ≤ ` − 1.
In both cases, by construction, no subword of v = v1 · · · v` equals to w andv ∈ Lu . Thus only a null piecewise testable language can be a subset of A∗ wA∗ ,/ ExtA (PTA ).
tuhence µPT (A∗ wA∗ ) = 0, i.e., A∗ wA∗ ∈A

Finally, we give an algebraic characterisation of PTA -measurability based on
Theorem 9. We notice that the syntactic monoid of every co-null regular language
has the zero element 0 (cf. [20]). We use Green’s J -relation =J and <J on a
monoid M defined by x =J y ⇔ M xM = M yM and x <J y ⇔ M xM ( M yM ,respectively (cf. [8]).
Theorem 11. A co-null regular language L ⊆ A∗ is PTA -measurable if andonly if (♦) for every x ∈ M \ {0} there is a letter a ∈ A such that x0 η(a) <J x0
for every x0 =J x, where η : A∗ → M and M is the syntactic morphism andmonoid of L, respectively.
Proof. It is clear that 0 is the minimum element of M with respect to <J . Also,
we have 0 ∈ η(L) by infinite monkey theorem. We write [x] for the J -class of x.
(⇐): Assume (♦). Let |M/ =J | = n and let [x1 ], . . . , [xn ] be a sequence of J classes of M such that (1) for every x ∈ M there is i such that x ∈ [xi ], and (2)for every i < j either xi >J xj or xi and xj are incomparable with respect to<J . By the assumption, for each J -class [xi ] where i 6= n (xn = 0 by definition),
there is a letter ai ∈ A such that x0 η(ai ) <J x0 for every x0 ∈ [xi ]. Define w =a1 · · · an−1 . By construction, it is clear that, for every w0 , w1 , . . . , wn−1 ∈ A∗ ,we have η(w0 a1 w1 a2 · · · wn−2 an−1 wn−1 ) = 0. Hence η(Lw ) = {0}, that is, we
obtain Lw ⊆ L. This means that L is PTA -measurable by Theorem 9.
(⇒): Assume the contrary of (♦). For any w = a1 · · · ak ∈ A∗ , we show that
Lw 6⊆ L holds. This implies that L is PTA -immeasurable by Theorem 9. By theassumption, there is y ∈ M \ {0} such that, for each letter ai , yi η(ai ) =J yi forsome yi ∈ [y]. yi η(ai ) =J yi =J y means that there is a pair (xi , zi ) such thatxi yi η(ai )zi = y. Also, for each yi ∈ [y], there is a pair (x0i , zi0 ) such that x0i yzi0 = yi .
For each i, let ui ∈ η −1 (xi ), vi ∈ η −1 (yi ), wi ∈ η −1 (zi ) and u0i ∈ η −1 (x0i ), wi0 ∈η −1 (zi0 ). Define t1 = u1 v1 a1 w1 and ti = ui u0i ti−1 wi0 ai wi for each 2 ≤ i ≤ k. By

Language

AlgebraLogic

MeasurabilitySFaperiodicFO

SF ( RExtA (SF) ( REG [22]LT

locally idempotent
and commutative

UPol

DA

FO2

PT

J -trivial

BΣ1

AT

idempotent
and commutative

FO1

ExtA (LT) = ExtA (UPol)PT ( RExtA (PT) ( ZO
L is PT-measurable iff L or L
contains a simple monomial
AT ( RExtA (AT) ( RExtA (PT)
L is AT-measurable
iff L or L
T
contains a∈A A∗ aA∗

Table 1. Correspondence of language-algebra-logic and summary of our results.

straightforward induction, we can show that η(ti ) = y holds for every 1 ≤ i ≤ k.
It also clear that tk ∈ Lw . Because y 6= 0, there is some x, z ∈ M such thatxyz ∈/ η(L) (if not y = 0 holds by the definition of the syntactic monoid of L).
This means that Lw 3 wx tk wz ∈/ L where wx ∈ η −1 (x), wz ∈ η −1 (z). Hence weobtain Lw 6⊆ L.
tu
Because the syntactic monoid of every regular language is finite, the condition(♦) is decidable.
Corollary 2. PTA -measurability is decidable for REGA .

5

Summary and Future WorkFor simplicity, in this section we only consider alphabets with two more letters,
and omit the subscript A for denoting local varieties. Table 1 shows algebraic andlogical counterparts of local varieties we considered (left) and a summary of ourresults (right). Here FOn stands for first-order logic with n-variables and BΣ1is the Boolean closure of existential first-order logic. The hierarchy of languages
is strictly decreasing top down excluding that LT and UPol (PT, respectively)
are incomparable. All algebraic and logical counterparts in Table 1 are nicely
described in a survey [6], with the sole exception LT [9,24,4].
Our future work are two kinds.
(1) Prove or disprove ExtA (LT) ( ExtA (SF).
(2) Prove or disprove the decidability of LT-measurability.
To show the decidability, perhaps we can use some known techniques related
to locally testable languages, for example, the so-called separation problem for alanguage class C: for a given pair of regular languages (L1 , L2 ), is there a language
L in C such that L1 ⊆ L and L ∩ L2 = ∅ (L “separates” L1 and L2 )? It is known

that the separation problem for PT, LT, and SF are all decidable [12,13,14].
Theorem 8 and Theorem 9 says that, AT-measurability and PT-measurability
does not rely on the existence of an infinite convergent sequence, but relies on
the existence of a single language ∩a∈A A∗ aA∗ and Lw as a subset, respectively.
But from Theorem 5, we can observe that, the situation of LT-measurability
is essentially different: LT-measurability heavily relies on the existence of an
infinite sequence of different locally testable languages. Because the density of
every regular language is rational (cf. [16]), for each LTA -measurable language
L with an irrational density, there is no single pair of regular languages (L1 , L2 )such that L1 ⊆ L ⊆ L2 and δA (L1 ) = δA (L2 ) = δA (L).
Between SF and LT, there is a fine-grained infinite hierarchy called the dotdepth hierarchy originally introduced by Cohen and Brzozowski [5] in 1970. Fora family C of languages, we denote by M C = {L1 · · · Lk | k ≥ 1, L1 , . . . , Lk ∈C} ∪ {{ε}} the monoid closure of C. The dot-depth hierarchy starts with thefamily B0 of all finite or co-finite languages, and continues as Bi+1 = BM Bi foreach i ≥ 0. Brzozowski and Knast [3] showed that this infinite
S hierarchy is strict:
Bi ( Bi+1 for each i ≥ 0. By definition, we have SF = i≥0 Bi , and actually,
we also have B0 ( LT ( B1 because each of wA∗ , A∗ w and A∗ wA∗ is obtainedby concatenating a finite language {w} and a co-finite language A∗ . Although
the dot-depth hierarchy was introduced in a half-century before and much ink
has been spent on it, the decidability of the membership problem for Bi is open
for i ≥ 3 and the research on this topic is still active: see a survey [11] or a
recent progress given by Place and Zeitoun [15] that shows the decidability ofthe separation problem for B2 , which implies the decidability of membership of
B2 . The equation ExtA (LT) = ExtA (SF) means that the dot-depth hierarchycollapses via ExtA . But if not, it might be interesting to consider the new hierarchy B0 = ExtA (B0 ) ( ExtA (B1 ) ⊆ ExtA (B2 ) ⊆ · · · ⊆ ExtA (SF).
Acknowledgements: I am grateful to my colleague Y. Yamaguchi (Osaka University) and Y. Nakamura (Tokyo Tech) for useful discussions. I also thank toanonymous reviewers for many valuable comments. This work was supported by
JSPS KAKENHI Grant Number JP19K14582 and JST ACT-X Grant Number
JPMJAX210B, Japan.

References
1. Adámek, J., Milius, S., Myers, R.S.R., Urbat, H.: Generalized eilenberg theorem I:
Local varieties of languages. In: Foundations of Software Science and Computation
Structures. pp. 366–380 (2014)
2. Berstel, J., Perrin, D.: Theory of codes, Pure and Applied Mathematics, vol. 117.
Academic Press Inc. (1985)
3. Brzozowski, J., Knast, R.: The dot-depth hierarchy of star-free languages is infinite.
Journal of Computer System Sciences 16, 37–55 (1978)
4. Brzozowski, J., Simon, I.: Characterizations of locally testable events. vol. 4, pp.
243–271 (1973)
5. Cohen, R.S., Brzozowski, J.: Dot-depth of star-free events. Journal of Computer
System Sciences 5, 1–16 (1971)

6. Diekert, V., Gastin, P., Kufleitner, M.: A survey on small fragments of first-orderlogic over finite words. Int. J. Found. Comput. Sci. 19(3), 513–548 (2008)
7. Gehrke, M., Grigorieff, S., Pin, J.: Duality and equational theory of regular languages. In: Automata, Languages and Programming. pp. 246–257 (2008)
8. Lawson, M.V.: Finite Automata. Chapman and Hall/CRC (2004)
9. McNaughton, R.: Algebraic decision procedures for local testability. Mathematicalsystems theory 8, 60–76 (1974)
10. McNaughton, R., Papert, S.: Coutner-Free Automata. The MIT Press (1971)
11. Pin, J.: The dot-depth hierarchy, 45 years later. In: The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski. pp. 177–202 (2017)12. Place, T., van Rooijen, L., Zeitoun, M.: Separating Regular Languages by Locally
Testable and Locally Threshold Testable Languages. In: IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science. pp.
363–375 (2013)
13. Place, T., van Rooijen, L., Zeitoun, M.: Separating regular languages by piecewise
testable and unambiguous languages. In: Mathematical Foundations of Computer
Science 2013. pp. 729–740 (2013)
14. Place, T., Zeitoun, M.: Separating regular languages with first-order logic. Log.
Methods Comput. Sci. 12(1) (2016)15. Place, T., Zeitoun, M.: Separation for dot-depth two. Logical Methods in Computer
Science 17 (Sep 2021)
16. Salomaa, A., Soittola, M.: Automata Theoretic Aspects of Formal Power Series.
Springer-Verlag New York, Inc., Secaucus, NJ, USA (1978)
17. Schützenberger, M.: Sur le produit de concaténation non ambigu. Semigroup Forum13, 47–75 (1976)
18. Schützenberger, M.P.: On finite monoids having only trivial subgroups. Information
and Control 8(2), 190–194 (1965)
19. Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages.
pp. 214–222 (1975)
20. Sin’ya, R.: An automata theoretic approach to the zero-one law for regular languages. In: Games, Automata, Logics and Formal Verification. pp. 172–185 (2015)21. Sin’ya, R.: Asymptotic approximation by regular languages. In: Current Trends in
Theory and Practice of Computer Science. pp. 74–88 (2021)
22. Sin’ya, R.: Carathéodory extensions of subclasses of regular languages. In: Developments in Language Theory. pp. 355–367 (2021)
23. Sin’ya, R.: Measuring power of locally testable languages (full version) (2022),
http://www.math.akita-u.ac.jp/~ryoma/misc/LTmeasure_full.pdf
24. Zalcstein, Y.: Locally testable languages. Journal of Computer and System Sciences
6(2), 151–167 (1972)