࡟ ఩ ࢱ㝈 ⨨ ࢖ࡿ 协 ࣉ卐 ₎ 㒊Ꮠࢱ ศࢸ ࡢ᭩ 㓄ࡁ ⨨Carathéodory Extensions ofSubclasses of Regular Languages

࣐࣮ࠝࢡ㒊ศ࡜ࢱ࢖ࣉ㒊ศࢆ⤌ࡳྜࢃࡏࡓ౛♧ࠞʧ

A

Ryoma Sin’ya (Akita University)
DLT 2021 Aug 17.

Outline
1. Background: density and measurability
2. Carathéodory extensions of local varieties
3. Conclusion2

Density of formal languages
1
Example 1: δA((AA)*) = .
2

The density of a language L over A
is defined asn−1

i1#(L ∩ A )
δA(L) = lim.
i∑#(A)n→∞ ni=01
Example 2: δA(aA*) =.
#(A)nExample 3: L⊥ = {w ∈ A* ∣ 3 ≤ | w | < 3
does not have a density.
n−1

in+1

for some even n}#(L⊥ ∩ A )1→ The value
can be larger than 2/3 and smaller than 1/3i∑
n i=0 #(A )infinitely many times, hence δA(L) diverges.
3Density of formal languages
1
Example 1: δA((AA)*) = .
2

The density of a language L over A
is defined asn−1i1#(L ∩ A )
δA(L) = lim.
i∑#(A)n→∞ ni=01
Example 2: δA(aA*) =.
#(A)nExample 3: L⊥ = {w ∈ A* ∣ 3 ≤ | w | < 3
does not have a density.

n+1

for some even n}

Theorem (cf. [Berstel 1973]):
Every regular language do have a rational density.

4

𝒞-measurability [SOFSEM 2021]
A*

K1

K2

L・・・・・・M2
M1

L is said to be 𝒞-measurable if there exists an infinite sequence of pairs oflanguages (Mn, Kn)n∈ℕ in 𝒞 such that Mn ⊆ L ⊆ Kn and lim δA(Kn∖Mn) = 0.
5n→∞

Example of a regular measurable language
Theorem [SOFSEM2021]:
The semi-Dyck language 𝖣 = {ε, ab, aabb, abab, …} over A = {a, b} isregular measurable.
Proof: Let Lk = {w ∈ A* ∣ | w |a = | w |bmod k} for each k ≥ 1.

the # of occurrences of a in w

1
Then, for each k ≥ 1, 𝖣 ⊆ Lk and δA(Lk) =→ 0 (if k → ∞) .
kThus the infinite sequence (∅, Lk)k≥1 converges to 𝖣 .
Note: there is no regular language L such that 𝖣 ⊆ L and δA(L) = 0.
6Known results [SOFSEM 2021]
All regular measurable languagesThe set of all primitive words

𝖰𝖣Many complex CFLs
There are uncountably many
regular measurable languages

𝖬2 = {w ∈ {a, b}* ∣ | w |a > 2 | w |b }nL⊥ = {w ∈ A* ∣ 3 ≤ | w | < 3
7n+1

for some even n}

Measurability à la Carathéodory
The outer-𝒞-measure (over A) of L ⊆ A* is defined asμ𝒞(L) = inf{δA(K) ∣ L ⊆ K ∈ 𝒞A}
where 𝒞A is the class of all languages in 𝒞 over A.
Theorem [S]:For any language L ⊆ A* (with a certain density condition),
L is 𝒞-measurable if and only if it satisfies the Carathéodory condition:μ𝒞(M) = μ𝒞(M ∩ L) + μ𝒞(M ∩ L) for any language M ⊆ A*.
We call ExtA(𝒞) = {L ⊆ A* ∣ L is 𝒞-measurable} the Carathéodory extensionof a class 𝒞.

Motivation of this work
The class ExtA(REG) = {L ⊆ A* ∣ L is REG-measurable} andthe class ExtA(REG) ∩ CFL are somewhat hard to analyse.

What about “miniatures” of ExtA(REG) ∩ CFL?
e.g., RExtA(ℒ) = {L ∈ REGA ∣ L is ℒ-measurable}

a regular extension of some subclass ℒ of regular languages.

9Outline
1. Background: density and measurability
2. Carathéodory extensions of local varieties
3. Conclusion

10

Closure properties
Theorem [S]:If language classes 𝒞 ⊆ 𝒟 satisfies the following conditions:(1) every language in 𝒟 has the density,(2) 𝒞 and 𝒟 are closed under left and right quotients,
then ExtA(𝒞) ∩ 𝒟A is closed under left and right quotients.
Proof idea: Let L ∈ 𝒟A be a 𝒞-measurable language.
There exists a convergent sequence (Kn, Mn) of L in 𝒞A.
−1−1−1

We can show that (w Kn, w Mn) converges to w L(albeit that some non-trivial calculation on densities is required).
11

