࡟ ఩ ࢱ㝈 ⨨ ࢖ࡿ 协 ࣉ卐 ₎ 㒊Ꮠࢱ ศࢸ ࡢ᭩ 㓄ࡁ ⨨Measuring Power ofLocally Testable Languages

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

ARyoma Sin’ya (Akita University, Japan)

DLT 2022 May 12 @USF Tampa, US.

Outline
1. Background I: measurability(5 min.)2. Background II: fragments of star-free languages (5 min.)3. Measuring power of locally testable languages (10 min.)4. Conclusion(2~5 min.)2

Outline
1. Background I: measurability
2. Background II: fragments of star-free languages
3. Measuring power of locally testable languages4. Conclusion3

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

1
Example 2: δA(aA*) =.
#(A)n

Example 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.

fi4

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

Example of a regular measurable language
Theorem [S., SOFSEM’21]:= {ε, ab, aabb, abab, …} over A = {a, b} is regular measurable.

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

the # of occurrences of a in w

mod k} for each k ≥ 1.

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

fi

6

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→∞

7fi

𝒞𝒞𝒞-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) ∉Conjecture [Dömösi-Horvath-Ito 1991]:

is not context-free.

Regular measurability was originally introduced for tackling this conjecture(cf. [S., SOFSEM’21] [S., DLT’21]).

𝖰𝖰

𝖰𝖰

3

[S., DLT’21]“UnambiguousPolynomial” =SF = “Star Free”
LTUPol“PiecewiseTestable” == “Locally Testable”

PT=“AlphabetTestable”
ATThis work [S.,DLT’22]
9Outline
1. Background I: measurability
2. Background II: fragments of star-free languages
3. Measuring power of locally testable languages
4. Conclusion

10SF = “Star Free”“Unambiguous
Polynomial” =LT

UPol“Piecewise
Testable” == “Locally Testable”

PT
AT = “Alphabet Testable”
11Testable languages
A language L over A is called• locally testable if it can be represented as a nite Boolean combination oflanguages of the form uA*, A*v and A*wA* [McNaughton-Papert 1971].
• piecewise testable if it can be represented as a nite Boolean combinationof languages of the form Lw = A*a1A*a2…A*an A* where w = a1a2⋯an[Simon 1972].

• alphabet testable if it can be represented as a nite Boolean combinationof languages of the form A*aA* (where a ∈ A) (cf. [Place-Zeitoun 2021]).
fi

fi

fi

12

SF = “Star Free”“UnambiguousPolynomial” =LTUPol“PiecewiseTestable” == “Locally Testable”

PT
AT = “Alphabet Testable”
13Unambiguous polynomials [Schützenberger 1976]aA*…A*aA*• A monomial is a language of the form A*
0 1 1
n−1 n nwhere ai ∈ A and Ai ⊆ A.
isunambiguous
ifithastheaA*…A*aA*• A monomial M = A*
0 1 1
n−1 n nunique factorisation property i.e., ∀w ∈ M, ∃!w0, …, wn ∈ A* s.t.
w = w0a1w1⋯anwn and wi ∈ A*
iforeach.
i• A language is called unambiguous polynomial if it can be represented asa nite disjoint union of unambiguous monomials.

fi14∅*a∅*b∅*cA* =PT= (A∖{a})*a(A∖{b})*b(A*∖{c})cA*∉“PiecewiseTestable” =∈∈SF = “Star Free”
abcA*abcA*
A*abcA*“Unambiguous∈∉Polynomial” = UPol=
“LocallyTestable”
LT∈∉
A*aA*bA*cA*
abcA*

AT = “Alphabet Testable”
15SF = “Star Free”[Schützenberger 1976]“Unambiguous
Polynomial” =[McNaughton-Papert 1971]

LTUPol“PiecewiseTestable” =[Simon 1972]= “Locally Testable”

PT
AT = “Alphabet Testable”
16Outline
1. Background I: measurability
2. Background II: fragments of star-free languages
3. Measuring power of locally testable languages
4. Conclusion

17Main results
Theorem I:
L is LT-measurable if and only if L is UPol-measurable .

(relatively) Not easy↑↓Easy

Theorem II:
L is PT-measurable if and only if L or its complement contains Lw for some w.
Theorem III:
L is AT-measurable if and only if L or its complement contains

⋂a∈A
18

A*aA*.

Proof sketch of “L is-measurable ⇒ L is-measurable”.

Remark: it is enough to show that any language of the form uA*, A*v, A*wA*
are-measurable (since-measurability is closed under Boolean operations).

uA* = ∅*a1∅*⋯∅*an A* itself is an unambiguous polynomial where u = a1⋯an,hence uA* is-measurable (A*v is-measurable, too).

𝗅𝗅𝗅𝗅𝗅𝗈𝗈𝗈𝗈𝗈𝖯𝖯𝖯𝖯𝖯However, A*wA*, is not a unambiguous polynomial in general (like A*abcA*).
We should construct a convergent sequence of unambiguous polynomials.
𝖳𝖴𝖴𝖫

