ランダム決定論的オートマトン

私は$ G(n、p)$のような無作為グラフの用語に精通しています。$ n
$の頂点を持つ簡単な無向グラフの分布で、各エッジはグラフw.pに現れます。 $ p $。すなわち、各グラフ$ G =(V、E)$は、$
p ^ {| E |} cdot(1-p)^ {{{{| V |} choose {2}}} – | E |} $。特に、$
G(n、 frac {1} {2})$はサイズ$ n $の簡単な無向グラフ上の一様分布です。

今、有限のアルファベット$ Sigma $と自然数$ n $が与えられています。決定論的オートマトン$ A
$を生成するランダムなプロセスがありますか?

  • $ A $に到達可能な州は$ n $あります。
  • $ A $は$ Sigma $に定義されています。
  • $ A $は、他の決定論的オートマトンと同じ確率を持ち、サイズは$ n $〜$ Sigma $です。

言い換えれば、我々は確定的なオートマトンに対して一様な分布$ D( Sigma、n、
frac {1} {2})$を生成する方法を持っていますか?

あなたが私を関連するリファレンスに導くことができれば幸いです。

ベストアンサー

The question is a bit ill-posed, since you did not specify that
equivalent automata should be counted as a single object. Without
that restriction (or the reachability one), the set of all
$n$-state DFAs over a binary alphabet and with starting state $s=1$
has exactly $n^{2n}2^n$ elements, and it is trivial to sample from
this set uniformly, as indicated in the link in my comment,
https://dl.acm.org/citation.cfm?id=3064434

現在、リンクされた論文は、元のものがナイーブな一様分布から引き出されたときに、最小限の等価DFAの予想されるサイズに鋭い境界を与える。バイナリアルファベットの場合、この数量は約$
0.7968n $に集中しています。つまり、$ n/0.7968 $州でDFAをサンプリングして最小化すると、およそ$ n
$到達可能状態のオートマトンが得られます。もちろん、このサンプリング手順が一様であるという主張はなされていない。しかし、リンクされた論文の参照
– 特に https://dl.acm.org/citation.cfm?id=782472
そして http://www.sciencedirect.com/science/article/pii/
S0304397507002861?via%3Dihub
– 後者はあなたの質問に最も関連しているようです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です