| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Fed Uberlandia, Fac Elect Engn, Uberlandia, MG - Brazil
[2] McMaster Univ, Dept Comp & Software, Hamilton, ON - Canada
[3] Murdoch Univ, Sch Engn & Informat Technol, Murdoch, WA - Australia
[4] Kings Coll London, Dept Informat, London - England
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | THEORETICAL COMPUTER SCIENCE; v. 854, p. 105-115, JAN 16 2021. |
| Web of Science Citations: | 0 |
| 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 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. (C) 2020 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 17/09105-0 - Suffix sorting and string similarity measures |
| Grantee: | Felipe Alves da Louza |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |