Solutions to the involution language equation

Abstract

In this paper, we study a generalization of the classical notions of language equations: involution language equations. This notion is motivated by DNA strand design where Watson–Crick complementarity can be modular as an antimorphic involution function. Characterizations of words u and languages A and B which satisfy the equation θ(u)B=Au are obtained. For a language L, solutions of the equation θ(L)B=AL are considered. We also study the characteristics of L _θ-commutative equivalent languages.

Keywords:

• antimorphic involution
• primitive words
• involution palindrome words

2000 AMS Subject Classifications :

• 68Q70
• 68R15

Acknowledgements

The authors would like to thank the referees for their careful reading of the manuscript and useful suggestions.