Refreshments will be served
Speaker: Neerja Mhaskar
Time/Place: Monday February 16, 2015, 7:00-8:00pm, in Del Norte 1545
Title: Repetition in Strings and String Shuffles.
Bio: Neerja Mhaskar is a PhD candidate in Computer Science at McMaster University. She did her masters in Engineering Science with Information Technology as major at Louisiana State University, and her undergraduate in Mechanical Engineering at Jawaharlal Nehru Technological University, Hyderabad, India. Her research interest is in the general area of string algorithms and combinatorics on words with an emphasis on computational complexity of the problems.
Abstract: There are several areas of emerging and continued interest such as bioinformatics, text searching, data compression, signal processing, abstract algebra which benefit from research in the general area of string algorithm.
A string (word) is traditionally a sequence of characters. A string (word) is said to be non-repetitive (square-free) if it does not contain a subword of the form vv. Given a list of alphabets L=L_1,L_2,…,L_n, we investigate the question of generating non-repetitive words w = w_1w_2,…,w_n$, such that the symbol w_i is a letter in the alphabet $L_i$. This problem has been studied by several authors (e.g., Grytczuk et al., Shallit), and it is a natural extension of the original problem posed and solved by A. Thue. In the first half of the talk, I will present our work on this problem, where we show that such strings exist over many classes of lists and suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.
In the remainder of the talk, I will present our contribution in the area of string shuffles. A shuffle of two strings is said to be formed by interleaving the characters into a new string in a way that keeps the characters of each string in order. In the paper “String Shuffle: Circuits and Graphs” we show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y, is not in AC^0, but it is in AC^1. The fact that shuffle is not in AC^0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et~al., while the fact that it is in AC^1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.