computer-science - オートマトン理論は死んだ？

Question

Automata Theory and Formal Languages で受講したコースが大好きだったので、当然のことながら、コースの基になった本が書かれてから何が起こったのかを知るためにインターウェブを調べ始めました。

私が発見したのは、私がよく知らないもののリストが非常に短いように思われるということでした. たとえば、件名のウィキペディアエントリのオートマトンのリストから、半分はコースでカバーされ、残りの半分はコースでカバーされていない 1 つの言語にほとんど関連していました。

さらに、理論の応用について調べたところ、ほぼ同じ結果が得られました。プログラミング言語の構文、コンパイラ、テキスト検索、そして....それだけです。

それで、それは本当に死んでいますか？それとも進化し続けますか？理論の新しいアプリケーションはありますか?

score 19 · Accepted Answer

オートマトンは本当に便利です。私は 20 年近く前にソフトウェアエンジニアリングとコンピューターサイエンスの学位を取得しました。最初のコースの 1 つはモデルオブマシンで、FSA をカバーし、旋盤、計算可能性、停止問題などに少し挑戦しました。

誰もが、このコースは退屈である、無関係である、難しすぎる、または無意味であると考えていました。円と円弧は誰にとってもほとんど意味がありませんでした。円と円弧だけのテープのポイントは何ですか? ハードディスクの何が問題になっていますか？コースの最後に、講師はアンケートを行いました。このコースは、1 か月後、1 年後、10 年後にどの程度役立つと思いますか。それから、私はそれらすべてに役に立たないと答えました。時間の経過とともに有用性が増し、「非常に有用」で終わります

私は日常の仕事でオートマトンをたくさん使ってきましたが、オートマトンは特定のクラスの問題に適したツールであり、他に競合するものはほとんどありません. 数百万の単語リストとカテゴリデータを圧縮するためにそれらを使用し (わかりました、非常に平凡です)、シンボルが複雑なオブジェクトであり、状態遷移が述語である拡張機能も実装しました。これにより、複雑なルールセットを決定論的 FST にコンパイルし、すべてのルールを冗長な計算なしで同時に決定論的に評価することができました。

私の投票は、まだ関連性があります!

score 4 · Accepted Answer

オートマトンと形式言語は、定期的に改善される正規表現、パーサー、コンパイラ、仮想マシンなどの基盤です。

また、定理証明者の領域では、プログラムまたはプロトコルがそのふりをしたことを達成することを証明することを目的としたプログラムチェックを行う必要があります。このドメインは重要であり (投票機ソフトウェア、銀行取引、車両のセキュリティシステムなど)、まだ開発中です。

いいえ、オートマトン理論と形式言語は死んでいません!

score 3 · Accepted Answer

それは死んでいない、より多くの「スタッドに出されている」-それは特に活発な研究トピックではなく、他の人の基礎としてより多く使用されている単純な形式主義です。

XMLスキーマに関するHenryThompsonの作業は、オートマトン理論を使用および拡張しています。

多くの組み込みソフトウェアプロジェクトは、オートマトンに関連する有限状態マシンを多用しており、それらを使用するための技術のいくつかは、オートマトン理論を利用または拡張しています。

パイ計算は、双模倣の概念でオートマトン理論を拡張し、並行プロセスを分析するための機能を追加します。これは、私が大学で学んだオートマトン理論に最も近い最近の研究です。

score 1 · Accepted Answer

量子コンピューティングやハイパーコンピューティングなどのコンピューティングの新しい分野が開かれるにつれて、オートマトン理論や進化型オートマトンや計算、セルオートマトンなどからの新しいアプリケーション要件、要件、理論的繁殖が生まれると思います。

死んでいるとは思いませんが、とりあえず少し寒いです。

score 1 · Accepted Answer

オートマトン理論は、人々が気付かないうちに多くの分野に関与していると思います。たとえば、暗号解読と暗号解読でのアプリケーションを見ることができます。

score 0 · Accepted Answer

多くのプロセス制御は理論に大きく基づいています。特に制御システムの堅牢性を証明するという点で。

score 0 · Accepted Answer

ワークフロープロセスを見て、説明されている概念とパターンを形式化する際にオートマトン理論をどのように使用できるかを確認してください。ワークフローパターン

score 0 · Accepted Answer

私が数年前に出会った新しいテクニックの 1 つは、Parsing Expression Grammars、別名 PEG、別名 Packrat Parsing と呼ばれるものです。Bryan Ford は、 http://pdos.csail.mit.edu/~baford/packrat/で見ることができるいくつかの作業を行いました。

これは基本的にトップダウンの再帰降下パーサーであり、その利点の 1 つは字句解析と意味解析を 1 つのステップで実行できることです。

PEG は CFG と比較して、PEG は文脈自由言語の解析により適しているのに対し、CFG は文脈自由言語の生成により適しています。

score 0 · Accepted Answer

理論を死んだものと見なすのではなく、アプリケーションにとって非常に実用的になり、理論を超えて移動したと考えてください。理論と応用の架け橋となる優れた本は、Miro Samek の「Practical Statecharts in C/C++」です。現在、第 2 版が入手可能ですが、私は読んでいません。しかし、初版に欠けているものは何も見つかりませんでした。今日に至るまで、私がこれまでに読んだ中で最も価値のあるテキストの 1 つだと思います。

computer-science - オートマトン理論は死んだ？

9 に答える 9

Related

Reference