数理解析研究所講究録
第 1799 巻 2012 年 57-59

57

2011 年度冬の LA シンポジウム [10]Relations between language classes
in terms of insertion and locality
Kaoru Fujioka

1Introduction

2*Preliminaries

Insertion systems use only insertion operations of
For a string $x\in V^{*}$ with an alphabet $V,$isthe form $(u,x, v)$ and produce a string
for a the length of . For $0\leq k\leq|x|$ , let $Pre_{k}(x)$given stringby inserting the string between and $Suf_{k}(x)$ respectively denote the prefix and theand .
the definition of insertion operati- suffix of with length . For $0\leq k\leq|x|$ , letons, using only insertion operations, we generate $Int_{k}(x)$ be the set of intermediate substrings ofonly context-sensitive languages.
with length .
Using insertion systems together with some morFor a positive integer , a language over isphisms, characterizing recursively enumerable lan- strictly k-testable if a triplet $S_{k}=(A, B, C)$ exguages is obtained in [8], [6]. Furthermore, simi- ists with $A,$ $B,$
such that, for any withlarly to the Chomsky-Sch\"utzenberger representa- $|w|\geq k,$ is in iff $Pre_{k}(w)\in A,$ $Suf_{k}(w)\in B$ ,tion theorem [1], each recursively enumerable lan- $Int_{k}(w)\subseteq C$. A language is strictly locally tesguage can be expressed using an insertion system table iff there exists an integer $k\geq 1$ such that isand a Dyck language in [7], and each context-hee strictly k-testable.
language can be expressed using an insertion syNote that, for an alphabet , a language
is astem and a star language in [5].
strictly l-testable language.
In [2] and [3], within the hamework of theLet $LOC(k)$ be the class of strictly k-testable
Chomsky-Sch\"utzenberger representation theorem, .languages. There is the following result.
some characterizations and representation theo...
rems of languages in the Chomsky hierarchy have I’heorem 1 [4] $LOC(1)$ $\subset LOC(2)$been provided by insertion system , strictly 10- $LOC(k)\subset\cdots\subset REG$ .
cally testable language , and morphism such as
We define an insertion system $\gamma=(T, P,A)$ ,$|x|$$\alpha uxv\beta$$\alpha uv\beta$

$u$

$v$

$x$

$x$

$R\cdot om$

$k$

$x$

$x$

$k$

$L$

$k$

$T$

$C\subseteq T^{k}$

$w$

$w$

$L$

$L$

$L$

$|$

$T^{+}$$T$$|$$\subset$$\subset$$\gamma$$R$$h(L(\gamma)\cap R)$

$h$

.

