࡟ ఩ ࢱ㝈 ⨨ ࢖ࡿ 协 ࣉ卐 ₎ 㒊Ꮠࢱ ศࢸ ࡢ᭩ 㓄ࡁ ⨨Measuring Power ofGeneralised Definite Languages
࣐࣮ࠝࢡ㒊ศ࡜ࢱ࢖ࣉ㒊ศࢆ⤌ࡳྜࢃࡏࡓ౛♧ࠞʧ

ARyoma Sin’ya (Akita University, Japan)

CIAA 2023 Sept 22@Famagsta, North Cyprus

Outline
1. Background I: measurability(5 min.)2. Background II: known properties(5 min.)3. Main results(10 min.)4. Conclusion(5 min.)2Outline
1. Background I: measurability(5 min.)2. Background II: known properties(5 min.)3. Main results(10 min.)4. Conclusion(5 min.)3Density of formal languages
The density of a language L over A
is de ned asn−1i1#(L ∩ A )
δA(L) = lim.
i∑n→∞ n#(A)
i=0

Here #(X) denotes the cardinality of X.

δA(L) can be regarded as the (average)
probability that a randomly chosen
word is in L.

fi4

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

The density of a language L over A
is de ned asn−1i1#(L ∩ A )
δA(L) = lim.
i∑n→∞ n#(A)i=0

Example 2: δA(A*wA*) = 1 for any w.
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.

fi5

A*K1

K2

L・・・・・・M2

M1

L is said to be -measurable if there exists an in nite sequence of pairs oflanguages (Mn, Kn)n∈ℕ insuch that Mn ⊆ L ⊆ Kn and lim δA(Kn∖Mn) = 0.
n→∞6fi𝒞𝒞𝒞-measurability [S., SOFSEM’21] (cf. [Buck, 1946])

Example of a regular measurable language
Theorem [S., SOFSEM’21]:= {w ∈ A ∣ | w |a = | w |b } over A = {a, b} is regular measurable.
the # of occurrences of a in w

Proof: Let Lk = {w ∈ A* ∣ | w |a = | w |b

mod k} for each k ≥ 1.

𝖡𝖡

𝖡

1
Then, for each k ≥ 1, ⊆ Lk and δA(Lk) =→ 0 (if k → ∞) .
kThus the in nite sequence (∅, Lk)k≥1 converges to .

fi7

A*K1

K2

L・・・・・・M2

M1

L is said to be -measurable if there exists an in nite sequence of pairs oflanguages (Mn, Kn)n∈ℕ insuch that Mn ⊆ L ⊆ Kn and lim δA(Kn∖Mn) = 0.
n→∞8fi𝒞𝒞𝒞-measurability [S., SOFSEM’21] (cf. [Buck, 1946])

Original motivation of mesurability• A non-empty word w is said to be primitive if it can not be represented as anpower of shorter words, i.e., w = u ⇒ u = w (and n = 1).
denotes the set of all primitive words over {a, b}.

Example： ababa ∈ababab = (ab) ∉Primitive worsd conjecture [Dömösi-Horvath-Ito 1991]:
is not context-free.

𝖰𝖰𝖰

My idea: while every context-free language isregular measurable, is regular immeasurable.
𝖰𝖰

3

𝖰𝖬
𝖡

Summary of [S., SOFSEM’21]
Regular measurable languages
A deterministic CFL
Many complex context-freelanguages.

= {w ∈ {a, b}* ∣ | w |a > | w |b }There are uncountably many regularmeasurable languages.

Outline
1. Background I: measurability(5 min.)2. Background II: known properties(5 min.)3. Main results(10 min.)4. Conclusion(5 min.)

11Some properties of-measurability [S. DLT’21]ℳA( ) = {L ⊆ A* ∣ L isNotation:• ℳA( ) can be de ned as the Carathéodory extension of,a standard notion from measure theory.

• ℳA( ) is closed under Boolean operations and left-and-right quotients if
is closed under these operations.

• “Is a given CFG generates a regular measurable languages?”
is undecidable.

𝒞𝒞𝒞𝒞

𝒞

12fi𝒞𝒞-measurable}

