定理 #330

# Parikhの定理のprofinite可換化表示と連続パラメータ持ち上げ 2026-09-13．洞龍弥との対話をもとに作成した研究ノート．AI生成・未査読． ## 投稿の要旨 自由profinite unital magmaから自由profinite可換モノイドへの標準写像について，clopen集合の直接像を分類し，その各成分のprofinite反復パラメータ化を元のclopen集合へ連続的に持ち上げる．前者は古典的Parikhの定理の再定式化，後者は本ノートで明示した追加的な構成として区別する．どちらについても，先行例が存在しないという意味の新規性は確定していない． ## 主張の一覧 有限alphabet A={a₁,…,a_k}，k≥1を固定する．T_A¹は単位を添加した自由magma，X_A=widehat(T_A¹)はすべての有限unital magma商によるcompletionとする．P=widehat(N)_monは加法モノイドNのすべての有限モノイド商によるcompletionであり，群のcompletion widehat(Z)とは区別する．葉数を数える写像は連続全射p:X_A→P^kへ延長される． ### A．clopen直接像の分類 任意のclopen U⊆X_Aについて有限個のb_i,v_ij∈N^kが存在して p(U)=⋃_i(b_i+Σ_j P v_ij)． 逆にこの形の集合はすべて，あるclopen Uの像である．αvは自然数倍n↦nvのPへの連続延長．各成分は有限生成部分モノイドの閉包の平行移動である．孤立点全体がN^kなので，「有限個の孤立点によって位相的に生成される閉部分モノイドの，孤立点による平行移動の有限和」という内在的な記述になる． ### B．連続パラメータ持ち上げ Aの表示は，連続写像s_i:P^{r_i}→Uが存在して p(s_i(α₁,…,α_{r_i}))=b_i+Σ_jα_jv_ij を満たすように選べる．自然数パラメータでは有限木を返す．有限木の種と有限個の一穴文脈を選び，各文脈の反復を有限変換モノイド経由でPに延長する構成による． 重要な限定：これは適切に選んだ有限表示のパラメータ空間からの持ち上げである．任意に指定された表示の持ち上げでも，成分集合そのものからのsectionでもない．一意性・標準性・自然性も主張しない．文脈の反復はmagmaの自己準同型でなくてよい．有限商の台集合上の自己写像の有限変換モノイドを使う． ### C．語の有限認識との比較 自由profinite monoid Y_A=widehat(A*)を挟み，yieldの延長y:X_A→Y_A，可換化a:Y_A→P^kとするとp=a∘yであり， {p(U):U∈Clop(X_A)}={a(V):V∈Clop(Y_A)}． これは「任意のCFLと同じParikh像を持つ正則言語が存在する」という古典的な主張のprofinite版である． ## 新規性と先行研究との関係 | 内容 | 位置づけ | |---|---| | Parikh像の半線形性，正則言語との可換同値 | 古典定理．新規性なし | | simple treeとreturn contextによる有限分解，型の初回使用とその後の自由反復 | Takahashi–Sin’ya，Rubtsovの既存の証明系統に属する．核の構成の新規性を主張しない | | 主張A，C，半線形閉包の表示 | 古典定理と標準的profinite理論を合わせた再定式化・整理．新しい言語論的定理とは位置づけない | | 元のclopen集合への連続パラメータ持ち上げB | 今回のノートで明示した追加的構成．この写像の形での既存の記述は確認した文献中では未確認だが，先行例不存在や独立した新規性は主張しない | | 孤立点による記述，openとなるalphabetの大きさ，境界での反例 | 定式化を明確にする直接計算・系．独立した新規性は主張しない | 主張Aは古典的Parikhの定理から標準的なcompletionの事実を用いて導け，逆に孤立点への制限から古典定理を復元できる．従ってAを古典定理より強い新しい言語論的結果として扱わない．証明でParikhの定理を前提にしないことと，新しい証明原理であることも区別する． 特に比較すべき先行研究は，Ganty–Majumdar–Monmegeの *Bounded Underapproximations* である．任意のCFL Lに対し，Lに含まれ同じParikh像を持つbounded CFL L′を構成する．従って「元の言語内で反復的な代表を選ぶ」という発想自体も新規とはいえない．Bは指定された木言語のclopen Uへの連続パラメータ化まで保持する記述であり，既存のbounded構成や木分解からどこまで直接従うかは追加比較を要する． https://arxiv.org/abs/0809.1236 「文献中で未確認」は新規性の証明ではない．投稿の貢献候補は，既存結果のprofinite幾何的整理と，構文木の反復を保った明示的な連続持ち上げの構成に限定する． ## 限界と検証 pがopenであることはk=1と同値（空alphabetも含めるならk≤1）であり，二文字以上ではclopenの像がclopenになるとは限らない．また，半線形集合の閉包は共通部分をそのまま保存しない．これらの反例は下の証明ノートに含める． 証明の非自明な入力は有限状態・有限個のreturn context・型の初回使用による起動である．compactnessだけでParikhを証明したとは主張しない．primitive word conjectureの解決，語順や曖昧性の保存，新しい計算量上界も主張しない． 添付の有限検算は，2状態の全16演算と二文字の全4割当て，葉数1〜5の550個の木を用いた35,200例である．対象は木分解・高さ・初回使用・再反復と葉数および状態の整合性．無限命題には証明を用い，有限検算をその代わりにしない．独立査読・Lean形式検証は未実施． ## 証明と参考文献 以下に基礎となる研究ノートの証明を収録する．節番号と文献番号は元ノートのものを保つ．木分解はSin’ya（https://arxiv.org/abs/1909.09393）とRubtsov（https://arxiv.org/abs/2301.00047）に帰属する既存の系統として扱う． --- # Profinite magma の可換化としての Parikh の定理 2026-09-13．洞龍弥との対話に基づく研究ノート．AI生成・未査読． ## 結論と出所 有限 alphabet A に対する自由 profinite unital magma から自由 profinite 可換モノイドへの標準写像を p とする．その clopen 集合の直接像は，ちょうど「孤立点による平行移動と，有限個の孤立点が生成する閉部分モノイドとの和」の有限和である．これを Parikh の定理を前提とせずに証明する．さらに，各成分の profinite パラメータ化は元の clopen 集合へ連続的に持ち上がる． 有限木の分解という証明の核は Takahashi–Sin’ya，Rubtsov の既存の証明系統に属する [2,3]．有限認識と profinite clopen の対応は標準的な枠組み [1,5]．本ノートはそれらを有限 magma の状態に直接適用し，完成化・像の分類・連続的持ち上げを明示したもの．新規性は主張しない． Parikh の定理そのものは証明の入力にしない．以下の主定理には未証明の予想を仮定しない．一方，Lean 等による形式検証はしていない．添付プログラムは有限整合性検査に限る． ## 1．対象と標準写像 A={a₁,…,a_k} を有限集合，k≥1 とする．T_A は A を葉ラベルとする非空の平面二分木の集合で，接ぎ木を演算とする自由 magma． 空語を扱うために，単位 ε を添加した自由 unital magma \[T_A^1=\{\varepsilon\}\sqcup T_A.\] を用いる．積は非空木どうしなら接ぎ木，ε·t=t·ε=t．これに結合律や可換律を課してはいない． X_A=widehat(T_A¹) をすべての有限 unital magma 商についての profinite completion とする．残留有限性は，葉数≤Nの木をそれぞれ記録し，それ以上を吸収元へ潰す有限 magma から分かる．したがって T_A¹ は X_A に稠密に埋め込まれる． N には 0 を含める．P=widehat(N)_mon を加法モノイド N の，すべての有限モノイド商による completion とする．群による completion widehat(Z) とは異なる． \[C_A=\widehat{\mathbb N^k}_{\mathrm{mon}}\cong P^k.\] 葉の個数を数える準同型 π:T_A¹→N^k，π(ε)=0，π(a_i)=e_i，π(s·t)=π(s)+π(t) は一意な連続準同型 \[p:X_A\longrightarrow P^k\] へ延長する．像は compact，したがって閉であり，稠密部分集合 N^k を含むため p は全射． 通常の非単位的自由 magma をそのまま使うと像は P^k\{0} になる．以下の単位添加は，この一点の不整合を避けるためである． ## 2．ターゲットの位相を具体的に計算する ### 命題2.1：有限閾値・周期商 N 上の有限指数モノイド合同は，整数 t≥0，d≥1 を用いて n~_{t,d}m ⇔ [n=m<t] または [n,m≥t かつ n≡m mod d] と表される．したがって P は有限巡回モノイド C_{t,d}=N/~_{t,d} の逆極限である． 証明：有限モノイドへの写像は 1 の像 x で決まり，列 0,x,2x,… は有限性から前周期と周期を持つ．最初の反復の場所と周期長を取れば，核合同がこの形になる．□ N^k から有限モノイドへの写像の各生成元像にも，それぞれ t_i,d_i を取れる．元の写像は各座標の C_{t_i,d_i} の積を経由する．逆にこれらの積は有限可換モノイド商である．この余終性から widehat(N^k)_mon≅P^k を得る． ### 命題2.2：有限点は孤立し，閉包から集合を復元できる P^k の孤立点全体は，ちょうど N^k である．任意の S⊆N^k に対して \[\overline S\cap\mathbb N^k=S.\tag{2.1}\] 証明：n∈N を固定し，閾値 t>n の商を取ると n の逆像は単集合 {n}．従って有限点は clopen．積でも同じ．逆に，孤立点は稠密部分集合 N^k と交わらない単集合ではありえない．(2.1) は孤立性から従う．□ したがって「profinite 閉包を取ると半線形性を判定するための集合情報が失われる」という理解は誤り．任意の離散集合が閉包から復元できる．問題は，その閉包に有限生成の特徴づけがあるかである． ### 命題2.3：境界は profinite integers 集合として \[P=\mathbb N\sqcup\{\infty_z:z\in\widehat{\mathbb Z}\}.\] ここで右辺は位相的な離散和ではない．N は開かつ稠密，境界 {∞_z} は閉で widehat(Z) と同相．加法は n+m は通常の和，n+∞_z=∞_{n+z}，∞_z+∞_w=∞_{z+w}． 境界点 ∞_z の近傍基は {n∈N:n≥t，n≡z mod d} ∪ {∞_w:w≡z mod d} で与えられる． 証明：逆極限の点がどこかの閾値商で前周期部分に入るなら，以後のすべての座標は同じ有限整数で決まり，有限点である．そうでなければすべての閾値を越え，周期座標は d ごとの整合的剰余族，すなわち widehat(Z) の点を与える．商で計算すれば加法と近傍の式を得る．□ ω:=∞_0 は lim n! であり，ω+ω=ω．これは N の単位 0 とは異なる． ## 3．半線形閉包の intrinsic な特徴づけ 有限ベクトル b,v₁,…,v_r∈N^k に対して，連続写像 f_{b,V}:P^r→P^k，(α₁,…,α_r)↦b+Σ_j α_j v_j を定める．αv は n↦nv の連続延長．ゼロベクトル v は除去してよい．r=0 の像は {b} とする． この compact な像を K(b;V) と書く．これは K(b;V)=b+cl(⟨v₁,…,v_r⟩) でもある．ここで ⟨…⟩ は加法部分モノイド． ### 定理3.1：半線形閉包の分類 K⊆P^k について，以下は同値． 1. K=cl(S) となる半線形集合 S⊆N^k がある． 2. K は有限個の K(b;V) の和集合である． 3. K は有限個の b_i+H_i の和集合で，各 b_i は孤立点，各 H_i は有限個の孤立点によって位相的に生成される閉部分モノイドである． そのとき S=K∩N^k で一意に復元できる． 証明：N^r は P^r に稠密であり，f_{b,V} は連続，定義域は compact なので \[\overline{b+\sum_j\mathbb N v_j}=f_{b,V}(P^r)=K(b;V).\tag{3.1}\] 有限和集合について閉包を取れば 1⇒2．2⇒1 も同じ式．2⇔3 は孤立点が N^k であることと，f_{0,V}(P^r)=cl(⟨V⟩) による．一意性は (2.1)．□ このように，ターゲットの位相とモノイド演算だけで，必要なクラスを記述できる．単なる closed/clopen や位相次元ではなく，孤立点による有限生成が本質である． ## 4．主定理：profinite Parikh theorem Clop(X_A) を clopen 部分集合の集合とする．定理3.1のクラスを Aff_fin(P^k) と書く． ### 定理4.1 \[\{p(U):U\in\operatorname{Clop}(X_A)\}=\operatorname{Aff}_{\mathrm{fin}}(P^k).\tag{4.1}\] すなわち，任意の clopen U について有限個の b_i,v_ij∈N^k が存在し， \[p(U)=\bigcup_{i=1}^{\ell}\left(b_i+\sum_{j=1}^{r_i}P v_{ij}\right).\tag{4.2}\] 逆に，右辺の形のすべての集合が，ある clopen の像になる．ℓ=0 は空集合． 証明は次節で与える．本質は，有限商ごとに別の式を得るのではなく，すべての有限可換モノイド商に共通して通用する有限個の b_i,v_ij を作ることにある． ## 5．有限状態による直接証明 ### 5.1 clopen を一つの有限 magma で認識する U はある有限 unital magma M，準同型 h:T_A¹→M，受理集合 F⊆M を用いて \[U=\widehat h^{-1}(F)\] と書ける．実際，逆極限の有限商による円筒集合は clopen 基をなし，U の compactness から有限個で覆える．それらの商の積を取ればよい． R=U∩T_A¹=h^{-1}(F) は U に稠密なので \[p(U)=\overline{\pi(R)}.\tag{5.1}\] ε の採否は singleton {0} として別に扱えばよい．以下，非空木を考える． m=|M| とし，各木のすべての節点に，その節点以下の部分木の h-値をラベルとして付ける． ### 5.2 有限個の小さい木と return contexts simple tree を，根から葉までの各道で同じ状態が二度現れない木と定義する．高さは辺の数で測る．simple tree の高さは <m なので，その全体は有限． 状態 q を指定した一穴文脈 C が return context であるとは，穴に q を入れて M で評価すると根も q になること：C_M(q)=q． 高さ≤mの return contexts とその穴状態の組 (q,C) 全体を E_M とする．これは有限集合．文脈の穴以外の葉の個数ベクトルを v_C∈N^k と書く．文脈が穴だけの場合は除外する． ### 補題5.2：小さい return contexts への分解 任意の非空木 t は，ある simple tree t₀に，E_M の文脈を有限回挿入して得られる．各挿入は穴状態 q の節点で行い，根の状態を変えない． 証明：t が simple でなければ，自分と同じ状態を持つ真の子孫が存在する節点の中で，最も深いもの v を選ぶ．v の真の子孫を根とする部分木はすべて simple．そうでなければ，v より深い位置に同じ性質を持つ節点が存在するからである．従って v 以下の高さは≤m． v と同じ状態 q を持つ子孫 w を選び，v 以下の木で w 以下を穴に置き換えたものを C とする．これは (q,C)∈E_M．元の v 以下を w 以下へ置き換えると，木が真に小さくなり，根の状態は変わらない．この操作を繰り返せば有限回で simple tree へ到達する．逆順に操作すれば要求する挿入列を得る．□ ### 5.3 型の最初の一回と，その後の反復を分離する 木 t に出現する状態集合を st(t) と書く．return context (q,C) の挿入は，既存の状態出現を消さず，C に含まれる状態を追加するだけである．その挿入可能性は q∈st(t) だけで決まる． simple tree t₀と E⊆E_M の組を admissible と呼ぶのは，E の各要素をちょうど一度ずつ挿入できる順序があるとき．これは有限集合上の条件：初期状態集合 st(t₀) から始め，根状態が現在の集合にある文脈を選び，その文脈に現れる全状態を加えることを繰り返せば判定できる． 補題5.2の挿入列から，同じ型の二回目以降を除き，型の最初の出現だけを順に並べると，admissible な列になる．同じ型の追加挿入が新たな状態の種類を提供することはなく，状態集合は型の集合だけで決まるためである． 逆に，E の全型を一度ずつ挿入して種木 t_* を作れば，全型の根状態が以後も存在する．従って各型を任意の回数だけ追加挿入できる． 以上から，t₀に E の各型を一回以上使って得る木の葉数ベクトル全体は，正確に \[\pi(t_0)+\sum_{C\in E}v_C+\sum_{C\in E}\mathbb N v_C.\tag{5.2}\] である．前向きは挿入ごとに葉数が v_C 増えることから，逆向きは種木から任意の追加回数を実現できることから従う． ### 5.4 主定理の上側包含 simple tree は有限個，E_M は有限集合なので，admissible な (t₀,E) も有限個．根状態 h(t₀)∈F のものを選ぶと，補題5.2と(5.2)より π(R\{ε})=⋃_{(t₀,E) admissible, h(t₀)∈F} [π(t₀)+Σ_{C∈E}v_C+Σ_{C∈E}N v_C]. (5.3) これは有限和である．(5.1)，(3.1)で完成化すれば(4.2)を得る．Parikh の定理を引用してこの式を得たのではなく，有限 magma の状態だけから導いた． ### 5.5 逆包含 有限個の b_i,v_ij∈N^k を与える．各ベクトル x に対して葉数が x の語 u_x を一つ選ぶ．例えば a₁^{x₁}⋯a_k^{x_k}，x=0なら ε．正則言語 L=⋃_i u_{b_i} (u_{v_i1})*⋯(u_{v_ir_i})* の Parikh 像は ⋃_i[b_i+Σ_j N v_ij]．L を認識する有限モノイドへの準同型を，yield:T_A¹→A* と合成すれば，有限 unital magma による認識が得られる．対応する clopen U の像は，(5.1)より要求する compact な集合．従って(4.1)の逆包含も成立する．□ ## 6．各 affine パラメータ化は元の clopen へ持ち上がる ### 定理6.1：連続的持ち上げ 定理4.1の表示を，連続写像 s_i:P^{r_i}→U が存在して \[p(s_i(\alpha_1,\ldots,\alpha_{r_i}))=b_i+\sum_j\alpha_jv_{ij}.\tag{6.1}\] を満たすように取れる．これは affine cone 自身からの section を主張するものではない．パラメータ空間からの持ち上げである． 証明：まず有限文脈 C の n 回反復 C^n を考える．任意の有限 magma 商 N で C は自己写像 C_N:N→N を誘導する．n↦C_N^n は有限変換モノイドへの準同型だから P へ連続延長する．これらは商写像と整合的なので，逆極限により連続写像 P×X_A→X_A，(α,x)↦C^α[x] が定まる．有限 n と有限木で成立する等式を稠密性によって延長し， \[p(C^\alpha[x])=p(x)+\alpha v_C.\tag{6.2}\] を得る． (5.2)に対応する種木 t_* を固定する．各型 C∈E の根状態 q が出現する節点を t_* の中で一つ選び，印を付ける．同じ節点に複数の印が付く場合は入れ子の順序を固定する．有限の種木において，印付き節点の部分木を C^{α_C}[部分木] に置き換えるという有限式を，内側から評価する．これが s_i． 各演算と(6.2)は連続なので s_i は連続．自然数パラメータでは，各 return context が状態を保存するため像は U に入る．U が閉で自然数パラメータが稠密なので，全 profinite パラメータでも像は U に入る．葉数の式は (6.2) を有限回適用すれば得る．□ この結果により，像がたまたま半線形閉包と一致するだけでなく，その profinite 反復パラメータを構文木側で実現できることが分かる． ## 7．通常の Parikh の定理を復元する CFG を Chomsky normal form にし，非空語の導出を扱う．非終端集合を Q とする．有限 magma の台集合を P(Q) とし， B·C={X:ある Y∈B，Z∈C に対して規則 X→YZ がある}， h(a)={X:規則 X→a がある} と置く．受理条件は開始記号が h(t) に含まれること．必要なら新しい単位を添加し，ε の受理を別に指定する． この有限 magma が認識する木の集合 R の yield がちょうど元の CFL L．従って Ψ(L)=π(R)=p(cl(R))∩N^k であり，定理4.1と定理3.1から半線形．さらに5.5の正則言語を選べば，L と同じ Parikh 像を持つ正則言語が得られる． 逆に，有限 magma が認識する木の yield は，状態 m を非終端とし，x·y=m に対応する規則 m→xy と，h(a)=m に対応する規則 m→a を作ることで CFL になる．したがって，この対応で CFL を取りこぼしていない． ## 8．自由 profinite monoid を挟んだ正確な言い換え Y_A=widehat(A*)，y:X_A→Y_A を yield の延長，a:Y_A→P^k を可換化とする．p=a∘y． ### 系8.1 {p(U):U∈Clop(X_A)} ={a(V):V∈Clop(Y_A)} =Aff_fin(P^k). (8.1) 証明：右の monoid 側の clopen は正則言語に対応する [1]．その像の閉包は半線形閉包であり，逆に5.5により全半線形閉包を実現する．magma側は主定理．□ 従って Parikh の定理の構造的内容は，「構文木の有限認識から得る compact 像は，可換化まで進むと語の有限認識から得る compact 像と同じになる」ということである． この式は y 自体が clopen 像を保つとは言っていない．その主張は全CFLが正則であるという誤った結論を与える． ## 9．どの位相的主張は偽か ### 9.1 像は一般には clopen ではない k=2 とし，D={(n,n):n∈N} を考える．これは正則言語 (ab)* の Parikh 像で，その閉包は対角線 Δ_P={(α,α):α∈P}． Δ_P は閉だが開ではない．実際，(n!,2n!) は対角線の外にあるが，(ω,ω) へ収束する．従って ω の対角点には対角線に含まれる近傍がない． 特に主定理を「pはopen map」「clopenの像はclopen」と置き換えることはできない． ### 系9.2：open map になる alphabet の大きさ p が open であることは k=1 と同値（k=0も含める規約ならk≤1）． 証明：k≥2では，最初の二座標に上の例を取り，残りを0に固定する．k=1では任意の半線形集合は最終的に周期的．実際，H=Σ_j N v_j に正の生成元 d があれば，各 mod d の実現される剰余類で最小元を取ると，その類に属する H の部分はその最小元から d 刻みのすべての整数となる．従って有限和の平行移動も最終的に周期的． その閉包はある有限 C_{t,d} の逆像なので clopen．主定理から p は clopen を open に送り，任意の open は clopen の和集合だから p は open．□ ### 9.3 閉包は Boolean 操作をそのまま保存しない S={(m,n):m<n}，T={(m,n):m>n} は互いに素な半線形集合．しかし (n!,2n!)∈S と (2n!,n!)∈T の極限はいずれも (ω,ω)．従って \[\overline S\cap\overline T\ne\varnothing=\overline{S\cap T}.\] 各 clopen 像を literal な共通部分や補集合で扱って，そのまま Presburger 集合の Boolean algebra だと同一視してはいけない．孤立点へ制限してから閉包を取り直す操作と区別する必要がある． ### 9.4 closed だけでは何も分類していない 任意の S⊆N^k の閉包は compact で，(2.1)で S を復元できる．例えば {n²:n∈N} の閉包も compact だが，有限個の K(b;V) の和にはならない．そうなら定理3.1から平方数全体が最終的に周期的になってしまうが，平方数の間隔は無界だからである． ## 10．有効性，証明の位置づけ，有限検査 主定理は有効な構成を与える．有限 magma の表から，高さ<mのsimple trees，高さ≤mのreturn contexts，admissibleな型集合をすべて有限列挙できる．それらから式(5.3)，ひいては(4.2)を得る．効率的であるとは主張しない．型の個数と部分集合の列挙は非常に大きくなりうる． 有限 magma の情報が有限回の反復で済むわけではない．無制限の反復を表すパラメータ N^r を，profinite反復 P^r として compact に保っている．各有限可換商ごとに別々に探索するのではなく，同じ有限表示が全商で通用する． 証明の数学的な核は，有限状態性と一穴文脈の挿入である．compactnessだけから任意の連続写像の像がこの形になるわけではない．既存研究として，木の有限分解は [2,3]，代数的・不動点的な別証明は [4]，正則言語を直接構成する別方針は [6] にある．本ノートの completion 表現と連続的持ち上げの新規性は監査していない． 同梱の check_pumping.py を実行した結果：2要素集合上の全16個のmagma演算，各4通りの二文字の像について，葉数1～5の全550個のラベル付き平面二分木を検査し，計35,200例で補題5.2の高さ制限，最初の型の出現による起動，葉数ベクトルの表示，追加反復による状態保存が一致した．無限の主張には上の証明を用い，この有限検査を証明の代用にはしていない． Kobinの関連記録を調べるための呼出しは今回ブロックされた．このノートをKobinに保存・更新したとは主張しない． ## 文献 [1] Jean-Éric Pin, Mathematical Foundations of Automata Theory. Chapter IV（rational/recognizable sets），Chapter X, §2–3（profinite completion, clopen対応）． https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf [2] Ryoma Sin’ya, Simple proof of Parikh’s theorem à la Takahashi, 2019. 単純木，一穴文脈，挿入型の有限性． https://arxiv.org/abs/1909.09393 https://arxiv.org/pdf/1909.09393 [3] Alexander Rubtsov, The Simplest Proof of Parikh’s Theorem via Derivation Trees, 2022. 小さい木への分解と型の重複の除去． https://arxiv.org/abs/2301.00047 https://arxiv.org/pdf/2301.00047 [4] Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir, A Fully Equational Proof of Parikh’s Theorem, BRICS RS-01-28, 2001. https://www.brics.dk/RS/01/28/BRICS-RS-01-28.pdf [5] Zoltán Ésik, Pascal Weil, Algebraic recognizability of regular tree languages, arXiv:cs/0609113. tree automaton / finite algebra recognition の背景． https://arxiv.org/abs/cs/0609113 [6] Javier Esparza, Pierre Ganty, Stefan Kiefer, Michael Luttenberger, Parikh’s Theorem: A simple and direct automaton construction, Information Processing Letters 111(12), 2011, pp.614–619. https://arxiv.org/abs/1006.3825