Parikh Matrices – Complexity and Applications: investigating the complexity of identifying the existence of a sequence associated to a Parikh matrix

Loughborough University is a top-ten rated university in England for research intensity (REF2014). In choosing Loughborough for your research, you’ll work alongside academics who are leaders in their field. You will benefit from comprehensive support and guidance from our Graduate School, including tailored careers advice, to help you succeed in your research and career.

Project Detail:

This project is part of a 5-student centre for doctoral training at Loughborough University within the area of Geometry and its applications.

With an increasing amount of data available in the world, the need for faster data processing and faster data transmission is paramount. This usually comes in the form of a trade-off where accuracy is lowered to the benefit of a faster manipulation of the data.

The Parikh vector associated to a sequence corresponding to any data stream is an established representation that provides such a mechanism by holding information about the number of occurrences of every symbol in the sequence. More recently, this representation was enhanced to reduce the ambiguity that the previous one was exhibiting (that is, the same Parikh vector is associated to a very large number of different sequences), leading to the concept of a so-called Parikh Matrix.

Parikh matrices contain information about the number of all lexicographically increasing sub-structures of a sequence. While such a representation is still not uniquely associated to a given sequence, it preserves much of the desirable compactness of Parikh vectors, and it drastically reduces their ambiguity. Parikh matrices are not fully understood at present, and we intend to study both their capability of data modelling in application domains such as data compression, online streaming and bioinformatics, as well as their theoretical properties. One of the main problems we are interested in investigating in this project refers to the complexity of identifying the existence of a sequence associated to a Parikh matrix. The problem is over 15 years old, and the only known algorithms to solve it take time proportional to the size of the word, instead of its representation. We plan to study this question using techniques from different areas, such as algebraic geometry, and expect that such approaches will also strengthen our understanding of other basic properties as well as applications of the concept.

Entry requirements:

Applicants should have, or expect, a first class degree (or equivalent) in Computer Science or Mathematics, or a related subject. A relevant Master’s degree and/or experience in one or more of the following will be an advantage: Theoretical Computer Science (e.g., Formal Language Theory, Complexity Theory, Algorithms), Discrete Mathematics, Algebraic Geometry.

Contact details:
Dr Robert Mercas, [Email Address Removed], 01509222545

Dr Daniel Reidenbach, [Email Address Removed], 01509222939

How to apply:

Applications should be made online at http://www.lboro.ac.uk/study/apply/research/. Under programme name, select ‘Computer Science’

Quote reference: GEOM5/CO/RM
Note that applicants to one of the projects in this cohort will automatically be considered for other projects.

Reference: GEOM5/CO/RM
Start date: 1/10/2017
Closing date: 5/5/17

Supervisors:
Primary supervisor: Dr Robert Mercas
Secondary supervisor: Dr Daniel Reidenbach