论文标题
惠勒语言
Wheeler Languages
论文作者
论文摘要
最近引入的Wheeler Graph类，受到给定字符串的Burrows-wheeler Transform（BWT）的启发，它承认有高效的索引数据结构，用于搜索具有给定路径标签的subpath，并提高了burrows-wheeler-wheeler转换的适用性，从字符串转换为语言。在本文中，我们研究了以Wheleer图作为过渡功能所接受的常规语言，并证明了此类语言的确定结果，MyHill_Nerode表征，可决定性和闭合属性。
The recently introduced class of Wheeler graphs, inspired by the Burrows-Wheeler Transform (BWT) of a given string, admits an efficient index data structure for searching for subpaths with a given path label, and lifts the applicability of the Burrows-Wheeler transform from strings to languages. In this paper we study the regular languages accepted by automata having a Wheeler graph as transition function, and prove results on determination, Myhill_Nerode characterization, decidability, and closure properties for this class of languages.
