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

A

17th Workshop Computational Logic and Applications@the Jagiellonian University in Kraków

Ryoma Sin’ya (Akita University), 2023 Dec 14.

CIAA 2024 in Akita (Septermber 3 to 6)
28th International Conference on Implementation and Application of Automata• Topics: algorithms on automata, automata and logic, bioinformatics, complexity of automata

operations, compilers, computer-aided verification, concurrency, data structure design forautomata, data and image compression, design and architecture of automata software, digital
libraries, DNA/molecular/membrane computing, document engineering, editors, environments,
experimental studies and practical experience, implementation of verification methods and model
checking, industrial applications, natural language and speech processing, networking, newalgorithms for manipulating automata, object-oriented modeling, pattern-matching, pushdown
automata and context-free grammars, quantum computing, structured and semi-structured
documents, symbolic manipulation environments for automata, transducers and multi-tapeautomata, techniques for graphical display of automata, VLSI, viruses and related phenomena,and the world-wide web.

• The proceedings will be published by in the series of LNCS
• Tentative submission deadline: April 14, 2024

About Akita• In Tohoku (northern Japan) region• The latitude of Akita City is 39.72°N• Reachable from Tokyo, Nagoya, Osaka:• By plane (1~1.5 hours)• By bullet train (3.5~6 hours)• Lot of snow in winter:

There is a ski resort 15 minutes by carfrom Akita university

Snowboarding in Akita (Febrary 16, 2023)

Outline
1. Background I: density and measurability(7 min.)2. Background II: known properties(5 min.)3. Complexity results(8 min.)4. Conclusion(3 min.)5

Outline
1. Background I: density and measurability(7 min.)2. Background II: known properties(5 min.)3. Complexity results(8 min.)4. Conclusion(3 min.)6

Density of formal languages
The density of a language L over A
is defined asn−1i1#(L ∩ A )
δA(L) = lim.
i∑#(A)n→∞ ni= 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.

7

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→∞ n
i= 0

Example 2: δA(A*wA*) = 1 for any w.
nn+ 1

Example 3: L⊥ = {w ∈ A* ∣ 3 ≤ | w | < 3
for some even n}does not have a density.
Theorem [Berstel 1973]:
Every regular language do have a rational density, and It is computable.
Every unambiguous context-free language do have an algebraic density.
Theorem [Kemp 1980]:
There is a context-free language whose density is transcendental.
8

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

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

i

1
#(L ∩ A )
δA(L) = lim.
i∑#(A)n→∞ ni= 0

Example 2: δA(A*wA*) = 1 for any w.
nn+ 1

Example 3: L⊥ = {w ∈ A* ∣ 3 ≤ | w | < 3for some even n}does not have a density.
Problem:
Does every context-free language L have a density? (δA(L) converges?)
Theorem [Nakamura 2019]:
it is undecidable whether a given context-free language L satisfies δA(L) = 1.
9Density of formal languages
1.
Example 1: δA((AA)*) =2

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

i

1
#(L ∩ A )
δA(L) = lim.
i
∑
#(A)
n→∞ n
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+ 1for some even n}n#(L ∩ A )Theorem [Kozik, CLA’05]: it is undecidable whether limn#(A )
n→∞converges or not for a given context-free language L.
10

𝒞-measurability [S., SOFSEM’21] (cf. [Buck, 1946])
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.
11n→∞

Example of a regular measurable language
Theorem:

𝖡 = {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 |bmod k} for each k ≥ 1.

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

12

𝒞-measurability [S., SOFSEM’21] (cf. [Buck, 1946])
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.
13n→∞Original motivation of mesurability• A non-empty word w is said to be primitive if it can not be represented as an
power of shorter words, i.e., w = u ⇒ u = w (and n = 1).
𝖰 denotes the set of all primitive words over {a, b}.

Example： ababa ∈ 𝖰

3ababab = (ab) ∉ 𝖰

Primitive worsd conjecture [Dömösi-Horvath-Ito 1991]:
𝖰 is not context-free.
My naive idea: while every context-free language isregular measurable, 𝖰 is regular immeasurable.

Summary of [S., SOFSEM’21]
Regular measurable languages
A (simple) deterministic CFL

𝖬

𝖡= {w ∈ A ∣ | w |a = | w |b }Many complex context-freelanguages.

= {w ∈ {a, b}* ∣ | w |a > | w |b }𝖰

The set of all primitive words

There are uncountably many regularmeasurable languages.

Outline
1. Background I: density and measurability(7 min.)2. Background II: known properties(5 min.)3. Complexity results(8 min.)4. Conclusion(3 min.)16

