EPSRC logo

Details of Grant 

EPSRC Reference: GR/L98640/01
Title: TREE STRUCTURES FOR ALGORITHMIC PROBLEMS ON STRINGS
Principal Investigator: Irving, Dr RW
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: School of Computing Science
Organisation: University of Glasgow
Scheme: Standard Research (Pre-FEC)
Starts: 01 April 1998 Ends: 31 March 2001 Value (£): 51,993
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:  
Summary on Grant Application Form
String processing problems are of increasing importance in computer science and in applications domains such as molecular biology. Among the elegant data structures that have been devised in this context is the suffix tree, which is a form of digital tree that gives an efficient representation of all the substrings of a string, and thereby facilitates fast solutions to many string searching and comparison problems.Comparison trees are classical data structures in computer science with many important uses and applications. Surprisingly, there has been little research into the viability of comparison trees in string searching and comparison problems. But preliminary investigation by the proposer has revealed that such trees, suitably adapted for the context, may well be strongly competitive with suffix trees and other established methodologies such as suffix arrays.A comprehensive theoretical and empirical investigation of the use of search trees in this context is proposed, with a view to identifying their relative strengths and weaknesses, and making software solutions, based on such structures, to practical string problems.
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.gla.ac.uk