论文标题
定期和不确定字符串的新方法
A New Approach to Regular & Indeterminate Strings
论文作者
论文摘要
在本文中，我们提出了一个新的，更合适的定义，对常规和不确定的字符串。一个常规字符串是一个对字符串的“同构”的字符串，其条目全部由一个字母组成，但它本身可能包括包含多个字母的条目。不定期的绳子是不确定的。首先，我们提出了一个新模型来表示字符串的定期或不确定的弦，然后继续描述线性时间算法，以确定字符串$ x = x [1..n] $是否是常规的，如果是的，则用词典图（lex-least）字符串$ y y y y $替换为单一字母。此外，我们将字符串的规律性连接到图表上的横向闭合问题，在我们的特殊情况下可以有效地解决该问题。然后，我们介绍了字符串的可行alindrome数组MP的想法，并证明每个可行的MP都对应于某些（常规或不确定）字符串。我们描述了一种构建与给定的MP相对应的字符串$ x $的算法，同时确保只要可能的$ x $是常规的，如果是的，则为Lex-Least。最后一部分概述了有关常规和不确定字符串的观点所建议的新研究指示。
In this paper we propose a new, more appropriate definition of regular and indeterminate strings. A regular string is one that is "isomorphic" to a string whose entries all consist of a single letter, but which nevertheless may itself include entries containing multiple letters. A string that is not regular is said to be indeterminate. We begin by proposing a new model for the representation of strings, regular or indeterminate, then go on to describe a linear time algorithm to determine whether or not a string $x = x[1..n]$ is regular and, if so, to replace it by a lexicographically least (lex-least) string $y$ whose entries are all single letters. Furthermore, we connect the regularity of a string to the transitive closure problem on a graph, which in our special case can be efficiently solved. We then introduce the idea of a feasible palindrome array MP of a string, and prove that every feasible MP corresponds to some (regular or indeterminate) string. We describe an algorithm that constructs a string $x$ corresponding to given feasible MP, while ensuring that whenever possible $x$ is regular and if so, then lex-least. A final section outlines new research directions suggested by this changed perspective on regular and indeterminate strings.
