String matching restricted by regular expressions and context free grammars

• Grant number: 13/19989-2
• Support Opportunities: Scholarships abroad - Research
• Start date: December 15, 2013
• End date: December 14, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Guilherme Pimentel Telles
• Grantee: Guilherme Pimentel Telles
• Host Investigator: Peter F. Stadler
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Leipzig University, Germany

Abstract

We propose investigating the problems of aligning strings restricted by regular expressions and context free grammars. These problems are related to the exact string matching problem, to the inexact string matching problem and also to the sequence alignment problem. We believe that it is possible to obtain more efficient algorithms, in time and memory usage, or fast heuristics for solving these problems. Such problems are related to the task of comparing biological sequences that contain motifs that can be represented by regular expressions and context free grammars. (AU)