Kalpana Mahalingam

In this paper, we introduce a new automata called Watson-Crick jumping finite automata, working on tapes which are double stranded sequences of symbols, similar to that of a Watson-Crick automata. This automata scans the double stranded sequence in a discontinuous manner (i.e.) after reading a double stranded string, the automata can jump over some subsequence and continue scanning, depending on the rule. We define some variants of such automata and compare the languages accepted by these variants with the language classes in Chomsky hierarchy. We also investigate some closure properties.

This paper provides an overview of existing approaches to encoding information on DNA strands for biocomputing, with a focus on the notion of Watson-Crick (WK) palindromes. We obtain a closed form for, as well as several properties of WK palindromes: The set of WK-palindromes is dense, context-free, but not regular, and is in general not closed under catenation and insertion. We obtain some properties that link the WK palindromes to classical notions such as that of primitive words. For example we show that the set of WK-palindromic words that cannot be written as the product of two nonempty WK-palindromes equals the set of primitive WK-palindromes. We also investigate various simultaneous Watson-Crick conjugate equations of words and show that the equations have, in most cases, only Watson-Crick palindromic solutions. Our results hold for more general functions, such as arbitrary morphic and antimorphic involutions. © 2009 Springer Science+Business Media B.V.

We investigate the maximum number of distinct palindromic sub-arrays in a two-dimensional finite word over a finite alphabet (Formula Presented). For any finite array in (Formula Presented), we find an upper bound for the number of distinct palindromic sub-arrays and improve it by giving a tight bound on the maximum number of distinct palindromes in an array in (Formula Presented) for (Formula Presented). We then, propose a better upper bound for any finite array in(Formula Presented).

We investigate the maximum number of distinct palindromic sub-words in a two-dimensional finite word. We give tight bounds for the maximum number of distinct palindromic sub-words in two-row periodic/aperiodic words. Using this, we give upper bounds for the number of distinct palindromic sub-words for 2D words of larger sizes. Lastly, we propose a better bound for any finite 2D word.

Derivation languages are language theoretical tools that describe halting derivation processes of a generating device. We consider two types of derivation languages, namely Szilard and control languages for splicing systems where iterated splicing is done in non-uniform way defined by Mitrana, Petre and Rogojin in 2010. The families of Szilard (rules and labels are mapped in a one to one manner) and control (more than one rule can share the same label) languages generated by splicing systems of this type are then compared with the family of languages in the Chomsky hierarchy. We show that context-free languages can be generated as Szilard and control languages and any non-empty context-free language is a morphic image of the Szilard language of this type of system with finite set of rules and axioms. Moreover, we show that these systems with finite set of axioms and regular set of rules are capable of generating any recursively enumerable language as a control language.

We introduce new labeling called m-bonacci graceful labeling. A graph G on n edges is m-bonacci graceful if the vertices can be labeled with distinct integers from the set (Formula presented.) such that the derived edge labels are the first n m-bonacci numbers. We show that complete graphs, complete bipartite graphs, gear graphs, triangular grid graphs, and wheel graphs are not m-bonacci graceful. Almost all trees are m-bonacci graceful. We give m-bonacci graceful labeling to cycles, friendship graphs, polygonal snake graphs, and double polygonal snake graphs.

Combinatorial properties of 1D Fibonacci words is a well studied topic in Formal language theory. In the year 2000, Apostolico et.al. extended the concept of one dimensional Fibonacci words to two dimensional Fibonacci arrays and investigated the number of repetitions of some structures (squares, tandems). In this paper, we investigate the number of distinct Palindromic occurrences in any given Fibonacci array. We also investigate the number of palindromes in the conjugacy class of a Fibonacci array.

Research in DNA computing was initiated by Leonard Adleman in 1994 when he solved an instance of an NP-complete problem solely by molecules. DNA code words arose in the attempt to avoid unwanted hybridizations of DNA strands for DNA based computations. Given a set of constraints, generating a large set of DNA strands that satisfy the constraints is an important problem in DNA computing. On the other hand, motivated by the non-determinism of molecular reactions, A. Ehrenfeucht and G. Rozenberg introduced forbidding and enforcing systems (fe-systems) as a model of computation that defines classes of languages based on two sets of constraints. We attempt to establish a connection between these two areas of research in natural computing by characterizing a variety of DNA codes that avoid certain types of cross hybridizations by fe-systems. We show that one fe-system can generate the entire class of DNA codes of a certain property, for example θ-k-codes, and confirm some properties of DNA codes through fe-systems. We generalize by fe-systems some known methods of generating good DNA code words which have been tested experimentally. © 2012 Springer-Verlag.

In this paper, we do a theoretical study of some of the notions in combinatorics of words with respect to the insertion operation on words. We generalize the classical notions of conjugacy and commutativity of words to insertion-conjugacy and insertion-commutativity of words. We define and study properties of such words (i.e.) of words u, v and w such that (formula presented).

A two-dimensional word (2D) is a rectangular finite array of letters from the alphabet Σ. A 2D word is said to be a 2D palindrome if it is equal to its reverse image. In this paper, we study some combinatorial properties of 2D palindromes. In particular, we provide a sufficient condition under which a 2D word is said to be a 2D palindrome, discuss the necessary and sufficient condition under which a 2D word can be decomposed into 2D palindromes, and find the relation between the set of all 2D palindromes and the set of all 2D primitive words. We also show that the set of all 2D palindromes is not a recognizable language, and study a special class of 2D palindromes, namely 2D palindrome square words.