Advanced search
Start date
Betweenand

String matching restricted by regular expressions and context free grammars

Grant number: 13/19989-2
Support type:Scholarships abroad - Research
Effective date (Start): December 15, 2013
Effective date (End): 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: Peter F. Stadler
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Local de pesquisa : 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)