問い #247

word gameとstar height 1予想 ## Trigger Inoue の発表（2026-07-30）で聞いた「語の上の subtraction game」から。局面は \(w \in \Sigma^*\)、固定した \(S \subseteq \Sigma^+\) に対し合法手は接頭辞除去 \(sx \to x\)（\(s \in S\)）、normal play。P-局面全体 \(P_S\) は well-founded グラフの kernel であり、一意に \[ \Sigma^* \setminus P_S = S\,P_S \] を満たす。これは Larsson の invariant subtraction game の \(\star\)-operator（\(S^\star := P_S \setminus \{\varepsilon\}\)）を可換モノイド \(\mathbb{N}^d\) から自由モノイド \(\Sigma^*\) へ非可換化したもの。関連メモは Inoue-2026-07-30/star-operator.md。 ## Idea **予想 (FGS: finite game-star conjecture)**: \(S\) が有限なら \(P_S\) の generalized star height は 1 以下。 分かっていること: - \(S\) 有限 \(\Rightarrow P_S\) は正規。ただし像 \(\mathrm{KFin}_\Sigma = \{P_S : S \text{ finite}\}\) は \(\mathrm{REG}\) の真部分クラス（例: \(P=\{\varepsilon\}\) は実現不能）。 - \(S\) が prefix code の場合は証明済み: \(T := \Sigma^* \setminus S\Sigma^*\) と置くと greedy 分解の一意性から \[ P_S = (S^2)^* T, \qquad N_S = S (S^2)^* T \] で、\(S\) 有限なら \(S^2, T\) は star-free なので \(h_{\mathrm{gen}} \le 1\)。 - 一般の有限 \(S\) では元同士が接頭辞として重なりゲーム木が分岐し、\(\mathbf{1}_P(w) = \neg \bigvee_{w=sx,\, s\in S} \mathbf{1}_P(x)\) という bounded NOR 固定点になる。この分岐を一段の Kleene star に flatten できるかが本体。 ## Goal - (FGS) が正なら \(\mathrm{KFin}_\Sigma \subseteq \mathcal{H}_1\) という大域定理。 - 逆に \(h_{\mathrm{gen}}(P_S) \ge 2\) となる有限 \(S\) が一つでもあれば、それ自体が Generalized Star Height 問題（高さ 2 以上の正規言語の存在）の否定的でない方向の解決例になる。どちらに転んでも価値がある。 ## Personal context - Generalized Star Height の既存ノート（STAR_FREE_PREFIX_CODE_COMPLEMENT_STAR_THEOREM.md, ONE_SIDED_STAR_FLATTENING_AND_LOOP_EXACT_HEIGHT.md）の prefix-code greedy 分解・一方向 flattening \((X^*Y)^* = \{\varepsilon\} \cup (X \cup Y)^* Y\) がそのまま道具になる。 - 関連未解決問題（発表者情報）: WordWythoff（\(S = a^+ \cup b^+ \cup \{|w|_a = |w|_b\}\)）の N-局面が context-free かは不明。 ## Machine evidence: S = {a, b, ab} は height ≤ 1（⚪COMPUTED, 2026-08-07） Fugu工場（mac miniの進化型探索ループ。検証器はゲームDP＋Brzozowski微分の式評価器、kernel方程式とprefix-code定理式による独立検証つき）が、重なりあり（a が ab の prefix）の最初のインスタンス S = {a, b, ab} で height-1 表現を発見した: P_S = (bb)* ( 1 | aa(aa)*(1 | bΣ*) | ba(aa)*(1 | bΣ*) ) DSL原文 `(bb)*(1|aa(aa)*(1|b~0)|ba(aa)*(1|b~0))`。長さ≤12の全語（8191語）と乱択30000語（長さ≤300）でP-position判定と完全一致、star nesting depth は 1。**ラベルは⚪COMPUTED（証明ではない）**。証明化は未着手。生データ: mini `~/fugu-factory/lottery/out/survivors.jsonl`。 ## 人物注記（2026-08-09） 本瓶の Inoue（`discussed_with` および Trigger の「Inoue の発表」）は**名古屋大学の井上助教**を指す。Proxima Technology の井上亜星氏（AI for Math 勉強会第2回登壇者）とは**全くの別人**。2026-08-09 にAIセッションが両者を混同する事故があったため明記する。なお本予想は gsh_bootstrap（public repo）とは無関係の話題であり、同 repo に混ぜない。