オートマトン補完

理論計算機科学と形式言語理論において、オートマトン補集合^[^明確化^]とは、別のオートマトンによって拒否された単語を正確に受け入れるオートマトンを計算する問題です。正式には、正規言語L を認識するオートマトンAが与えられた場合、 Lにない単語、つまりLの補集合を正確に認識するオートマトンを計算します。

補完操作に関する次のようないくつかの質問が研究されています。

計算の複雑さ: オートマトンが与えられた場合、補言語のオートマトンを計算する複雑さはどれくらいでしょうか?
状態の複雑さ: 補集合を認識するオートマトンの状態の最小数はどれくらいでしょうか?

決定論的有限オートマトン

非決定性有限オートマトン

非決定性有限オートマトンでは、補オートマトンの状態複雑度は指数関数的になることがある。 ^[1]一義的オートマトンの場合も下限値は既知である。^[2]

双方向オートマトン

補完性は双方向オートマトンでも研究されてきた。^[3]

Büchiオートマタ付き

参照

状態の複雑さ

参考文献

^ Birget, Jean-Camille (1993). 「単語の部分順序、正規言語の最小要素、および状態の複雑さ」.理論計算機科学. 119 (2): 267–291. doi :10.1016/0304-3975(93)90160-U. ISSN 0304-3975.
^ Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (2022年2月12日). 「通信複雑性による曖昧でないオートマトンの下界」. arXiv : 2109.09155 [cs.FL].
^ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007-08-01). 「双方向有限オートマトンを補完する」.情報と計算. 205 (8): 1173–1187. doi : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401.

[Birget1993b-1] Birget, Jean-Camille (1993). 「単語の部分順序、正規言語の最小要素、および状態の複雑さ」.理論計算機科学. 119 (2): 267–291. doi :10.1016/0304-3975(93)90160-U. ISSN 0304-3975.

[GoosKieferYuan2022-2] Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (2022年2月12日). 「通信複雑性による曖昧でないオートマトンの下界」. arXiv : 2109.09155 [cs.FL].

[3] Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007-08-01). 「双方向有限オートマトンを補完する」.情報と計算. 205 (8): 1173–1187. doi : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401.