Journal article
A new approach to regular & indeterminate strings
Theoretical Computer Science, Vol.854, pp.105-115
2021
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.
Details
- Title
- A new approach to regular & indeterminate strings
- Authors/Creators
- F.A. Louza (Author/Creator)N. Mhaskar (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.854, pp.105-115
- Publisher
- Elsevier BV
- Identifiers
- 991005544189507891
- Copyright
- © 2020 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
42 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science