Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A new approach to regular & indeterminate strings

Texto completo
Autor(es):
Louza, Felipe A. [1] ; Mhaskar, Neerja [2] ; Smyth, W. F. [2, 3, 4]
Número total de Autores: 3
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
Número total de Afiliações: 4
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