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.

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