Measuring Power ofGeneralised Definite 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 GD
of the class of all generalised definite languages. Although each generalised definite language only can check some local property (prefix andsuffix of some bounded length), it is shown that many non-generaliseddefinite languages are GD-measurable. Further, we show that it is decidable whether a given regular language is GD-measurable or not.

1

Introduction

C-measurability for a class C of languages is introduced by [14] 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 C-measurable (C-immeasurable) means that L has acomplex shape so that it can not be approximated by languages in C. While
the membership problem for a given language L and a class C just asks whether
L ∈ C, the C-measurability asks the existence of an infinite sequence of languages
in C 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 [15] 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 for regular
languages is still unknown. Only for some very restricted subclasses C of starfree languages, the decidability of C-measurability is known [16]. A language L
is called locally testable [5,9,18] if it is a finite Boolean combination of languagesof the form uA∗ , A∗ v and A∗ wA∗ . Although the definition of local testability isvery simple, it was shown in [16] that many non-locally-testable languages are
LT-measurable, where LT is the class of all locally testable languages, and any
unambiguous polynomial (language definable by the first-order logic with two
variables) is LT-measurable. However, the decidability of LT-measurability for
regular languages was left open in [16].

In this paper, as a continuation research of [16], we examine the measuring
power of languages defined by definiteness, which is a natural restriction of
the notion of local testability. A language L is called definite (reverse definite,
respectively) [3] if it is a finite Boolean combination of languages of the formA∗ u (uA∗ , respectively). Also, L is called generalised definite [7] if it is a finite
Boolean combination of languages of the form uA∗ and A∗ v. We consider GDmeasurability and also consider D-measurability and RD-measurability where
D, RD and GD is the class of all definite, reverse definite and generalised definite
languages. The main results of this paper are two folds. We show:(1) A simple automata theoretic and algebraic characterisation of RD-measurability(Theorem 1 and Theorem 3).
(2) The equivalence of the GD-measurability and the LT-measurability (Proposition 1) and a decidable characterisation of GD-measurability (Theorem 4).
This decidability result answers a question posed in [16].
The structure of this paper is as follows. Section 2 provides preliminaries
including density, measurability and definitions of fragments of locally testablelanguages. An automata theoretic characterisation of RD-measurability is given
in Section 3, and a decidable characterisation of GD-measurability is given in
Section 4, respectively. Related and future work are described in 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.1Languages and automata

For an alphabet 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 andAn for the set of all words of length n. For a word w ∈ A∗ and a letter a ∈ A,
|w|a denotes the number of occurrences of a in w. We denote by wr = ak · · · a1
the reverse of w = a1 · · · ak , and denote by Lr = {wr | w ∈ L} the reverse of thelanguage L. A word v is said to be a factor of a word w if w = xvy for somex, 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.
A deterministic automaton A over A is a quadruple A = (Q, ·, q0 , F ) where Q
is a finite set of states, · : Q × A → Q is a transition function, q0 ∈ Q is an initialand F ⊆ Q is a set of final states. The language recognised by A is denoted by
L(A) = {w ∈ A∗ | q0 · w ∈ F }. For a set of states Q0 ⊆ Q and a word w, we write
Q0 · w for the set of transition states from Q0 by w: Q0 · w = {q · w | q ∈ Q0 }.

The automaton A is called accessible if for every state p ∈ Q there is a word
w such that q0 · w = p. In this paper, we only consider accessible deterministic
automata. Q0 is called strongly connected if for every p, q ∈ Q0 , there is someword w such that p · w = q. We say that Q0 is a sink if it is strongly connected
and there is no outgoing transition from Q0 , i.e., Q0 · w ⊆ Q0 for any w.
2.2

Locally testable and definite languages

