2025-11-15T04:52:11.684179

Dyck Words, Pattern Avoidance, and Automatic Sequences

Mol, Rampersad, Shallit

We study various aspects of Dyck words appearing in binary sequences, where $0$ is treated as a left parenthesis and $1$ as a right parenthesis. We show that binary words that are $7/3$-power-free have bounded nesting level, but this no longer holds for larger repetition exponents. We give an explicit characterization of the factors of the Thue-Morse word that are Dyck, and show how to count them. We also prove tight upper and lower bounds on $f(n)$, the number of Dyck factors of Thue-Morse of length $2n$.

academic

Dyck Words, Pattern Avoidance, and Automatic Sequences

基本情報

論文ID: 2301.06145
タイトル: Dyck Words, Pattern Avoidance, and Automatic Sequences
著者: Lucas Mol (Thompson Rivers University), Narad Rampersad (University of Winnipeg), Jeffrey Shallit (University of Waterloo)
分類: cs.DM (離散数学), cs.FL (形式言語), math.CO (組合論)
掲載誌: Communications in Mathematics 33 (2025), no. 2, Paper no. 5
論文リンク: https://arxiv.org/abs/2301.06145

要旨

本論文は、0を左括弧、1を右括弧と見なす二進列におけるDyck語の様々な性質を研究する。研究により、7/3-無冪二進語は有界なネスト深度を持つが、より大きな繰り返し指数に対してはこの性質が成立しないことが示される。論文はThue-Morse列におけるDyck因子の明示的な特性化を与え、それらの個数を計算する方法を示す。さらに、長さ2nのThue-Morse Dyck因子の個数f(n)に対する厳密な上界と下界が証明される。

研究背景と動機

問題定義

本研究が探究する中心的な問題は、無限二進列におけるDyck語因子の構造と性質の理解である。Dyck語は形式言語理論における基本的な概念であり、平衡括弧列を表現し、計算機科学と数学において重要な応用を有する。

研究の重要性

理論的意義: Dyck言語は文脈自由言語の典型例であり、自動列における分布を研究することは形式言語理論と自動機理論の深い関連性の理解に寄与する
組合数学的価値: パターン回避と無冪性は組合語学の中核的研究方向であり、本研究はこれらの概念をDyck語と結合させる
計算応用: 自動列はアルゴリズムと計算複雑性理論に広く応用され、そのDyck因子の性質の理解は実用的意義を有する

既存研究の限界

特定の自動列におけるDyck因子の体系的な特性化の欠如
無冪性とネスト深度の関係に関する定量的分析の不足
自動列のDyck因子計数に対する有効なアルゴリズムの欠落

核心的貢献

無冪性とネスト深度の関係: 7/3-無冪Dyck語のネスト深度は最大3であるが、任意に大きなネスト深度を持つ7/3⁺-無冪Dyck語が存在することを証明
Thue-Morse列のDyck因子の特性化: Thue-Morse列におけるすべてのDyck因子の完全な特性化を与える：h(x)の形式、ここでxは特定の三進列sの因子
自動列の一般理論: 実行和同期自動列のDyck因子に関する判定可能性理論の枠組みを確立
精密な計数結果: Thue-Morse列における長さ2nのDyck因子の個数d(n)に対する厳密な上下界を証明：d(n) ≤ nおよびd(n) ≥ n/2

方法の詳細

タスク定義

二進語w = w1..nが与えられたとき、0を左括弧、1を右括弧と見なすときwが平衡括弧列を表現する場合、wをDyck語と呼ぶ。形式的には、wがDyck語であることと以下は同値である：

B(w) = |w|₀ - |w|₁ = 0（平衡条件）
すべての前置詞w'に対してB(w') ≥ 0（非負性条件）

ネスト深度N(w)は、すべての前置詞におけるB(w')の最大値として定義される。

中核的方法

1. 無冪性分析方法

帰納法と構成的証明を使用：

定理2.1: 7/3-無冪Dyck語の構造を分析することにより、そのネスト深度≤3を証明
定理2.9: 特殊な準同型f、gを構成し、f(gᵗ(2))が任意に大きなネスト深度を持つ7/3⁺-無冪Dyck語を生成

2. 自動機理論的方法

Walnut定理証明器を利用した計算検証：

morphism f "0->00100110100110010110010011001011001101
           1->00101100110100110110011010010110011011
           2->00101101001101001011001101001011010011"
morphism g "0->022012 1->022112 2->202101"