论文标题
关于正式语言理论中的准排队的使用
On the Use of Quasiorders in Formal Language Theory
论文作者
论文摘要
在本文中，我们在单词上使用Quasiorders来提供有关正式语言理论中两个研究的问题的新观点：确定语言包容性并操纵普通语言的有限自动机表示。首先，我们提出了一个基于通用的准排出者的框架，该框架与不同的类别实例化时，会产生不同的算法（其中一些新算法）来确定语言包含。然后，我们实例化此框架，以设计有效的算法，用于搜索语法压缩文本的正则表达式。最后，我们定义了一个基于Quasiorder的自动机构构造的框架，以提供有关残留自动机的新观点。
In this thesis we use quasiorders on words to offer a new perspective on two well-studied problems from Formal Language Theory: deciding language inclusion and manipulating the finite automata representations of regular languages. First, we present a generic quasiorder-based framework that, when instantiated with different quasiorders, yields different algorithms (some of them new) for deciding language inclusion. We then instantiate this framework to devise an efficient algorithm for searching with regular expressions on grammar-compressed text. Finally, we define a framework of quasiorder-based automata constructions to offer a new perspective on residual automata.
