A new approach to regular & indeterminate strings
Louza, F.A., Mhaskar, N. and Smyth, W.F. (2021) A new approach to regular & indeterminate strings. Theoretical Computer Science, 854 . pp. 105-115.
*Subscription may be required
Abstract
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 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.
Item Type: | Journal Article |
---|---|
Murdoch Affiliation(s): | School of Engineering and Information Technology |
Publisher: | Elsevier BV |
Copyright: | © 2020 Elsevier B.V. |
URI: | http://researchrepository.murdoch.edu.au/id/eprint/59309 |
![]() |
Item Control Page |