Some properties of 𝒞-measurability [S. DLT’21]
Notation:ℳA(𝒞) = {L ⊆ A* ∣ L is 𝒞-measurable}• ℳA(𝒞) can be defined 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.

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

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

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

18

Decidability• 𝖯𝖳-measurability for DFAs is decidable in linear time [SYN 2022],
where 𝖯𝖳 is the class of all piecewise testable languages.
Definition: L is piecewise testable [Simon 1972] if it can berepresented as a finite Boolean combination of languages of the form
Lw = A*a1A*a2…A*an A* where w = a1a2⋯an .

19

Decidability• 𝖯𝖳-measurability for DFAs is decidable in linear time [SYN 2022],
where 𝖯𝖳 is the class of all piecewise testable languages.
• 𝖠𝖳-measurability for DFAs is coNP-complete [SYN 2022],
where 𝖠𝖳 is the class of all alphabet testable languages.
Definition: L is alphabet testable if it can be represented as a finite
Boolean combination of languages of the form A*aA* (where a ∈ A) .
20

Decidability• 𝖯𝖳-measurability for DFAs is decidable in linear time [SYN 2022],
where 𝖯𝖳 is the class of all piecewise testable languages.
• 𝖠𝖳-measurability for DFAs is coNP-complete [SYN 2022],
where 𝖠𝖳 is the class of all alphabet testable languages.
• The decidability of 𝖦𝖣-measurability for DFAs is decidable [S. CIAA’23],
where 𝖦𝖣 is the class of all generalised definite languages.
Definition: L is generalised defintie if it can be represented as a finite
Boolean combination of languages of the form uA*, A*v .
21

Decidability
Notation:ℳA(𝒞) = {L ⊆ A* ∣ L is 𝒞-measurable}• 𝖯𝖳-measurability for DFAs is decidable in linear time [SYN 2022],
where 𝖯𝖳 is the class of all piecewise testable languages.
• 𝖠𝖳-measurability for DFAs is coNP-complete [SYN 2022],
where 𝖠𝖳 is the class of all alphabet testable languages.
• The decidability of 𝖦𝖣-measurability for DFAs is decidable [S. CIAA’23],
where 𝖦𝖣 is the class of all generalised definite languages.
• Hierarchy is strict [S. DLT’22]: ℳA(𝖠𝖳) ⊊ ℳA(𝖯𝖳) ⊊ ℳA(𝖦𝖣).
22

Outline
1. Background I: density and measurability(7 min.)2. Background II: known properties(5 min.)3. Complexity results(8 min.)4. Conclusion(3 min.)23

Characterisation of 𝖠𝖳- and 𝖯𝖳-meaurability
Theorem [S. DLT’22]:A language L is 𝖠𝖳-measurable if and only if L or L contains the language
A*aA*.

⋂a∈AA language L is 𝖯𝖳-measurable if and only if L or L contains the language
Lw for some w ∈ A*, where Lw is the set of all words containing w as asubsequence (scattered subword).
Corollary:
If a given language L is regular, then 𝖠𝖳-measurability is decidable(because the inclusion problem is decidable for regular languages).
24

Characterisation of 𝖠𝖳- and 𝖯𝖳-meaurability
Theorem [S. DLT’22]:
A language L is 𝖠𝖳-measurable if and only if L or L contains the language
A*aA*.

⋂a∈A

A language L is 𝖯𝖳-measurable if and only if L or L contains the language
Lw for some w ∈ A*, where Lw is the set of all words containing w as asubsequence (scattered subword).
Theorem [SYN 2022]:
The 𝖠𝖳-measurability for DFAs is coNP-complete, while the 𝖯𝖳-measurability
for DFAs is decidable in linear time.
25

Definite languages [Brzozowski 1962] [Ginzburg 1966]
Notation: ℬ(𝒞) denotes the (finite) Boolean closure of 𝒞.

Definite:Reverse definite:

𝖣 = ℬ{A*w ∣ w ∈ A*}

𝖱𝖣 = ℬ{wA* ∣ w ∈ A*}

Generalised definite:

𝖦𝖣 = ℬ{uA*v ∣ u, v ∈ A*}

26

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

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

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

q5a, bq3q4a, b27

Characterisation of RD-measurable REGs
Theorem: Let 𝒜 = (Q, ⋅ ,q0, F) be a minimal deterministic automaton. TFAE:(1) L(𝒜) is 𝖱𝖣-measurable.
(2) Every sink component of 𝒜 is a singleton (contains only one state).

a, ba, baq1q2aq0a, bbbaq5q1aq0bq4q5a, bq3q4a, bb𝖱𝖣-immeasurable

𝖱𝖣-measurable

28ba, ba, bq3q2a

