Constrained Coding for Context-Free Languages with Applications to Genetic Sequence Modelling

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 (Delest-Schutzenberger-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.