For a family CA of languages over A, we denote by BCA the finite Boolean closureof CA . The class LTA of all locally testable languages over A can be defined as
LTA = B{wA∗ , A∗ w, A∗ wA∗ | w ∈ A∗ }.
The class DA , RDA and GDA of all definite, reverse definite [3] and generalised
definite [7] languages over A are defined as follows:
DA = B{A∗ w | w ∈ A∗ },RDA = B{wA∗ | w ∈ A∗ },GDA = B{A w, wA | w ∈ A }.
∗∗∗Hence these classes are proper subclasses of locally testable languages.
Remark 1 (cf. [5]). In [3,7] definite languages are originally defined as follows. A
language L is called:– definite if and only if L = E ∪ A∗ F for some finite sets E, F ⊆ A∗ .
– reverse definite if and only if L = E ∪ F A∗ S
for some finite sets E, F ⊆ A∗ .
– generalised definite if and only if L = E ∪ i∈I Fi A∗ Gi for some finite sets
E and Fi , Gi ⊆ A∗ for all i ∈ I, where I is a finite index set.
∗
For any word
combinaS w ∈ A , ∗the singleton {w} can be written∗ as the Boolean∗tion wA ∩ a∈A waA , hence any finite subset F ⊆ A is in B{wA∗ | w ∈ A∗ }.
Conversely, for any w, the complement wA∗ can be written in the form of areverse definite language: {u ∈ A∗ | |u| < |w|} ∪ (A|w| \ {w})A∗ . Hence, these
original definitions can be modified by using the finite Boolean closure as above.

2.3

Density and measurability of formal languages

For a set X, we denote by #(X) the cardinality of X. We denote by N the setof natural numbers including 0.
Definition 1 (cf. [2]). The density δA (L) of L ⊆ A∗ is defined asn−1

1 X # L ∩ Ak
n→∞ n#(Ak )δA (L) = lim

k=0

if it exists, otherwise we write δA (L) = ⊥. The language L is called null if
δA (L) = 0, and dually, L is called co-null if δA (L) = 1.

Example 1. It is known that every regular language has a rational density (cf. [11])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 factor, is of density one (co-null). This fact follows from the so-called
the infinite monkey theorem (this is also called as “Borges’s theorem”, cf. [6,p.61, Note I.35]): take any word w. A random word of length n contains w
as a factor with probability tending to 1 as n → ∞.
A language L having a forbidden word w is always null: having a forbidden
word w means A∗ wA∗ ⊆ L hence we have δA (A∗ wA∗ ) ≤ δA (L), which
implies δA (L) = 1 by the infinite monkey theorem.
(2) The set of all palindromes Lpal = {w ∈ A∗ | w = wr } over A = {a, b} isdense but null. This follows from the fact that #(Lpal ∩ An ) equals to 2dn/2e
and 2dn/2e /2n < 2(1−n/2) tends to zero if n tends to infinity.
We list some basic properties of the density as follows.
Lemma 1. Let K, L ⊆ A∗ with δA (K) = α, δA (L) = β. Then we have:(1) α ≤ β if K ⊆ L. (2) δA (L \ K) = β − α if K ⊆ L. (3) δA (K) = 1 − α.
(4) δA (K ∪ L) ≤ α + β if δA (K ∪ L) 6= ⊥. (5) δA (K ∪ L) = α + β if K ∩ L = ∅.
−|u|(6) δA (uL) = δA (Lu) = δA (L) · #(A)for each u ∈ A∗ .
For more properties of δA , see Chapter 13 of [2].
The notion of “measurability” on formal languages is defined by a standard
measure theoretic approach as follows.
Definition 2 ([14]). 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).
We give some examples of LTA -(im)measurable languages from [14,16].
Example 2. (1) The set of all palindromes Lpal = {w ∈ A∗ | w = wr } is LTA measurable. The sequence of locally testable languages Lk = {wA∗ wr | |w| =k} converges to Lpal from outer if k tends to infinity (see [14] for the detail). The density of Lpal is zero as stated in Example 1, hence the constantsequence of the empty language trivially converges to Lpal from inner.
(2) For any real number α ∈ [0, 1], there is an LTA -measurable language L whose
density is α. See [15] for the detailed construction.
(3) The language Mk = {w ∈ {a, b}∗ | |w|a = |w|b mod k} is LT-immeasurable
for any k ≥ 2. See [16] or Section 4.1 for the proof.

