| EPSRC Reference: |
GR/S53503/01 |
| Title: |
Applications of Automata and Languages in the Theory of Pattern Classes of Permutations |
| Principal Investigator: |
Ruskuc, Professor N |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics and Statistics |
| Organisation: |
University of St Andrews |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 February 2004 |
Ends: |
31 January 2007 |
Value (£): |
157,723
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Pattern classes of permutations arise naturally when considering various sorting devices (such as stacks) connected in various ways. Every pattern class can also be described in terms of avoiding a collection of patterns (basis). A number of natural algorithmic and complexity questions arise: determining the enumeration sequence or its asymptotic behaviour, membership testing, determining the basis, etc. Recent advances by the PI, Atkinson and RA include new connections between pattern classes and regular languages, major progress towards a structure theory, and an in-depth analysis of antichains. In this project we want to build on these recent advances, in two major ways. Firstly, we want to implement algorithms arising from our investigations, and use them to treat a number of open problems. Secondly, we would like to develop the full potential of our theory, by extending it to languages other than regular, and to fundamental constructions such as unions, merges and wreath products. As a result of our work we hope to have a structure theory of pattern classes, unifying its Computer Science and Combinatorial aspects, a series of algorithms for dealing with pattern classes based on this theory, and a suite of implementations, available to other researchers in the area.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.st-and.ac.uk |