Buchi Automatonあれこれ 思いつき次第追記していきます Emptiness checking Buchi Automatonが受理する言語が空でない 初期状態から到達可能かつサイクル上にある終状態が存在する. 効率的なアルゴリズム オートマトンを有向グラフとみなし強連結成分に分け…

Tree automata 今回は(one way) tree automataの話です. ざっくり直感的な説明をするなら、木構造をした入力テープ上を走査(ただし今回はone wayなので逆走したりはしない)して、そこに書かれたアルファベットを入力として読んでいき状態遷移するようなオー…