For a family CA of languages over A, we denote by ExtA (CA ) (RExtA (CA ),respectively) the class of all CA -measurable languages (CA -measurable regular
languages, respectively) over A. A family of regular languages over A is called a
local variety [1] over A if it is closed under Boolean operations and left-and-rightquotients.
Lemma 2 ([15]). 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 .
The following lemma is useful and will be used in Section 3 and Section 4.
Lemma 3. Let A = (Q, ·, q0 , F ) be a deterministic automaton, Q1 , · · · , Qk be
Sk
its all sink components and let Q0 = Q \ i=1 Qi . Then the language P 0 = {w ∈A∗ | q0 · w ∈ Q0 } is of density zero, Pi = {w ∈ A∗ | q0 · w ∈ Qi } satisfies
Pi = Pi A∗ and has a non-zero density for each i.
Proof. The condition Pi = Pi A∗ is clear because Qi is a sink for each i: Qi · w ⊆Qi holds for every w. For each i, Pi is non-empty because A is accessible (allautomata in this paper are accessible as stated in Section 2.1). Let w be a−|w|word in Pi . By Lemma 1, we have δA (Pi ) ≥ δA (wA∗ ) = #(A)> 0, i.e.,
Pi has a non-zero density. Now we show that the density of P 0 is zero. Let
Q0 = {q0 , q1 , · · · , qn }. For every state qi in Q0 , there exists some word wqi suchthat qi · wqi is in some sink component. Because every qi in Q0 is not in any sinkcomponent, qi is not reachable from the state qi · wqi , i.e.(qi · wqi ) · w ∈/ Q0 forevery w. Define u0 = wq0 and ui = wqi ·vi−1 if qi · vi−1 ∈ Q0 and ui = ε otherwisefor each i ∈ {1, · · · , n} where vi−1 is the word of the form u0 · · · ui−1 . By theconstruction, for every qi in Q0 , we have qi · u0 · · · un ∈/ Q0 . This means thatu0 · · · un is a forbidden word of P 0 and hence P 0 is of density zero by the infinitemonkey theorem.
tu
For simplicity, here after we fix an alphabet A and omit the subscript A for
denoting local varieties.

3

Simple Characterisation of RD-Measurability

The next theorem gives a simple automata theoretic characterisation of RDmeasurability.
Theorem 1. For a minimal deterministic automaton A, the followings are equivalent:(1) Every sink component of A is a singleton.
(2) L(A) is RD-measurable.

