Constrained coding for context-free languages with applications to genetic sequence modelling

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Constrained coding is a combinatorial technique for converting unrestricted sequences into sequences with a predefined set of properties. Traditionally, applications of this coding technique are confined to sequences drawn from regular languages. Nevertheless, there exist many families of words that cannot be described within this narrow setting. We propose to reformulate and extend a set of results from constrained coding theory in order to analyze sequences from context-free languages. For the purpose of computing the capacity of the context-free constraints, we use the DSV (Delést-Schützenberger- Viennot) theory for grammars and attribute grammars. We illustrate the new approach on a problem related to enumerating RNA secondary structures that satisfy certain stability requirements.

Original languageEnglish (US)
Title of host publicationProceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007
Pages1686-1690
Number of pages5
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event2007 IEEE International Symposium on Information Theory, ISIT 2007 - Nice, France
Duration: Jun 24 2007Jun 29 2007

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101

Other

Other2007 IEEE International Symposium on Information Theory, ISIT 2007
Country/TerritoryFrance
CityNice
Period6/24/076/29/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Constrained coding for context-free languages with applications to genetic sequence modelling'. Together they form a unique fingerprint.

Cite this