On the Complexity of Parsing Ill-formed Inputs

概要

論文の詳細を見る
This paper gives an analysis of time and space complexities of parsing ill-formed inputs. So far it is known that any context-free langauge can be parsed by an efficient algorithm, e.g., Earley's method, in O(n^3) time complexity. This complexity seems not to be realized for parsing ill-formed inputs. Two modified efficient approaches based on chart parsing methodology are considered: a simple method with no consideration of full context and a method with consideration of full context. We show that inputs with the following common types of errors: extra-word, omitted-word and substituted-word, can be parsed by these two algorithms in O(n^3ε^3) and O(n^<2(p+ε)>) respectively, where n is the length of the input string, p is the length of the longest production and ε is the number of errors in the input. The space complexities of these approaches are shown to be propositional to n^3ε^2 and n^<2(p+ε)> respectively.
一般社団法人情報処理学会の論文
1994-10-21