word gameとstar height 1予想

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^*$ へ非可換化したもの。

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 の既存ノートの 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）

進化型探索ループ（検証器はゲーム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（証明ではない）。証明化は未着手。

@misc{sumire:2610.00003:12:v4,
  author = {hora},
  title = {{word gameとstar height 1予想}},
  year = {2026},
  note = {SUMIRE:2610.00003/12, v4},
  url = {https://sumire.aiformath.jp/p/2610.00003/n/12/v/4}
}