Proof. Let L = L(A), Q1 , · · · , Qk be all sink components of A = (Q, ·, q0 , F ) andSk
let Q0 = Q \ i=1 Qi . For each i ∈ {1, · · · , k}, define Pi = {w ∈ A∗ | q0 · w ∈ Qi }and define P 0 = {w ∈ A∗ | q0 · w ∈ Q0 }. Clearly, P1 , · · · , Pk and P 0 form thepartition of A∗ , and we have δA (P 0 ) = 0 by Lemma 3.
Proof of (1) ⇒ (2): Because each Qi is a singleton, Pi is contained in L if thestate in Qi belongs to F and Pi is contained in L otherwise. Define
M=[{Pi | Qi ⊆ F }

and

M0 =

[

{Pi | Qi ⊆ Q \ F }.

By the definition and Lemma 3 , we have M = M A∗ ⊆ L and M 0 = M 0 A∗ ⊆ L.
Because P1 , · · · , Pk , P 0 form the partition of A∗ and the density of P 0 is zero,
we can deduce that δA (M ) + δA (M 0 ) = 1, which implies δA (M ) = δA (L) andδA (M 0 ) = δA (L0 ). For each n ∈ N and i, the set Mn = {w ∈ M | |w| ≤ n} and
Mn0 = {w ∈ M 0 | |w| ≤ n} are finite and hence the sequence of reverse definite
languages Mn A∗ and Mn0 A∗ converges to L from inner and outer, respectively,i.e.(i) Mn A∗ ⊆ L and Mn0 A∗ ⊇ L holds for each n, and (ii) limn→∞ δA (Mn A∗ ) =δA (L) and limn→∞ δA (Mn0 A∗ ) = δA (L).
Proof of (2) ⇒ (1): This direction is shown by contraposition. We assume that(1) is not true, i.e., some sink component, say Qj , is not a singleton. By theminimality of A, Qj contains at least one final state, say p, and at least one
non-final state, say p0 (if not, all states in Qj are right equivalent). For eachq ∈ Qj , we write Lq for the language Lq = {w ∈ A∗ | q0 · w = q}.
Because Pj is non-empty and Pj = Pj A∗ holds, the density of Pj is not zero.
Pj has non-zero density implies that there exists at least one state q in Pj suchthat Lq has non-zero density. Since Qj is a sink (strongly connected, especially),
there exist some words wq,p and wp,p0 such that q · wq,p = p and p · wp,p0 = p0 .
Thus Lq wq,p ⊆ Lp holds, from which we can deduce that δA (Lp ) ≥ δA (Lq wq,p ) =−|w |δA (Lq ) · #(A) q,p > 0, i.e., Lp has non-zero density, say α > 0.
We can show that, for every reverse definite language R = E ∪ F A∗ (where
E, F are finite sets) such that R ⊆ L, F A∗ ∩ Lp = ∅ holds as follows. If there
is some word w ∈ F A∗ ∩ Lp , then wwp,p0 is in F A∗ ∩ L since wwp,p0 ∈ Lp0
and p0 is non-final. This violates the assumption R ⊆ L. This means that every
reverse definite subset R = E ∪ F A∗ of L should have density less than or equalto δA (L \ Lp ) = δA (L) − α < δA (L). Hence, no sequence of reverse definite
languages converges to L from inner.
tu
For a given automaton A, we can construct its reverse automaton Ar recognising L(A)r by flipping final and non-final states and reversing transition relations. By the definition of definite and reverse definite languages, L is Dmeasurable if and only if Lr is RD-measurable. Hence, we can use Theorem 1
to deduce the decidability of D-measurability.
Corollary 1. For a given regular language L it is decidable whether L is RDmeasurable (D-measurable, respectively).

3.1

Algebraic characterisation

In this subsection we give an algebraic characterisation of RD-measurability,
which is a natural analogy of the algebraic characterisation of RD stated asfollows. Let S be a semigroup. An element x ∈ S is called a left zero if xS = {x}holds. An element x ∈ S is called an idempotent if x2 = x holds.
Theorem 2 (cf. [4]). For a regular language L and its syntactic semigroup SL ,the followings are equivalent:(1) L is in RD.
(2) Every idempotent of SL is a left zero.
Let M be a monoid. For elements x and y in M , we write x ≤R y if xM ⊆ yM
holds. Notice that x ≤R y if and only if yz = x for some z ∈ M . An element x
is called R-minimal if y ≤R x implies x ≤R y for every y in M .
Theorem 3. For a regular language L and its syntactic monoid ML , the followings are equivalent:(1) L is RD-measurable.
(2) Every R-minimal element of ML is a left zero.
(3) Every R-minimal idempotent of ML is a left zero.
Proof. Let A = (Q, ·, q0 , F ) be the minimal automaton of L. Notice that ML
is isomorphic to the transition monoid T = ({fw : Q → Q | w ∈ A∗ }, ◦, fε ) of
A where fw is the map defined by fw (q) = q · w, the multiplication operation◦ is the composition fu ◦ fv = fuv and the identity element fε is the identity
mapping on Q. Hence, we identify ML with T .
Proof of (1) ⇒ (2): Let f be an R-minimal element of T . If f (q) is not in any
sink component of A for some q, there is a some word w such that (f ◦ fw )(q) =f (q) · w is in some sink component. But this means that f is not R-minimal
because q is not reachable by f (q)·w, which implies (f ◦fw )◦g 6= f for any g ∈ T .
Hence, f (q) is in some sink component. By the assumption and Theorem 1, every
sink component of A is a singleton. This means that f (q) · w = q holds for every
w, i.e., f is a left zero.
Proof of (2) ⇒ (1): This direction is shown by contraposition. Assume (1) is
not true. That is, there is a sink component Q0 ⊆ Q which is not a singleton by
Theorem 1. Let p and q in Q0 be two different states and f be an R-minimal
element in T such that f (q0 ) = p (such f always exists since A is accessible andQ0 is sink). Because Q0 is strongly connected, there is some word w such thatp · w = q. This means that f 6= f ◦ fw (because f (q0 ) = p 6= q = (f ◦ fw )(q0 )),i.e., f is not a left zero.
Proof of (2) ⇔ (3): (2) implies (3) is trivial. Assume (3). Let x be an R-minimal
element of ML . Because ML is finite, there is some index i ≥ 1 such that xi is an
idempotent. By the R-minimality of x and xi = x · xi−1 ≤R x, xi · y = x holds
for some y. But xi is a left zero by the assumption, this means that x = xi . tu4

Decidable Characterisation of GD-Measurability

In this section we consider the GD-measurability. First we show that the GDmeasurability is equivalent to the LT-measurability.
Proposition 1. A language L is LT-measurable if and only if L is GD-measurable.
Proof. For proving the equivalence ExtA (LT) = ExtA (GD), it is enough toshow that every locally testable language is GD-measurable by the monotonicity and idempotency of ExtA (Lemma 2): ExtA (GD) ⊇ LT implies ExtA (GD) =ExtA (ExtA (GD)) ⊇ ExtA (LT) ⊇ ExtA (GD). Further, since GD is closed under Boolean operations, GD-measurability is closed under Boolean operations
by Lemma 2 and hence we only have to show that wA∗ , A∗ w and A∗ wA∗ are
all GD-measurable for every w. The languages of the form wA∗ and A∗ w arealready in GD, thus it is enough to show that A∗ wA∗ is GD-measurable. Thiswas essentially shown in [16] as follows. Since the case w = ε is trivial, we assume w = a1 · · · an where ai ∈ A and n ≥ 1. Define Wk = (Ak \ Kk )wA∗ where
Kk = {u ∈ Ak | ua1 · · · an−1 ∈ A∗ wA∗ } for each k ≥ 0. Intuitively, Wk is theset of all words in which w firstly appears at the position k + 1 as a factor.
By definition, Wk is generalised definite (reverse definite, in particular).
Clearly,S
Wi ∩ Wj = ∅ and δA (Wi ) > 0 for each i 6= j, thus we have k≥0 Wk = A∗ wA∗
S

n
∗
∗
∗
∗
and hence limn→∞ δAk≥0 Wk = 1, i.e., µGD (A wA ) = 1. Thus A wA ∈tu

ExtA (GD).

Next we give a decidable characterisation of GD-measurability for regular languages. The characterisation is not so much simple as the one of RDmeasurability stated in Theorem 1, but the proof is a natural generalisation of
the proof of Theorem 1.
Theorem 4. Let A = (Q, ·, q0 , F ) be a deterministic automaton and let Q1 , · · · , Qk
Sk
be its all sink components and let Q0 = Q \ i=1 Qi . Define
Pi = {w ∈ A∗ | q0 · w ∈ Qi }∗Si = {w ∈ A | Qi · w ⊆ F }P 0 = {w ∈ A∗ | q0 · w ∈ Q0 }Si0 = {w ∈ A∗ | Qi · w ⊆ Q \ F }for each i ∈ {1, · · · , k}, and define
M=

k
[
i=1

Pi Si

and

M0 =

k
[

Pi Si0 .

i=1Then L = L(A) is GD-measurable if and only if δA (L) = δA (M ) and δA (L) =δA (M 0 ) holds.
Proof. By the construction,clearly M ⊆SL and M 0 ⊆ L holds. Also, by Lemma 3,Skk∗we have M = i=1 Pi A Si and M 0 = i=1 Pi A∗ Si0 . Intuitively, M and M 0 are“largest” (with respect to the density) languages of the form P A∗ S included inL and L, respectively. “if” part is easy. δA (L) = δA (M ) and δA (L) = δA (M 0 ) imSk
plies that the two sequences of generalised definite languages Mn = i=1 {uA∗ v |Sku ∈ Pi , v ∈ Si , |u| + |v| ≤ n} and the complements of Mn0 = i=1 {uA∗ v | u ∈Pi , v ∈ Si0 , |u| + |v| ≤ n} converges to L if n tends to infinity from inner andouter, respectively.
Next we show “only if” part by contraposition. With out loss of generality,
we can assume that δA (L) > δA (M ). For every u, v ∈ A∗ , we show thatuA∗ v ⊆ L ⇒ (uA∗ \ P 0 )v ⊆ M.

(♦)

This implies δA (uA∗ v) = δA ((uA∗ \ P 0 )v) ≤ δA (M ) (because P 0 has density
zero by Lemma 3), from this we can conclude that every generalised definite
language should have density less than or equal to the density of M . Hence,no sequence of generalised definite languages converges to L from inner by theassumption δA (L) > δA (M ). Let u, v ∈ A∗ be words satisfying uA∗ v ⊆ L, andlet uw be a word in uA∗ \ P 0 . Because uw is not in P 0 , uw is in Pj for somej ∈ {1, · · · , k}. The condition uA∗ v ⊆ L implies uwA∗ v ⊆ L and hence we haveuww0 v ∈ L for any word w0 ∈ A∗ . For every q ∈ Qj , there is some word w0 suchthat q0 · uww0 = q because Qj is strongly connected. Thus we can conclude thatq · v ∈ F for each q ∈ Qj , which means that v is in Sj and hence uwv
S is in M (byuw ∈ Pj and v ∈ Sj ), i.e., the condition (♦) is true. Let R = E ∪ i∈I Fi A∗ Gi bea generalised definite language included in L, where E and Fi , Gi ⊆ A∗ are finite
for all i ∈ I and I is a finite index set. The condition (♦) and R ⊆ L implies thatS∗
0i∈I (Fi A \ P )Gi ⊆ M (note that E is density zero because it is finite). Thismeans that any generalised definite subset of L should have a density smaller or
equal to δA (M ) which is strictly smaller than δA (L) by the assumption. Thus
there is no convergent sequence of generalised definite languages to L from inner.
tu
By the construction, clearly, all languages Pi , Si , Si0 are regular and automata
recognising these languages can be constructed from A. Hence, we can effectively construct two automata recognising M and M 0 from A. Also, checking
the condition δA (L) = δA (M ) and δA (L) = δA (M 0 ) is decidable: this conditionis equivalent to δA (M ∪ M 0 ) = 1, and it is decidable in linear time whether agiven deterministic automaton recognises a co-null regular language (cf. [13]).
Corollary 2. For a given regular language L it is decidable whether L is GDmeasurable (equivalently, LT-measurable by Proposition 1).
4.1

Remark on the measuring power of GD

As we stated in Example 2, the language Mk = {w ∈ {a, b}∗ | |w|a = |w|b
mod k} is LT-immeasurable for any k ≥ 2. The proof of the above fact givenin [16] uses an algebraic characterisation of locally testable languages. However,through Proposition 1, we can more easily prove this fact by showing that Mk
is LT-immeasurable as follows.

Proposition 2. Mk = {w ∈ {a, b}∗ | |w|a = |w|b mod k} is GD-immeasurable
for any k ≥ 2.
Proof. By simple calculation, we have δA (Mk ) = 1/k. By definition, every infinite generalised definite language must contain a language of the form uA∗ v
for some u, v ∈ A∗ . Let n = |uv|a − |uv|b mod k, define w = b if n = 0 andw = ε otherwise. Then we have uwv ∈ L but uwv 6∈ Mk . This means thattuµGD (Mk ) = 0 < δA (Mk ), i.e., Mk is GD-immeasurable.
A non-empty word w is said to be primitive if there is no shorter word v
such that w = v k for some k ≥ 2. In [14], it is shown that the set Q of allprimitive words over A = {a, b} is REG-immeasurable where REG is the class of
all regular languages. The proof given in [14] involves some non-trivial analysisof the syntactic monoid of a regular language. If we consider the more weaker
notion, GD-measurability, the proof of the GD-immeasurability is almost trivial:
by definition, every infinite generalised definite language must contain a languageof the form uA∗ v. But uA∗ v contains the non-primitive word uvuv, hence there
is no infinite generalised definite subset of Q.
From the last example, one can naturally consider that the GD-measurability
is a very weaker notion than the REG-measurability. We are interested in how
far the GD-measurability is from the REG-measurability: is there any natural
subclass GD ( C ( REG of regular languages such that the C-measurability
differs from these two measurability? A possible candidate is SF the class of all
star-free languages as we discussed in the next section.

5

Related and Future WorkAs we stated in Section 1, the decidability of SF-measurability [15] for regular
languages is still unknown. The decidability of LT-measurability was left openin [16], but thanks to Proposition 1 and Theorem 4, it was shown that LTmeasurability (= GD-measurability) is decidable.
For some weaker fragments of star-free languages, the decidability of measurability for regular languages are known: a language L is called piecewise
testable [12] if it can be represented as a finite Boolean combination of languages of the form A∗ a1 A∗ · · · A∗ ak A∗ (where ai ∈ A for each i), and L is calledalphabet testable if it can be represented as a finite Boolean combination of languages of the form A∗ aA∗ (where a ∈ A). We denote by PT and AT the classof all piecewise testable and alphabet testable languages, respectively. It was
shown in [16] that AT-measurability and PT-measurability are both decidable.
Moreover, AT-measurability and PT-measurability do not rely on the existenceof an infinite convergent sequence, but rely on the existence of a certain single
language [16]:T– L is AT-measurable if and only if L or its complement contains a∈A A∗ aA∗ .
– L is PT-measurable if and only if L or its complement contains a languageof the form A∗ a1 A∗ · · · A∗ ak A∗

In [17] the tight complexity bounds of AT-measurability and PT-measurability
for regular languages was given: AT-measurability is co-NP-complete and PTmeasurability is decidable in linear time, if an input regular language is given bya deterministic automaton. Even though AT is a very restricted subclass of PT,
the complexity of AT-measurability is much higher than PT-measurability. This
contrast is interesting. Thanks to Theorem 1, RD-measurability is decidable inlinear time, if an input regular language is given by a minimal automaton.
Our future work are three kinds.
(1) Give the tight complexity bound of D- and GD-measurability.
(2) Prove or disprove ExtA (GD) ( ExtA (SF).
(3) If ExtA (GD) ( ExtA (SF), prove or disprove the decidability of SF-measurability.
As demonstrated in the proof of Theorem 4, GD-measurability heavily relies on the existence of an infinite sequence of different generalised definite languages. Hence the situation is essentially different with AT-measurability andPT-measurability. One might naturally consider that GD-measurability has amore higher complexity than AT-measurability.
To tackle the problem (2) and (3), perhaps we can use some known techniques
related to star-free languages, for example, the so-called separation problem fora language 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 SF is decidable [10].
Acknowledgements: I am grateful to Mark V. Lawson whose helpful discussions were extremely valuable. The author also thank to anonymous reviewers
for many valuable comments. This work was supported by 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., Reutenauer, C.: Codes and Automata, Encyclopedia ofmathematics and its applications, vol. 129. Cambridge University Press (2010)
3. Brzozowski, J.: Canonical regular expressions and minimal state graphs for definite
events. Mathematical Theory of Automata 12, 529–561 (1962)
4. Brzozowski, J.: On Aperiodic I-monoids. Department of Computer Science. University of Waterloo. Research Report CS-75-28 (1975)
5. Brzozowski, J., Simon, I.: Characterizations of locally testable events. vol. 4, pp.
243–271 (1973)
6. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press,
New York, NY, USA, 1 edn. (2009)
7. Ginzburg, A.: About some properties of definite, reverse-definite and related automata. IEEE Transactions on Electronic Computers EC-15(5), 806–810 (1966)
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. Place, T., Zeitoun, M.: Separating regular languages with first-order logic. Log.
Methods Comput. Sci. 12(1) (2016)11. Salomaa, A., Soittola, M.: Automata Theoretic Aspects of Formal Power Series.
Springer-Verlag New York, Inc., Secaucus, NJ, USA (1978)
12. Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages.
pp. 214–222 (1975)
13. 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)14. Sin’ya, R.: Asymptotic approximation by regular languages. In: Current Trends in
Theory and Practice of Computer Science. pp. 74–88 (2021)
15. Sin’ya, R.: Carathéodory extensions of subclasses of regular languages. In: Developments in Language Theory. pp. 355–367 (2021)
16. Sin’ya, R.: Measuring power of locally testable languages. In: Diekert, V., Volkov,
M. (eds.) Developments in Language Theory. pp. 274–285. Springer International
Publishing, Cham (2022)
17. Sin’ya, R., Yamaguchi, Y., Nakamura, Y.: Regular languages that can be approximated by testing subword occurrences. Computer Software 40(2), 49–60 (2023),(written in Japanese)
18. Zalcstein, Y.: Locally testable languages. Journal of Computer and System Sciences
6(2), 151–167 (1972)