Some properties ofNotation:-measurability [S. DLT’21]ℳA( ) = {L ⊆ A* ∣ L is-measurable}

Q: How about the decidability of -measurability for some
subclassof regular languages?

• “Is a given CFG generates a regular measurable languages?”
𝒞𝒞𝒞𝒞

𝒞is undecidable.

13•-measurability for DFAs is decidable in linear time [SYN 2022],
whereis the class of all piecewise testable languages.

𝖳De nition: L is piecewise testable [Simon 1972] if it can be
represented as a nite Boolean combination of languages of the form
Lw = A*a1A*a2…A*an A* where w = a1a2⋯an.

𝖳fi

14fi

𝖯𝖯Decidability•-measurability for DFAs is decidable in linear time [SYN 2022],
whereis the class of all piecewise testable languages.

•-measurability for DFAs is coNP-complete [SYN 2022],
whereis the class of all alphabet testable languages.

𝖳𝖳fi

15fi

𝖳De nition: L is alphabet testable if it can be represented as a nite
Boolean combination of languages of the form A*aA* (where a ∈ A) .
𝖳𝖯𝖯𝖠

𝖠Decidability•-measurability for DFAs is decidable in linear time [SYN 2022],
whereis the class of all piecewise testable languages.

•-measurability for DFAs is coNP-complete [SYN 2022],
whereis the class of all alphabet testable languages.

• The decidability ofwhere-measurability for DFAs is open [S. DLT’22],is the class of all locally testable languages.

𝖳𝖳fi

16fi

𝖳𝖳

𝖳

De nition: L is locally testable if it can be represented as a nite
Boolean combination of languages of the form uA*, A*v, A*wA*.
𝖳𝖯𝖯𝖫

𝖫𝖠

𝖠Decidability

ℳA( ) = {L ⊆ A* ∣ L isNotation:-measurable}•-measurability for DFAs is decidable in linear time [SYN 2022],
whereis the class of all piecewise testable languages.

•-measurability for DFAs is coNP-complete [SYN 2022],
whereis the class of all alphabet testable languages.

• The decidability of-measurability for DFAs is open [S. DLT’22],is the class of all locally testable languages.

where𝒞) ⊊ ℳA(𝖳𝖫

𝖳𝖯

𝖳𝖠

𝖳𝖳

𝖳

𝖳𝖳

𝒞

• Hierarchy is strict [S. DLT’22]: ℳA(𝖳𝖯𝖯𝖫𝖫𝖠

𝖠Decidability17) ⊊ ℳA().

Decidability

Main result of this work:
A decidable characterisation of-measurable}-measurable regular languages.

• The decidability of-measurability for DFAs is open [S. DLT’22],is the class of all locally testable languages.

