革新知能統合研究センター

部分語数え上げ言語 $L(w_1, cdots, w_k)$ はパラメータとなる語 $w_1, cdots, w_k$ について部分語として出現する回数がすべて等しい語からなる言語である．
昨年9月に行われた国際会議DLT 2018 のT. F. Lidbette氏による講演[1]において，$k = 2$ の場合において $L(w_1, w_2)$ が正則言語となる(決定可能な)必要十分条件が紹介されていた．
$k leq 2$の一般の場合における$L(w_1, cdots, w_k)$の無限性についてもいくつかの部分的な結果が紹介されていたが，(決定可能な)必要十分条件については未解決という状況であった．
その後，講演者は$k leq 2$の一般の場合における$L(w_1, cdots, w_k)$の無限性に対する決定可能な必要十分条件を与えることに成功した．
決定可能な必要十分条件の鍵となるのは，de Bruijn graph と呼ばれる特定の長さの部分語の情報を全て含む特殊な有限有向グラフと，有限グラフ上の歩道(walk)に対する組合せ論的考察である．
本講演では$L(w_1, cdots, w_k)$の決定可能な必要十分条件を与え，証明の概略を説明する．さらに，いくつかの具体例について考察し，時間があれば今後の展開についても簡単な解説を行いたい．

[1] C. J. Colbourn, R. E. Dougherty, T. F. Lidbetter, J. Shallit: “Counting Subwords and Regular Languages”, LNCS Vol. 11088, pp. 1611–3349.(arXiv: https://arxiv.org/abs/1804.11175 )
[2] Ryoma Sin’ya, Note on the infiniteness of L(w_1, …, w_k) https://arxiv.org/abs/1812.02600