Kalpana Mahalingam ; Anuran Maity - Watson-Crick conjugates of words and languages

dmtcs:13593 - Discrete Mathematics & Theoretical Computer Science, August 29, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.13593
Watson-Crick conjugates of words and languagesArticle

Authors: Kalpana Mahalingam ; Anuran Maity

    In this work, we explore the concept of Watson-Crick conjugates, also known as $θ$-conjugates (where $θ$ is an antimorphic involution), of words and languages. This concept extends the classical idea of conjugates by incorporating the Watson-Crick complementarity of DNA sequences. Our investigation initially focuses on the properties of $θ$-conjugates of words. We then define $θ$-conjugates of a language and study closure properties of certain families of languages under the $θ$-conjugate operation. Furthermore, we analyze the iterated $θ$-conjugate of both words and languages. Finally, we discuss the idea of $θ$-conjugate-free languages and examine some decidability problems related to it.


    Volume: vol. 27:3
    Section: Combinatorics
    Published on: August 29, 2025
    Accepted on: August 19, 2025
    Submitted on: May 15, 2024
    Keywords: Formal Languages and Automata Theory, Combinatorics

    Consultation statistics

    This page has been seen 534 times.
    This article's PDF has been downloaded 420 times.