PhD Defense

Franziska Biegler

Decomposition and Descriptional Complexity of Shuffle on Words and Finite Languages

Date:
Time:
Place:
Supervisor:
Thesis Examiners:

Extra-Departmental
Examiner:
External Examiner:

Wednesday, September 02, 2009
9:30 a.m.
Middlesex College, Room 320
Dr. Mark Daley / Dr. Kai Salomaa
Dr. Lucian Ilie
Dr. Sheng Yu

Dr. Stuart Rankin (Mathematics)
Dr. Michael Domaratzki (Univ. of Manitoba)

Abstract:

We investigate various questions related to the shuffle operation on words and finite languages. The shuffle of two words u and v is defined as the set of all words obtained by interleaving u and v, which is extended to languages in the natural way.

The shuffle decomposition into finite languages is, in general not unique. That is, it is possible for the shuffle of L1 and L2 to be equal to the shuffle of L3 and L4. However, if all four languages are singletons, it follows by a result of Berstel and Boasson, that the solution is unique; that is {L1, L2 } = {L3, L4}. We extend this result to show that if L1 and L2 are arbitrary finite sets and L3 and L4 are singletons (with at least two letters in each), the solution is unique. This is strong as we cannot let all four be arbitrary finite sets.

We furthermore investigate the size of shuffle automata for words. It was recently shown that there exist words u and v such that the minimal shuffle DFA for u and v requires an exponential number of states. We study the size of shuffle DFAs for restricted cases of words, namely when the words u and v are both periods of a common underlying word. We show that, when the underlying word obeys certain conditions, then the size of the minimal shuffle DFA for u and v is at most quadratic.

Moreover we provide an efficient algorithm, which decides for a given DFA A and two words u and v, whether the shuffle of u and v is a subset of L(A).

Also from this web page: