Grammatical Verification for Mathematical Formula Recognition Based on Context-Free Tree Grammar

摘要

This paper proposes the use of a formal grammar for the verification of mathematical formulae for apractical mathematical OCR system. Like a C compiler detecting syntax errors in a source file, we want to havea verification mechanism to find errors in the output of mathematical OCR. A linear monadic context-free treegrammar (LM-CFTG) is employed as a formal framework to define “well-formed” mathematical formulae. A cubictime parsing algorithm for LM-CFTGs is presented. For the purpose of practical evaluation, a verification system formathematical OCR is developed, and the effectiveness of the system is demonstrated by using the ground-truthedmathematical document database InftyCDB-1 and a misrecognition database newly constructed for this study.