Header menu link for other important links
X
Context-free systems with a complementarity relation
Published in
2011
Pages: 194 - 198
Abstract
Motivated by the studies on Watson-Crick finite automata and Watson-Crick L systems, we introduce a generative device known as a Watson-Crick context-free system (WKCFS) making use of a complementarity relation and a context-free type of rewriting on double-stranded strings with the symbols in the string in the lower strand complementary to the symbols of the string in the upper strand. The language generated by a WKCFS is the set of all strings in the upper strands of the double-stranded strings (u, v) generated such that the strings u, v are of the same length and the corresponding symbols in the strings u, v are related by the complementarity relation. We compare the generative power of WKCFS with some families of languages and also certain variants of Watson-Crick finite automata. © 2011 IEEE.
About the journal
JournalProceedings - 2011 6th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2011
Open AccessNo
Concepts (9)
  •  related image
    COMPLEMENTARITY RELATIONS
  •  related image
    Context-free
  •  related image
    L-SYSTEMS
  •  related image
    PURE CONTEXT-FREE GRAMMAR
  •  related image
    WATSON-CRICK COMPLEMENTARITY
  •  related image
    WATSON-CRICK FINITE AUTOMATA
  •  related image
    Computation theory
  •  related image
    Finite automata
  •  related image
    Context free languages