A new approach to regular & indeterminate strings

Autor(es)

Louza, Felipe A. ^[1] ; Mhaskar, Neerja ^[2] ; Smyth, W. F. ^{[2, 3, 4]}

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: THEORETICAL COMPUTER SCIENCE; v. 854, p. 105-115, JAN 16 2021.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 17/09105-0 - Ordenação de sufixos e medidas de similaridade entre cadeias
• Beneficiário: Felipe Alves da Louza
• Linha de fomento: Bolsas no Brasil - Pós-Doutorado