問い #235

Height-one input extension ## Trigger 全元 alphabet 上の群 word problem $W_G$ と Conway–Krob–Ésik の group identities が同じ Cayley automaton / matrix star を使うことを整理したとき、少数生成元版の height-$1$ 表現から全元 alphabet版へ移る操作が、Conway 理論の input extension と平行であることに気づいた。 ## Idea 有限群 $G$、全射 \[ \eta:A^*\twoheadrightarrow G \] と語 $u\in A^*$ を取る。新しい文字 $c$ を加え、 \[ \eta':(A\sqcup\{c\})^*\twoheadrightarrow G, \qquad \eta'|_A=\eta, \qquad \eta'(c)=\eta(u) \] とする。このとき \[ h_{\mathrm g}(\eta^{-1}(1))\leq1 \quad\Longrightarrow\quad h_{\mathrm g}((\eta')^{-1}(1))\leq1 \] は成立するか。 一般の inverse morphism では、一文字を長い語へ送る置換に star が入り込み、height preservation は自動ではない。この問題は、その置換を「既存の語と同じ作用を持つ新文字の追加」として一段ずつ処理できるかを問う。 ## Goal 肯定的なら、height $1$ が分かっている二生成元版 $A_5$ から60元の全元 alphabet版へ有限回の input extension で移れる。さらに full-alphabet reduction により、$A_5$ が認識する任意の言語の generalized star height が高々 $1$ と従う可能性がある。 ## Conway connection Ésik の automaton identities では、ある finite automaton identity から input extension の identity が従う。Conway の最終予想に現れる「全群元を使う巨大な group identity を少数生成元の symmetric identities で圧縮する」という方向と、本問題は構造的に平行である。ただし通常の正規表現の等式理論から bounded star-depth preservation は直接には従わず、この接続自体は研究問題である。 ## Personal context [[w9v6hw]] の marked generating system 依存性を正面から扱う派生問題。Sin'ya Ryoma から聞いた Conway の最終予想との関係を調べる会話から生まれた。