𝖴𝖴𝖴Theorem I:
L is LT-measurable if and only if L is UPol-measurable.

19

Proof sketch of “L isA*wA* =-measurable ⇒ L is-measurable”.

∞x ∈ A* ∣ w rstly apperas in x at the index n as a factor} .
{⨄n≥0Each language Wn = {x ∈ A* ∣ w rstly apperas in x at the index n as a factor}
kis an unambiguous polynomial, hence its nite disjoint union ⊎n≥0 Wk converges

fi

20fi

𝗅𝗈𝖯fito A*wA* from inner.
𝖳𝖫𝖴Theorem I:
L is LT-measurable if and only if L is UPol-measurable.

(very rough) Proof outline of “L is-measurable ⇐ L is-measurable”.

Let M = A*
beanunambiguous
monomial.
aA*⋯a
A*1nn01We construct a convergent sequence (Ln)n∈ℕ of locally testable languages frominner, i.e., Ln ⊆ M and lim δA(Ln) = δA(M).
n→∞

𝗅𝗈𝖯

If we can construct such a sequence, then we can also construct a convergent
sequence of locally testable languages from outer (because the complement of an
unambiguous polynomial is also unambiguous polynomial [Schützenberger 1976]).
𝖳𝖫

𝖴

Theorem I:
L is LT-measurable if and only if L is UPol-measurable.

21

(very rough) Proof outline of “L is-measurable ⇐ L is-measurable”.

Let M = A*
beanunambiguousmonomial.
aA*⋯aA*1nn0
1We construct a convergent sequence (Ln)n∈ℕ of locally testable languages frominner, i.e., Ln ⊆ M and lim δA(Ln) = δA(M).
n→∞𝗅22fi𝗈𝖯

Case δA(M) = 0: The constant sequence (∅)n∈ℕ satis es the condition.

𝖳𝖫𝖴

Theorem I:
L is LT-measurable if and only if L is UPol-measurable.

(very rough) Proof outline of “L is-measurable ⇐ L is-measurable”.

Case δA(M) > 0:
Lemma 1: M can be written as M = PA*S where δA(P) = δA(S) = 0.
Lemma 2: PA*S =xA*z ∣ (x, z) ∈ Un} where Un is some nite set.
{⨄n≥0The sequence⋃xA*zof locally testable languages converges to M.
n∈ℕ𝗅23fi𝗈𝖯(x,z)∈Un𝖳𝖫

𝖴

Theorem I:
L is LT-measurable if and only if L is UPol-measurable.

Theorem II:
L is PT-measurable if and only if L or its complement
contains Lw for some w.
Theorem II’ (algebraic characterisation of PT-measurable regular languages):A regular language L is PT-measurable if and only if its syntactic monoid M
and syntactic morphism η satis es the following condition: for everyx ∈ M∖{0} there is a letter a ∈ A such that x′η(a) < x′ for every x′ x .

￼24fi￼￼

𝒥𝒥

Corollary: the PT-measurability for regular languages is decidable.

Outline
1. Background I: density and measurability
2. Background II: fragments of star-free languages
3. Measuring power of locally testable languages
4. Conclusion

25

Main results
Theorem I:
L is LT-measurable if and only if L is UPol-measurable .
Theorem II:
L is PT-measurable if and only if L or its complement contains Lw for some w.
Theorem III:
L is AT-measurable if and only if L or its complement contains⋂a∈A26

A*aA*.

Decision problems and complexity (progress report)• Yoshiki Nakamura pointed out that the PT-measurability for regular languages isdecidable in linear time, by using a reduction to some decision problem
considered in [N. Rampersad, J. Shallit, Z. Xu, 2009].
• Yutaro Yamaguchi pointed out that the AT-measurability for regular languages iscoNP-complete.

• The same coNP-completeness result was independently shown inKazuhiro Inaba’s unpublished manuscript“Quick Brown Fox in Formal Languages”
on arXiv uploaded in 2015.

• We summarised these results in our manuscript written in Japanese[S.-Yamaguchi-Nakamura, PPL2022].

27

Open problems and future work
• Is the LT-measurability for regular languages decidable?
• Does “L is SF-measurable ⇔ L is LT-measurable” hold or not?
• Measuring power of other fragments (or super class) of regular languages?

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

A(Akita-Inu)
29

Summary (“Table 1” of my paper)
Language

AlgebraLogic

Measurability

SFaperiodicFO

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

locally idempotent
and commutative

UPolPTATDA
J -trivial
idempotent
and commutative

ExtA (LT) = ExtA (UPol)
FO

2

B⌃1FO

130

PT ( RExtA (PT) ( ZO
L is PT-measurable i↵ L or L
contains a simple monomial
AT ( RExtA (AT) ( RExtA (PT)
L is AT-measurablei↵
LorLT⇤⇤
contains a2A A aA