where𝒞) ⊊ ℳA(𝖳𝖫𝖳𝖯𝖳𝖠𝖳𝖳𝖳𝒞• Hierarchy is strict [S. DLT’22]: ℳA(𝖫𝖫

𝖫ℳA( ) = {L ⊆ A* ∣ L isNotation:18) ⊊ ℳA().

Outline
1. Background I: measurability(5 min.)2. Background II: known properties(5 min.)3. Main results(10 min.)4. Conclusion(5 min.)19

Notation: ℬ() denotes the ( nite) Boolean closure of

De nite:.

Reverse de nite:= ℬ{wA* ∣ w ∈ A*}= ℬ{A*w ∣ w ∈ A*}
Generalised de nite:= ℬ{uA*v ∣ u, v ∈ A*},⊊⊊= ℬ{wA*, A*w, A*wA* ∣ w ∈ A*}

𝖳𝖫

𝖣𝖦𝖣𝒞𝖱𝖣Remark:

fifi

fi

20fi

𝖣𝖣𝖱𝖦𝒞

𝖣

Definite languages [Brzozowski 1962] [Ginzburg 1966]

Proposition: ℳ() = ℳ().

Proof (sketch):

Because ℳ is idempotent and preserves the closure property under
Boolean operations, it is enough to show thatwA*, A*w, A*wA* ∈ ℳ( ) for any word w.
But wA*, A*w is already in, we only have to show A*wA* ∈ ℳ().

De ne Wk = {xwy ∈ A* ∣ x, y ∈ A*, | x | ≤ k}.

𝖣𝖦𝖣𝖣𝖦𝖦

This means that Wk converges to A*wA* (from inner).
𝖳𝖫

Each Wk is reverse de nite, Wk ⊆ A*wA* , and satis es lim δA(Wk) = 1.
𝖣fi

fi

21fi

𝖦

Measuring power of LT and GDk→∞Sink component (a.k.a bottom strongly connected component)= (Q, ⋅ ,q0, F) be a deterministic automaton.

De nition: Let

A subset S ⊆ Q is called sink if it satis es following:(1) S is strongly connected: ∀p, q ∈ S ∃w ∈ A* p ⋅ w = q(2) S has no outgoing transition: ∀p ∈ S ∀w ∈ A* p ⋅ w ∈ S.

a, baq1q2aq0a, bbb
Sink components can be considered
as a minimal SCC with respect to thereachability relation.

q5a, bq3q4

𝒜a, bfifi22

= (Q, ⋅ ,q0, F) be a minimal deterministic automaton. TFAE:(1) L( ) is-measurable.

Theorem: Let(2) Every sink component of

is a singleton (contains only one state).

a, ba, baq1q2aq0a, b𝒜𝖣𝖣b𝖣𝒜𝖱𝖱𝒜𝖱Characterisation of RD-measurable REGs

baq5q1aq0bq4q5a, bq3q4a, bb-immeasurable-measurable
23ba, ba, bq3q2a= (Q, ⋅ ,q0, F) be a minimal deterministic automaton. TFAE:(1) L( ) is-measurable.

Theorem: Let(2) Every sink component ofCorollary:is a singleton (contains only one state).

-measurability for minimal DFAs are decidable in linear time.
-measurability for DFAs are decidable.

𝒜𝖣Corollary:

𝖣𝒜𝖱𝖱𝒜

𝖣

Characterisation of RD-measurable REGs24

= (Q, ⋅ ,q0, F) be a deterministic automaton, andQ1, …, Qk be its all sink components.
De ne Pi = {w ∈ A* ∣ q0 ⋅ w ∈ Qi},
Si = {w ∈ A* ∣ Qi ⋅ w ⊆ F} and S′i = {w ∈ A* ∣ Qi ⋅ w ∩ F = ∅}.

Theorem: LetLetM=) isk⋃
i=1

Pi Siand⋃Pi S′i.

-measurable if and only if δA(M) + δA(M′) = 1.

￼

25fi

M′ =ki=1

￼𝒜￼￼Then L(𝖣𝒜𝖦

Characterisation of GD-measurable REGs

Characterisation of GD-measurable REGs
Intuition: M is a largest subset of L( ) That is, M is a largest= (Q, ⋅ ,q0, F) be a deterministic automaton, andTheorem: Letthat can be represented as a-measurable subset of L(beitsallsinkcomponents.
Q,…,Qk(possibly in1 nite) unionof languages
Also, M′ is a largest
P={w∈A*∣q⋅w∈Q}
Dene,0iof the form uA*wi .
-measurable subset of L(.
)
S = {w ∈ A* ∣ Q ⋅ w ⊆ F} and S′ = {w ∈ A* ∣ Q ⋅ w ∩ F = ∅}.
iM=LetThen L() isk⋃
i=1iPi Siand￼￼fi⋃iPi S′i.

)) = δA(M) and δA(L( )) = δA(M′).
26fiM′ =ki=1

￼𝒜𝒜￼￼𝒜𝒜𝒜𝖣𝖣𝒜￼𝖣𝖦i-measurable if and only if δA(M) + δA(M′) = 1.

This condition means δA(L(𝖦𝒜𝖦).

= (Q, ⋅ ,q0, F) be a deterministic automaton, andQ1, …, Qk be its all sink components.
De ne Pi = {w ∈ A* ∣ q0 ⋅ w ∈ Qi},
Si = {w ∈ A* ∣ Qi ⋅ w ⊆ F} and S′i = {w ∈ A* ∣ Qi ⋅ w ∩ F = ∅}.

Theorem: LetLetThen L(M=) isk⋃
i=1Pi Siand⋃

Pi S′i.

-measurable if and only if δA(M) + δA(M′) = 1.

-measurability for DFAs is decidable.
(because the density of a regular language is computable
and M, M′ are regular by the construction)
￼27fiM′ =ki=1

￼

￼

𝒜

￼

𝖣￼

Corollary:

𝖣𝖦𝒜

𝖦

Characterisation of GD-measurable REGs

Outline
1. Background I: measurability(5 min.)2. Background II: known properties(5 min.)3. Main results(10 min.)4. Conclusion(5 min.)28

Theorem 1:-measurability for DFAs is decidable in linear time.
Theorem 2:
The measuring power ofandare equivalent, and-measurability is decidable for DFAs (in PSPACE).

𝖣𝖣𝖣Progress: we (S., Y. Nakamura and Y. Yamaguchi) found that it is in PTIME.

𝖳𝖱𝖦𝖫

𝖦Summary29

Is the measuring power ofequivalent or not?
[S. DLT’22]: ℳA(and) ⊊ ℳA((the class of all star-free languages)) ⊊ ℳA(= ℳA ()) ⊆ ℳA().

Is this inclusion strict?

𝖳𝖫

𝖥𝖲𝖳-measurability is weaker than regular measurability?

𝖯𝖣𝖦𝖳𝖠

𝖣𝖣How much𝖥𝖦𝖲𝖦Open problem

30

of all primitive words is regular immeasurable.

[S. SOFSEM’21]: The set

The proof uses non-trivial analysis of syntactic monoids of regular languages.
However, the-immeasurability ofis almost trivia:

Because uA*v contains non-primitive word uvuv,
there is no in nite generalised de nite subset of .

-measurability is weaker than regular measurability?

𝖣How much

𝖣fi

31fi𝖦

𝖰

𝖦𝖰

𝖰

Open problem

The decidable characterisation ofapproximation scheme:-measurability gives us the following

Input : an automaton
and an admissible error ratio ϵ > 0.
Output: an automaton ℬ (if exists) such that
(1) L( ) ⊆ L(ℬ),(2) L(ℬ) is generalised de nite,and (3) | δA(L( )) − δA(L( )) | ≤ ϵ.

𝒜𝒜fi

32
ffi

𝒜Can we apply this scheme to, say,obtain an e cient regular expression matching algorithm?
(or other decision problems)?
𝖣𝖦𝒜Application?

࡟ ఩ ࢱ㝈 ⨨ ࢖ࡿ 协 ࣉ卐 ₎ 㒊Ꮠࢱ ศࢸ ࡢ᭩ 㓄ࡁ ⨨࣐࣮ࠝࢡ㒊ศ࡜ࢱ࢖ࣉ㒊ศࢆ⤌ࡳྜࢃࡏࡓ౛♧ࠞʧAThanks!

(Akita-Inu)
33

Some known properties ofℳA( ) = {L ⊆ A* ∣ L isNotation:-measurable}• ℳA( ) is closed under Boolean operations and left-and-right quotients if
is closed under Boolean operations and left-and-right quotients.

• ℳA( ) is closed under Boolean operations and left-and-right quotients if
is closed under Boolean operations and left-and-right quotients.

• ℳA is a closure operator:⊆ ℳA( ) (monotone) ⊆ ⇒ ℳA( ) ⊆ ℳA( )(extensive)(idempotent) ℳA(ℳA( )) = ℳA( )𝒞𝒟𝒞𝒞𝒞𝒞𝒟𝒞𝒞𝒞𝒞
𝒞𝒞𝒞

𝒞-measurability [S. DLT’21]

34

Sink component (a.k.a bottom strongly connected component)
De nition: Let= (Q, ⋅ ,q0, F) be a deterministic automaton.

A subset S ⊆ Q is called sink if it satis es following:(1) S is strongly connected: ∀p, q ∈ S ∃w ∈ A* p ⋅ w = q(2) S has no outgoing transition: ∀p ∈ S ∀w ∈ A* p ⋅ w ∈ S.

= (Q, ⋅ ,q0, F),
the language P = {w ∈ A* ∣ q0 ⋅ w not in any sink component}

Fact: For any deterministic automaton

𝒜𝒜has density zero.

fifi35