Regular Languages meet Prefix Sorting
Regular Languages meet Prefix Sorting
复制标题
DOI：
10.1137/1.9781611975994.55
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Jarno N. Alanko;G. D’Agostino;A. Policriti;N. Prezza
中科院分区：
文献类型：
--
作者：
Jarno N. Alanko;G. D’Agostino;A. Policriti;N. Prezza
可以说，通过前缀（或后缀）排序索引字符串是过去几十年来最成功的算法技术之一。索引可以扩展到语言吗？本文的主要贡献是启动对自动机接受的普通语言子类的研究，其状态可以前缀分类。从最近的Wheeler Graph [Gagie等人，TCS 2017]开始，该概念自然扩展了前缀排序的概念以标记为图形，我们研究了Wheeler语言的属性，即接受接受惠勒接受的常规语言。有趣的是，我们将这个家庭描述为带有共同学序列的普通语言的自然延伸：分类时，属于Wheeler语言的字符串被划分为有限数量的共同摄影间隔，每种间隔都由单个单个元素形成myhill-nerode等效类。此外：（i）我们证明，每个Wheeler NFA（WNFA）带有$ n $ state的每个Wheeler NFA（WNFA）承认同等的Wheeler DFA（WDFA），最多最多$ 2N-1- | \ sigma | $ nate可以在$ o（n ^3）$时间。这与一般的NFA形成了鲜明的对比。 （ii）我们描述了一种二次算法，用于前缀sort the WDFA的适当超集，$ o（n \ log n）$ - 时间在线算法以对无循环进行acyclic wdfas和最佳的线性离线算法，以对一般的WDFA进行排序。通过贡献（i），我们的算法也可以用来以中等价格将自动机尺寸加倍的中等价格索引任何WNFA。 （iii）我们提供了一种最小化定理，该定理表征了最小的WDFA识别任何输入WDFA的语言。相应的构建算法在无环的情况下以最佳线性时间和$ O（n \ log n）$时间在一般情况下运行。 （iv）我们展示了如何在几乎最佳时间内计算与任何无环DFA的最小WDFA。
Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages? The main contribution of this paper is to initiate the study of the sub-class of regular languages accepted by an automaton whose states can be prefix-sorted. Starting from the recent notion of Wheeler graph [Gagie et al., TCS 2017]-which extends naturally the concept of prefix sorting to labeled graphs-we investigate the properties of Wheeler languages, that is, regular languages admitting an accepting Wheeler finite automaton. Interestingly, we characterize this family as the natural extension of regular languages endowed with the co-lexicographic ordering: when sorted, the strings belonging to a Wheeler language are partitioned into a finite number of co-lexicographic intervals, each formed by elements from a single Myhill-Nerode equivalence class. Moreover: (i) We show that every Wheeler NFA (WNFA) with $n$ states admits an equivalent Wheeler DFA (WDFA) with at most $2n-1-|\Sigma|$ states that can be computed in $O(n^3)$ time. This is in sharp contrast with general NFAs. (ii) We describe a quadratic algorithm to prefix-sort a proper superset of the WDFAs, a $O(n\log n)$-time online algorithm to sort acyclic WDFAs, and an optimal linear-time offline algorithm to sort general WDFAs. By contribution (i), our algorithms can also be used to index any WNFA at the moderate price of doubling the automaton's size. (iii) We provide a minimization theorem that characterizes the smallest WDFA recognizing the same language of any input WDFA. The corresponding constructive algorithm runs in optimal linear time in the acyclic case, and in $O(n\log n)$ time in the general case. (iv) We show how to compute the smallest WDFA equivalent to any acyclic DFA in nearly-optimal time.