【24h】

TAL Recognition O(M(n~2)) Time

机译:TAL识别时间O(M(n〜2))

获取原文
获取原文并翻译 | 示例
       

摘要

We propose an O(M(n~2)) time algorithm for the recognition of tree adjoining languages (TALs), where n is the size of the input string and (M(k) is the time needed to multiply two k×k Boolean matrices. Tree adjoining grammars are formalisms suitable for natural language pro- cessing and have received enormous attention in the past among not only natural language processing researchers but also algorithms designers. The first polynomial time algorithm for TAL parsing was proposed in 1986 and had a run time of O(n~6). Quite recently, an O(n~3M(n)) algorithm has been proposed. The algorithm presented in This paper improves the run time of the recent result using an entirely Different approach.
机译:我们提出了一种O(M(n〜2))时间算法来识别树邻接语言(TAL),其中n是输入字符串的大小,(M(k)是将两个k×k相乘所需的时间布尔矩阵。树邻接语法是适用于自然语言处理的形式主义,在过去不仅受到自然语言处理研究人员的欢迎,而且受到算法设计者的广泛关注。1986年提出了第一种用于TAL解析的多项式时间算法,该算法具有O(n〜6)的运行时间最近,人们提出了一种O(n〜3M(n))算法,本文提出的算法使用完全不同的方法改善了最近结果的运行时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号