• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Mathematical Foundations of Computer Science >A Unified Construction of the Glushkov, Follow, and Antimirov Automata
【24h】

A Unified Construction of the Glushkov, Follow, and Antimirov Automata

机译：Glushkov的统一建设，关注和Antimirov Automata

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A number of different techniques have been introduced in the last few decades to create ε-free automata representing regular expressions such as the Glushkov automata, follow automata, or Antimirov automata. This paper presents a simple and unified view of all these construction methods both for unweighted and weighted regular expressions. It describes simpler algorithms with time complexities at least as favorable as that of the best previously known techniques, and provides a concise proof of their correctness. Our algorithms are all based on two standard automata operations: epsilon-removal and minimization. This contrasts with the multitude of complicated and special-purpose techniques previously described in the literature, and makes it straightforward to generalize these algorithms to the weighted case. In particular, we extend the definition and construction of follow automata to the case of weighted regular expressions over a closed semiring and present the first algorithm to compute weighted Antimirov automata.
机译：在过去的几十年中，已经引入了许多不同的技术，以创建代表Glushkov Automata，遵循自动机或Antimirov Automata等正则表达式的ε-无自动机。本文介绍了对未加权和加权正则表达式的所有这些施工方法的简单统一视图。它描述了具有时间复杂性的更简单的算法，至少与最佳先前已知的技术一样有利，并且提供了简明的正确性证明。我们的算法都基于两个标准自动机操作：epsilon - 去除和最小化。这与先前在文献中描述的多种复杂和专用技术形成对比，并且使得简直于将这些算法概括为加权案例。特别是，我们将遵循自动机的定义和构造扩展到封闭的精彩的加权正则表达式的情况，并呈现第一种计算加权Antimirov Automata的算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号