Closure properties
Theorem [S]:If language classes 𝒞 ⊆ 𝒟 satisfies the following conditions:(1) every language in 𝒟 has the density,(2) 𝒞 and 𝒟 are closed under left and right quotients,
then ExtA(𝒞) ∩ 𝒟A is closed under left and right quotients.
Theorem [S]:If language classes 𝒞 ⊆ 𝒟 satisfies the following conditions:(1) every language in 𝒟 has the density,(2) 𝒞 and 𝒟 are closed under Boolean operations,then ExtA(𝒞) ∩ 𝒟A is closed under Boolean operations.
12Local varieties and Eilenberg theorem
A family of regular languages ℒ over A is called local variety [Adámek et al. 2014]
if it is closed under left-and-right quotients and Boolean operations

There is a corresponding notion for a family of finite monoids generated by A,
called local pseudovariety.
And there is an Eilenberg theorem for local varieties [Gehrke et al. 2008] roughly
stating “there is a natural bijection between local varieties and local pseudovarieties”.

13Star-free languages
A language L is said to be star-free if it can be represented as a finite applications ofBoolean operations and concatenations to finite languages.
The class 𝖲𝖥 of all star-free languages over A is a local variety.
Theorem [Schutzenberger 1965]:
L is star-free if and only if the syntactic monoid ML of L is aperiodic, i.e.,
ML has no non-trivial subgroup.

14Regular extension of local varieties
Theorem [S]:For a local variety ℒ over A, RExtA(ℒ) = {L ∈ REGA ∣ L is ℒ-measurable}
is also a local variety. Moreover, RExtA is a closure operator on local varieties.
(extensive) ℒ ⊆ RExtA(ℒ)

Theorem [S]:(monotone) ℒ ⊆ ℒ′ ⇒ RExtA(ℒ) ⊆ RExtA(ℒ′)(idempotent) RExtA(RExtA(ℒ)) = RExtA(ℒ)

𝖲𝖥 ⊊ RExtA(𝖲𝖥) ⊊ REGA if A contains at least two letters,i.e., RExtA extends SF non-trivially.
Note: 𝖲𝖥 ⊊ RExtA(𝖲𝖥) is clear because (aa)* ∉ SF, but(aa)* ⊆ A*(A∖{a})A* ∈ SF and hence (aa)* ∈ RExtA(SF).

Regular extension of SF
Lemma [S]:If the density of a star-free language L ⊆ A* is positive, then L contains words ofeven and odd length.

Theorem [S]:𝖲𝖥 ⊊ RExtA(𝖲𝖥) ⊊ REGA if A contains at least two letters,i.e., RExtA extends SF non-trivially.
Note: by Lemma above, we can deduce that any star-free subset of (AA)* is ofdensity zero and hence (AA)* ∉ RExtA(SF).

Regular extension of SF
Lemma [S]:If the density of a star-free language L ⊆ A* is positive, then L contains words ofeven and odd length.
i−1uw v ∈ η (t)Proof sketch:i+1−1
Claim 1uw v ∈ η (t)A*“δ*”and“isfinite”
imply(L)>
0MMLLALS intersects with the minimal ideal K of ML.
SηClaim 2The inverse image of K is of density 1(infinite monkey theorem), thus it contains
word of odd length, say, w. Let η(w) = m.

K
tw s.t. | w | = 1 mod 2
ii+1
By Schutzenberger’s theorem there exists i ≥ 1 such that x = x
for any x ∈ ML. By the minimality of K,
i+1i+1ii
there exist u and v such that η(uw v) = η(u)m η(v) = t = η(u)m η(v) = η(uw v) .
Claim 3

Summary
Local Varieties

Local Pseudovarieties

regularfinite
Correspondence?

star-freezero-one

aperiodic

zeroExtension RExt
finite co-finite(nilpotent)*zero-one = the class of all regular languages with density zero or one

Conclusion and future work
• We consider Carathéodory extensions of local varieties of regular languages.

These extensions could be considered as a “miniature” of the class of regularmeasurable context-free languages: a diﬃcult object.

• We showed that the extension operator RExtA is a closure operator on local varieties, andit extends 𝖲𝖥 non-trivially, and it does not extend some other local varieties (𝖥𝖨𝖭 or 𝖹𝖮).

• By Eilenberg theorem for local varieties, there exists a closure operator−1
MExtA(ℳ) = F (RExtA(F(ℳ)))

on local pseudovarieties of finite monoids(where F is the natural bijection between local varieties and local pseudovarieties).
Can we characterize this operator in purely algebraic way?
19࡟ ఩ ࢱ㝈 ⨨ ࢖ࡿ 协 ࣉ卐 ₎ 㒊Ꮠࢱ ศࢸ ࡢ᭩ 㓄ࡁ ⨨࣐࣮ࠝࢡ㒊ศ࡜ࢱ࢖ࣉ㒊ศࢆ⤌ࡳྜࢃࡏࡓ౛♧ࠞʧThanks!

A(Akita-Inu)
20