IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

We introduce the notion of m-bonacci-sum graphs denoted by Gm,n for positive integers m,n. The vertices of Gm,n are 1,2,…,n and any two vertices are adjacent if and only if their sum is an m-bonacci number. We show that Gm,n is bipartite and for n≥2m−2, Gm,n has exactly (m−1) components. We also find the values of n such that Gm,n contains cycles as subgraphs. We use this graph to partition the set 1,2,…,n into m−1 subsets such that each subset is ordered in such a way that sum of any 2 consecutive terms is an m-bonacci number. © 2021 Elsevier B.V.

Department of Mathematics

World University root node

Discrete Applied Mathematics

Properties of m-bonacci-sum graphs

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. © 2021 The Author(s). Published with license by Taylor & Francis Group, LLC.

Fulltext

AKCE International Journal of Graphs and Combinatorics

m-Bonacci graceful labeling

A DNA string is a Watson-Crick (WK) palindrome when the complement of its reverse is equal to itself. The Watson-Crick mapping (Formula Presented) is an involution that is also an antimorphism. (Formula Presented)-conjugates of a word is a generalization of conjugates of a word that incorporates the notion of WK-involution (Formula Presented). In this paper, we study the distribution of palindromes and Watson-Crick palindromes, also known as (Formula Presented)-palindromes among both the set of conjugates and (Formula Presented)-conjugates of a word w. We also consider some general properties of the set (Formula Presented), i.e., the set of (Formula Presented)-conjugates of a word w, and characterize words w such that (Formula Presented), i.e., with the maximum number of elements in (Formula Presented). We also find the structure of words that have at least one (WK)-palindrome in (Formula Presented). © 2020, Springer Nature Switzerland AG.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Theta Palindromes in Theta Conjugates

We study the Szilard languages of InsDel(insertion-deletion) systems. We compare the Szilard languages obtained by these systems with the families of languages in Chomsky hierarchy. We show that although InsDel systems can characterize recursively enumerable languages, there exist some regular languages which cannot be obtained as a Szilard language by any InsDel system. Moreover, InsDel systems of size (1, 1, 1; 1, 1, 1) (i. e., having insertion/deletion rules where one symbol is inserted/deleted in the contexts with one symbol) can obtain context-sensitive languages which are not context-free as Szilard languages. Any regular and context-free language can be obtained as a homomorphic image of Szilard language of InsDel systems of size (1, 1, 1; 1, 1, 0) (i. e., having insertion rules where one symbol is inserted in the contexts with one symbol and deletion rules where one symbol is deleted with one symbol in the left-context) and (3, 1, 1; 1, 1, 1) (i. e., having insertion rules where three symbols are inserted in the contexts with one symbol and deletion rules where one symbol is deleted in the contexts with one symbol) respectively. Also any recursively enumerable language can be obtained as a homomorphic image of the Szilard language of InsDel systems of size (3, 0, 0; 3, 1, 0), (3, 0, 0; 2, 1, 0), (2, 0, 0; 3, 1, 0) and (3, 0, 0; 3, 0, 0). © Institut für Informatik · Justus-Liebig-Universität Giessen.

Journal of Automata, Languages and Combinatorics

On szilard languages of insdel systems

The Parikh matrix mapping plays an important role in the study of words through numerical properties. The Parikh q-matrix mapping, introduced by Egecioglu and Ibarra (2004) as an extension of the Parikh matrix mapping, maps words to matrices with polynomial entries in q. A word w over an ordered alphabet ς is said to be q-ambiguous if there exists another word v over ς such that both the words have same Parikh q-matrix. Here we derive several properties of q-ambiguous words, in particular, for a binary alphabet. © 2020 World Scientific Publishing Company.

Department Of Biotechnology

International Journal of Foundations of Computer Science

Parikh q-Matrices and q-Ambiguous Words

The non-trivial extension of Fibonacci words to Fibonacci arrays was proposed by Apostolico and Brimkov in order to study repetitions in arrays. In this paper we investigate several combinatorial as well as formal language theoretic properties of Fibonacci arrays. In particular, we show that the set of all Fibonacci arrays is a 2D primitive language (under certain conditions), count the number of borders in Fibonacci arrays, and show that the set of all Fibonacci arrays is a non-recognizable language. We also show that the set of all square Fibonacci arrays is a two dimensional code. © Springer Nature Switzerland AG 2019.

GENERAL

Combinatorial properties of fibonacci arrays

