Transforming strings by rearrangement operations

• Grant number: 19/13312-7
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2020
• End date: May 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Carla Negri Lintzmayer
• Grantee: Gustavo da Silva Teixeira
• Host Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil

Abstract

In Problems of Transforming Strings (or Sorting Permutations) by Rearrangement Operations, given two sequences of symbols - where each symbol appears the same number of times in each sequence - and a set of allowed rearrangement operations, one wants to find a sequence of lowest cost containing rearrangement operations that transforms one symbol sequence into the other.The cost of this optimal sequence of operations would represent the distance between the two given sequences of symbols.If we consider that the sequences have only one copy of each symbol, we can represent them as permutations, which is the most traditional approach to dealing with the problems of Transforming by Rearrangement Operations.However, another approach assumes that there is at least one symbol that appears more than once within the sequences.In these cases, the sequences are represented by strings.Since the late 1970s, when Gates and Papadimitriou published about bounds for the Pancake Problem (or Sorting Permutations by Prefix Reversals), much work has been done to obtain results for related problems.Efforts aim to find algorithms that return solutions close to the optimal one, since most related problems are NP-hard.However, when comparing the strings approach to the permutations approach, we can still observe the lack of algorithmic results in the literature for the string problems.This Scientific Initiation project aims to study the problems of Transforming Strings by Rearrangement Operations, from the theoretical point of view, to understand the results obtained in the area so far, and to study algorithmic techniques that can help us obtain new results, with the intention of proposing new algorithms for the problems.