文脈自由言語の bottom-up的最小誤り訂正アルゴリズムについて
スポンサーリンク
概要
- 論文の詳細を見る
On the assumption that three types of syntactic errors (the replacement of a symbol by an incorrect symbol, the insertion of an extraneous symbol, or the deletion of a symbol) debasing the strings of a language generated by a context-free grammar can occur arbitrarily many times, there are top-down algorithms that will correct any input string in the fewest possible number of errors (least error correction). However, there has not been any bottom-up algorithm correcting the above three types of errors. In this paper a bottom-up least error correction algorithm for the three types of errors is presented which requires time proprotional to the cube of the length of an input. Also a bottom-up least error correction algorithm which works in less than cubic time is presented, in the case that the number of errors (which are in the three types) in an input can be bound out of the relation to its length.
- 一般社団法人情報処理学会の論文
- 1977-08-15
著者
関連論文
- The Satisfiability Problems for Some Classes of Extended Horn Sets in the Propositional Logic (Mathematical Studies of Information Processing)
- Horn節集合による計算について (数理情報科学の基礎理論と応用)
- Complexity of Some Strategies Proving Theorems in the Propositional Logic (Studies on Computational Complexities and Related Topics)
- 入カ導出を階層化した導出について (計算機科学の数学的基礎)
- 系列パターン認識システムの考え方 : 系列パターンの誤り処理 (時系列パターンの認識システムの研究)
- プッシュダウンオートマトンに対応する無限状態オートマトンの性質 (オートマトン理論と数理言語の研究)
- 文脈自由言語の bottom-up的最小誤り訂正アルゴリズムについて