Indeterminates in London

Today my masters student Joel Helling presented our joint work, Constructing an Indeterminate String from its Associated Graph,  co-authored with P.J. Ryan, W.F. Smyth, at the LSD & LAW 2017 conference. This work started with the visit of W.F. Smyth at CSU Channel Islands in March 2016 – see here, when Joel, Bill and I started working on an initial algorithm designed by Joel; this algorithm computed a labeling for a graph such that any two nodes that shared an edge would also share a label, and would not share a label otherwise. Of course, the easy way to do this is to assign each edge a unique label; but there are better ways of doing it, in the sense that fewer labels may be required (for example, imagine a clique: then a single label would do it). This problem is directly related to indeterminate strings; strings that arise in bio-informatics, where certain positions may consist of several possible symbols. For example, {a,b}ab{a,b,c}{b,c}a, where the first position is not determined (it could be a or b), the second position is a, the third b, the fourth is again not determined (it could be a or b or c), etc. Such strings are well suited to represent genetic
information which often contains “noise”. The paper is now accepted for publication in Elsevier’s journal of Theoretical Computer Science,  as well as presented by Joel at the conference.

I would like to express my gratitude to the British Royal Society for awarding us an exchange grant, CSU Channel Islands / King’s College London, which financed the trip of Joel Helling.

CI Facebook post.

Share

Talk at PSC2016 on paper with Neerja Mhaskar

IMG_2999I just gave a talk at PSC2016 conference in Prague based on a paper with Neerja Mhaskar, Forced repetitions over alphabet lists. This paper explores further the problem posed by Grytczuk in 2010 regarding the construction of non-repetitive strings over alphabet lists where each alphabet has 3 symbols. We use some string combinatorics, as well as an approach based on the Crossing sequences technique from complexity theory. The conference took place at České vysoké učeni technické v Praze – Fakulta stavebni, which is quite a mouthful to say, even for a fellow slav :), and is the Czech Technical University in Prague.

Slides are attached:

Some other pictures:

Share

Talk at LSD2016 in London

20160205_093553It was a great pleasure to give an invited talk at LSD2016, “London Stringology Days,” a yearly meeting of Stringologists. The title of my talk was Some Open Problems in Stringology Related to Alphabet Sizes, a talk connected to my current research, where the following three problems were discussed: (i) Is Square Shuffle still NP-hard over alphabets of size less than 7? (see [doi]); (ii) Can we create non-repetitive lists over alphabet lists where each alphabet is of size 3? (see [doi]); (iii) An interesting Conjecture due to Bill Smyth (see Conjecture 21 in [doi]) related to the association of indeterminates to graph sizes. Stringology is a beautiful field, that gathers scientists interested in bioinformatics, formal languages, compression, big data, and IMG_1783mathematicians who work in combinatorics on words. The conference took place at King’s College, where the British computer pioneer Charles Babbage first demonstrated his prototype difference engine at King’s College in the 1840s, and then donated his machines and designs to the College (they are now in the Science Museum). The telegraph was invented here by Charles Wheatstone, a professor at the College. And not far away, the first commercial radio broadcasts in the world were made by a company that became the BBC. Across the street is the Marconi Building, which later became the headquarters of the English Electric Company, a ground-breaking British manufacturer of computer mainframes in the 1950s and early 1960s. London requires a lifetime to know, it’s architecture is especially beautiful, and my favorite activity is to wonder the streets and take refuge from time to time in a quaint pub.

Share

Neerja Mhaskar and I have a paper presented at PSC 2015

We (Neerja Mhaskar and Michael Soltys) had our paper presented at the Prague Stringology Conference; the paper introduces a new formal framework for Stringology, which consists of a three-sorted logical theory S designed to capture the combinatorial reasoning about finite words:

And these are the slides:

Share