Characterisation of RD-measurable REGs
Theorem: Let 𝒜 = (Q, ⋅ ,q0, F) be a minimal deterministic automaton. TFAE:(1) L(𝒜) is 𝖱𝖣-measurable.
(2) Every sink component of 𝒜 is a singleton (contains only one state).

Corollary: 𝖱𝖣-measurability for minimal DFAs are decidable in linear time.
Corollary: 𝖣-measurability for DFAs are decidable.

29

Characterisation of GD-measurable REGs
Theorem: Let 𝒜 = (Q, ⋅ ,q0, F) be a deterministic automaton, andQ1, …, Qk be its all sink components.
Define Pi = {w ∈ A* ∣ q0 ⋅ w ∈ Qi},Si = {w ∈ A* ∣ Qi ⋅ w ⊆ F} and Si′ = {w ∈ A* ∣ Qi ⋅ w ∩ F = ∅}.
Let

M=k⋃

Pi Siandi= 1M′ =k⋃i= 1Pi Si′.

Then L(𝒜) is 𝖦𝖣-measurable if and only if δA(M) + δA(M′) = 1.

30

Characterisation of GD-measurable REGs
Intuition: M is a largest subset of L(𝒜) That is, M is a largest
Theorem: Let 𝒜 = (Q, ⋅ ,q0, F) be a deterministic automaton, andthat can be represented as a
𝖦𝖣-measurable subset of L(𝒜).
beits
all
sink
components.
Q,…,Q1k(possibly infinite)
unionof languages
Also, M′ is a largestP={w∈A*∣q⋅w∈Q}
Define,0iof the form uA*wi .
𝖦𝖣-measurable subset of L(𝒜).

Si = {w ∈ A* ∣ Qi ⋅ w ⊆ F} and Si′ = {w ∈ A* ∣ Qi ⋅ w ∩ F = ∅}.
Let

M=k⋃

Pi Si

and

i= 1M′ =k⋃

Pi Si′.

i= 1

Then L(𝒜) is 𝖦𝖣-measurable if and only if δA(M) + δA(M′) = 1.

This condition means δA(L(𝒜)) = δA(M) and δA(L(𝒜)) = δA(M′).
31

Characterisation of GD-measurable REGs
Theorem: Let 𝒜 = (Q, ⋅ ,q0, F) be a deterministic automaton, andQ1, …, Qk be its all sink components.
Define Pi = {w ∈ A* ∣ q0 ⋅ w ∈ Qi},
Si = {w ∈ A* ∣ Qi ⋅ w ⊆ F} and Si′ = {w ∈ A* ∣ Qi ⋅ w ∩ F = ∅}.
Let

M=k⋃

Pi Si

and

i= 1M′ =k⋃

Pi Si′.

i= 1

Then L(𝒜) is 𝖦𝖣-measurable if and only if δA(M) + δA(M′) = 1.

Corollary: 𝖦𝖣-measurability for DFAs is decidable (in PSPACE).
(because the density of a regular language is computableand M, M′ are regular by the construction)32

Outline
1. Background I: density and measurability(7 min.)2. Background II: known properties(5 min.)3. Complexity results(8 min.)4. Conclusion(3 min.)33

Summary• 𝖯𝖳-measurability and 𝖱𝖣-measurability for DFAs is decidable in linear time,
while 𝖠𝖳-measurability for DFA is coNP-complete.
• 𝖦𝖣-measurability is decidable for DFAs (in PSPACE).
Progress: we (S., Y. Nakamura and Y. Yamaguchi) found that it is in PTIME.

34

Open problem
Is the measuring power of 𝖦𝖣 and 𝖲𝖥 (the class of all star-free languages)
equivalent or not?
Definition: L is star-free if and only if it can be represented as a finite
Boolean combination and concatenation finite languages.
[S. DLT’22]: ℳA(𝖠𝖳) ⊊ ℳA(𝖯𝖳) ⊊ ℳA(𝖦𝖣) ⊆ ℳA(𝖲𝖥).
Is this inclusion strict?
How much 𝖦𝖣-measurability and 𝖲𝖥 are weaker than regular measurability?
35

Application?
The decidable characterisation of 𝖦𝖣-measurability gives us the following
approximation scheme:
Input : an automaton 𝒜 and an admissible error ratio ϵ > 0.
Output: an automaton ℬ (if exists) such that
(1) L(𝒜) ⊆ L(ℬ),(2) L(ℬ) is generalised definite,and (3) | δA(L(𝒜)) −δA(L(𝒜)) | ≤ ϵ.
Can we apply this scheme to, say,obtain an eﬃcient regular expression matching algorithm?
(or other decision problems, e.g., inclusion ?)36Dziękuję!

(Akita-Inu)
37