We introduce the notion of m-bonacci-sum graphs denoted by Gm,n for positive integers m, n. The vertices of Gm,n are 1,2, …, n and any two vertices are adjacent if and only if their sum is an m-bonacci number. We show that Gm,n is bipartite and for (Formula presented) has exactly (m-1) components. We also find the values of n such that Gm,n contains cycles as subgraphs. We also use this graph to partition the set {1,2, …, n} into m-1 subsets such that each subset is ordered in such a way that sum of any 2 consecutive terms is an m-bonacci number. © Springer Nature Switzerland AG 2019.

On m-Bonacci-sum graphs

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. © Springer Nature Switzerland AG 2019.

Watson-crick jumping finite automata

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). © 2019, Springer Nature Switzerland AG.

Operation Insertion on the Conjugacy and Commutativity of Words

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). © 2019, Springer Nature Switzerland AG.

On the Maximum Number of Distinct Palindromic Sub-arrays

We investigate the least number of distinct palindromic sub-arrays in two-dimensional words over a finite alphabet Σ={a1,a2⋯,aq} for a given alphabet size q. We discuss the case for both periodic as well as aperiodic words. © 2019

Theoretical Computer Science

On the least number of palindromes in two-dimensional words

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. © 2018 Editura Academiei Romane. All rights reserved.

Romanian Journal of Information Science and Technology

Palindromic Properties of Two-Dimensional FibonacciWords

We introduce the concept of relative Watson-Crick primitivity of words and its generalization, the relative θ-primitivity of words, where θ is a morphic or an antimorphic involution. Similar to relatively prime integers which do not share any common factors, we call two words u and v relatively θ-primitive if they do not share a common θ-primitive root. We study some combinatorial properties of relatively θ-primitive words, as well as establish relations between each of the two words u and v and the result of some binary word operation between u and v, from this perspective. © Institut für Informatik · Justus-Liebig-Universität Giessen.

Relative Watson-Crick primitivity of words

We introduce an extension of the restricted shuffle operator on binary words considered by Atanasiu and Teh (2016). We then derive properties on Parikh matrix equivalence of words over a binary alphabet based on this extended shuffle operator and a weak-ratio property of words. We also examine the recently introduced concept of core Parikh matrix equivalence of binary words in the context of the restricted shuffle operator. © 2018 World Scientific Publishing Company.

Properties of parikh matrices of binary words obtained by an extension of a restricted shuffle operator

Representation of a word by a graph is an important branch of study in combinatorics of words. The vertices and the edges are defined using certain properties of words. Such a representation is useful in solving some problems in graph theory. One such representation is the idea of Rauzy graphs that was used to study Arnoux-Rauzy sequences. In this paper, we define half range Rauzy graphs and study the structural properties of such a variant for some special words. © 2018 Editura Academiei Romane. All rights reserved.

On a Special Variant of Rauzy Graphs

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. © 2018 University of Szeged, Institute of Informatics. All rights reserved.

Acta Cybernetica

On derivation languages of a class of splicing systems

Based on the idea of "q-count" of certain subwords of a word and generalizing the notion of Parikh matrix of a word, the notion of Parikh q-matrix of a word over an ordered alphabet was introduced. On the other hand, with a two-dimensional picture array of symbols arranged in rows and columns, two kinds of upper triangular matrices, known as row and column Parikh matrices have also been introduced and investigated. Here combining these two kinds of matrices of a picture array, we introduce row/column Parikh q-matrix of an array, leading to the concept of q- A mbiguity of a picture array. Results relating to q- A mbiguity of picture arrays are derived in the context of these Parikh q-matrices of arrays. © Published under licence by IOP Publishing Ltd.

Journal of Physics: Conference Series

Two-dimensional picture arrays and Parikh q-matrices

Labelled splicing P systems are distributed parallel computing models, where sets of strings that evolve by splicing rules are labelled. In this work, we consider labelled splicing systems with the following modifications: (i) The strings in the membranes are present in arbitrary number of copies; (ii) the rules in the regions are finite in number. Results on the language family generated by the labelled splicing system in comparison with the language families of the Chomsky hierarchy, including recursively enumerable languages, are obtained, by involving only either one or two membranes in the P systems considered. © Springer Nature Singapore Pte Ltd 2017.

Communications in Computer and Information Science

Derivation languages of splicing P systems

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. © Springer International Publishing AG 2017.

Two-dimensional palindromes and their properties

The motion of a robot inside a rectangular grid is simulated using Isotonic Array P System (IAPS)defined by Sureshkumar and Rama in 2015. A polynomial time algorithm has been proposed using this grammatical model to find the shortest path with and/or without obstacles. The obstacles are usually assumed be of polygonal shape in the rectangular grid. © 2017 [International Journal of Imaging and Robotics].