1
whereis an alphabet, $P$ is a finite set of insertion
The purpose of this paper is to clarify the relation
ules of the form $(u,x,v)$ with $u,x,$ $v\in\tau*$ , andbetween the classes of languages $h(L(\gamma)\cap R)$ using
is a finite set of strings over called axioms.
insertion systems of weight $(i, 0)$ for $i\geq 1$ and thoseWe write
ifand $\beta=$
using insertion systems of weight $(i, 1)$ for $i\geq 1$ .
for some insertion rule : $(u, x, v)\in P$with. We write
if no confusion exists. The reflexive and transitive closure of$*0ffice$ for Strategic Research Planning. Kyushu Univerdefined as.
sity$T$$A$$\{$$T$$i$$\alpha\Rightarrow^{r}\gamma\beta$$\tau$$\alpha_{1},\alpha_{2}\in T^{*}$$\alpha\Rightarrow\beta$$S$$\Rightarrow is$$\alpha=\alpha_{1}uv\alpha_{2}$$r$$\alpha_{1}uxv\alpha_{2}$$($$\Rightarrow^{*}$

58
A language generated by$\gamma$

2. $H(INS_{i}^{1}\cap LOC(1))\subset CF(i\geq 1)$ .

is defined as

In the present paper, we specifically examine the relation between language classes
An insertion system $\gamma=(T, P, A)$ is said to be of $H(INS_{[be]}^{0}\cap LOC(b))$ and $H(INS_{*1}^{i}\cap LOC(k_{1}))$weight $(m,n)$ if.
for$L(\gamma)=\{w\in T^{*}|s\Rightarrow_{\gamma}^{*}w$, for some $s\in A\}$ .

$i_{0},$$m$$=$$\max\{|x||(u,x,v)\in P\}$ ,$n$$=$$\max\{|u||(u,x,v)\in P or (v,x,u)\in P\}$ .

3$k_{0},i_{1},k_{1}\geq 1$

Main Results

For $m,n\geq 0$ , let
be the class of all lanFor context-free languages, from Theorem 3 andguages generated by insertion systems of weightTheorem 4, we obtain$(m’, n’)$ with $m’\leq m$ and $n’\leq n$ . We use insteadof $m$ or if the parameter is not bounded.
$CF=$ $H(INS_{i_{0}}^{0}\cap LOC(k_{0}))$$INS_{m}^{n}$

$*$

$n$

$=$

Theorem 2 [8].
withWe next examin the language class $H(INS_{2}^{0}\cap$$LOC(1))$ . From Theorem 3, $H(INS_{2}^{0}\cap LOC(1))$
and $REG$ are known to be incomparable.
$i_{0},$ $k_{0},$.

1.

$IN\mathscr{S}_{*}\subseteq IN\mathscr{S}_{i}’(0\leq i\leq i’, 0\leq j\leq j’)$2.

$INS_{*}^{1}\subset CF$$H(INS_{i_{1}}^{1}\cap LOC(k_{1}))$$k_{1}\geq 2,$ $i_{1}\geq 1$$e$.

A mapping : $V^{*}arrow\tau*$ is called morphism if
and $h(xy)=h(x)h(y)$ hold for any $x,y\in$ Theorem 5 $H(INS_{2}^{0}\cap LOC(1))$ and $H(INS_{1}^{1}\cap$. For any in , if $h(a)=a$ holds, then is an $LOC(1))$ are incomparable.
$h$$h(\lambda)=\lambda$$V^{*}$$a$$T$$h$identity morphism.
The following results related to Chomsky- Proof Consider an insertion systemof weight (2,0) with $T=$
Sch\"utzenberger like characterization are obtained$\{a, b\}$ , a strictly l-testable language $R=T^{+}$ , andusing insertion systems of weight $(i,0)$ or $(i, 1)$ for
an identity morphism $h:T^{*}arrow\tau*$ . The above de$i\geq 1$ and strictly k-testable languages $(k\geq 1)$ .
finition indicates directly that $L(\gamma)=h(L(\gamma)\cap R)$ .
We can show thatis not in $H(INS_{1}^{1}\cap$
Theorem 3 [2]$LOC(1))$ by contradiction. We omit the proof here.
1. $H(INS_{1}^{0}\cap LOC(1))\subset REG$ .
Now we consider an insertion system$(T, \{(a_{:}a, \lambda), (b, b, \lambda)\}, \{a,b\})$ of weight (1, 1) with
2. $H(INS_{1}^{0}\cap LOC(k))=REG(k\geq 2)$ .
$T=\{a, b\}$ , a strictly l-testable language $R=T^{+}$ ,3. $H(INS_{1}^{0}\cap LOC(1))$ and $REG$ are incompara- and an identity morphism $h:T^{*}arrow\tau*$ . From the$ble(i\geq 2)$ .
definition, we have $L(\gamma_{2})=h(L(\gamma_{2})\cap R)=\{a^{i}|$$i\geq 1\}\cup\{b^{i}|i\geq 1\}$ .
4. $H(INS_{1}^{0}\cap LOC(1))\subset CF(i\geq 2)$ .
From [2],is not in $H(INS_{2}^{0}\cap LOC(1))$ .
$\gamma_{1}$$=$$(T, \{(\lambda, ab, \lambda)\}, \{\lambda\})$$L(\gamma_{1})$$\gamma_{2}$$=$$\{$$($$t$$L(\gamma_{2})$5.

$H(INS_{\dot{*}}^{0}\cap LOC(k))=CF(i, k\geq 2)$.

Theorem 4 [3]Theorem 5 implies the following Corollaries.

Corollary 1 $H(INS_{2}^{0}\cap LOC(1))$ and $H(INS_{1}^{1}\cap$$LOC(1))\cap H(INS_{1}^{0}\cap LOC(2))$ are incomparable.
$($1.

$H(INS^{i}\cap LOC(k))=CF(i\geq 1, k\geq 2)$ .

$\square$59
Corollary 2 $H(INS_{2}^{0}\cap LOC(1))\subset H(INS_{i}^{1}\cap$$LOC(1))(i\geq 2)$ .
For the class of languages $H(INS_{1}^{0}\cap LOC(1))$ ,ffom the size of parameters, we have the inclusions
and$H(INS_{1}^{0}\cap LOC(1))\subseteq H(INS_{1}^{0}\cap LOC(2))$ . Next
we present the following proper inclusion.
$H(INS_{1}^{0}\cap LOC(1))\subseteq H(INS_{1}^{1}\cap LOC(1))$

Theorem 6 $H(INS_{1}^{0}\cap LOC(1))\subset H(INS_{1}^{1}\cap$$LOC(1))\cap H(INS_{1}^{0}\cap LOC(2))$ .
Proof To show the proper inclusion, we consider

an insertion system$\{a, b\})$,of weight (1, 1) with $T=\{a, b\}$ , a strictly$\gamma_{2}=(T,$$\{(a.a, \lambda), (b, b, \lambda)\}$l-testable language $R=T^{+}$ , and an identity morphism $h:T^{*}arrow\tau*$ .
In a similar way to Theorem 5, we can show thatis not in $H(INS_{1}^{0}\cap LOC(1))$ .

$L(\gamma_{2})$$LOC(1))\cap H(INS_{1}^{0}\cap LOC(2))\cap H(INS_{2}^{0}\cap$$LOC(1))$ .

Concluding Remarks

In the present paper, we specifically examined
the language classes $H(INS_{i_{0}}^{0}\cap LOC(k_{0}))$ andforand considered the relations of those language classes.
The following remain as open problems:$H(INS_{i_{1}}^{1}\cap LOC(k_{1}))$$i_{0},$$i_{1},$ $k_{0},$$k_{1}\geq 1$$\circ H(INS_{2}^{0}\cap LOC(1))\cap H(INS_{1}^{1}\cap LOC(1))=$.
.

[1] N. Chomsky and M.P. Sch\"utzenberger. The
algebraic theory of context-free languages.

Computer Programming and Formal Systems.
North Holland, pp.118-161, 1963.
[2] K. Fujioka. Morphic characterizations in termsof insertion systems with a context of lengthone. DLT 2011, LNCS 6795, pp.474-475, 2011.

[3] K. Fujioka. Morphic characterizations of languages in Chomsky hierarchy with insertionand locality. Information and Computation
209, pp.397-408, 2011.

[4] R. McNaughton and S.A. Papert. CounterFree Automata (M.I.T. research monographno. 65) The MIT Press, 1971.

$\square$Corollary 3 $H(INS_{1}^{0}\cap LOC(1))\subseteq H(INS_{1}^{1}\cap$

4References$H(INS_{1}^{0}\cap LOC(1))$

holds?

[5] F. Okubo and T. Yokomori. Morphic characterizations of language families in terms of insertion systems and star languages. Int. J. Found.
Comput. Sci., 22 (1), pp.247-260, 2011.
[6] K. Onodera. A note on homomorphic representation of recursively enumerable languages
with insertion grammars. IPSJ Joumal, 44,5,pp.1424-1427, 2003.
[7] G.
, M.J. P\’erez-Jim\’enez, and T. Yokomori. Representations and characterizationsof languages in Chomsky hierarchy by using
insertion-deletion systems. Int. J. Found.
Comput. Sci. 19,4, pp.859-871, 2008.
$P\dot{a}un$[S] G.
, G. Rozenberg, and A. Salomaa.
Homomorphic characterizations of recursively
enumerable languages with very small language classes. Theoretical Computer Science,
250, pp.55-69, 2001.
$P\dot{a}un$$H(INS_{2}^{0}\cap LOC(1))\cap H(INS_{1}^{1}\cap LOC(1))\supset$$H(INS_{2}^{0}\cap LOC(1))\cap H(INS_{1}^{0}\cap LOC(2))$

holds?
$CF=H(INS_{m}^{2}\cap LOC(k))$$m,$ $k\geq 1$?

holds for some