Search

Your search keyword '"Raman, Indhumathi"' showing total 104 results
Start Over Author "Raman, Indhumathi"
104 results on '"Raman, Indhumathi"'

1. On Computational Completeness of Semi-Conditional Matrix Grammars

Author

Fernau, Henning, Kuppusamy, Lakshmanan, and Raman, Indhumathi

Subjects
Computer Science - Formal Languages and Automata Theory, 68Q45
Abstract

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Originally, they have been introduced by \'Abrah\'am on linguistic grounds. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the matrix length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on attaching a permitting and a forbidden string to every matrix in a matrix grammar. The matrix is applicable to a sentential form~$w$ only if the permitting string is a subword in~$w$ and the forbidden string is not a subword in~$w$. We call such a grammar, where the application of a matrix is conditioned as described, a semi-conditional matrix grammar. We consider $(1)$ the maximal lengths of permitting and forbidden strings, $(2)$ the number of nonterminals, $(3)$ the number of conditional matrices, $(4)$ the maximal length of any matrix and $(5)$ the number of conditional matrices with nonempty permitting and forbidden strings, as the resources (descriptional complexity measures) of a semi-conditional matrix grammar. In this paper, we show that certain semi-conditional matrix grammar families defined by restricting resources can generate all of the recursively enumerable languages.

Published
2024

2. When Stars Control a Grammar's Work

Author

Fernau, Henning, Kuppusamy, Lakshmanan, and Raman, Indhumathi

Subjects
Computer Science - Formal Languages and Automata Theory, F.4.2, F.4.3
Abstract

Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. Such a system has several components and each component contains some insertion-deletion rules. The components are the vertices of a directed control graph. A rule is applied to a string in a component and the resultant string is moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. We impose the restriction in the structure of the underlying graph to be a star structure where there is a central, control component which acts like a master and transmits a string (after applying one of its rules) to one of the components specified in the (applied) rule. A component which receives the string can process the obtained string with any applicable rule available in it and sends back the resultant string only to the center component. With this restriction, we obtain computational completeness for some descriptional complexity measures, Comment: In Proceedings AFL 2023, arXiv:2309.01126

Published
2023
Full Text
View/download PDF

3. Counting Simple Rules in Semi-conditional Grammars is not Simple

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Goos, Gerhard, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Levy Patey, Ludovic, editor, Pimentel, Elaine, editor, Galeotti, Lorenzo, editor, and Manea, Florin, editor

Published
2024
Full Text
View/download PDF

6. Generalized Forbidding Matrix Grammars and Their Membrane Computing Perspective

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Freund, Rudolf, editor, Ishdorj, Tseren-Onolt, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Zandron, Claudio, editor

Published
2021
Full Text
View/download PDF

8. On the Power of Generalized Forbidding Insertion-Deletion Systems

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Jirásková, Galina, editor, and Pighizzini, Giovanni, editor

Published
2020
Full Text
View/download PDF

10. Descriptional Complexity of Matrix Simple Semi-conditional Grammars

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Hospodár, Michal, editor, Jirásková, Galina, editor, and Konstantinidis, Stavros, editor

Published
2019
Full Text
View/download PDF

11. Improved Descriptional Complexity Results on Generalized Forbidding Grammars

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Oladele, Rufus O., Raman, Indhumathi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Pal, Sudebkumar Prasant, editor, and Vijayakumar, Ambat, editor

Published
2019
Full Text
View/download PDF

12. On Matrix Ins-Del Systems of Small Sum-Norm

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Catania, Barbara, editor, Královič, Rastislav, editor, Nawrocki, Jerzy, editor, and Pighizzini, Giovanni, editor

Published
2019
Full Text
View/download PDF

13. A note on closed-form representation of Fibonacci numbers using Fibonacci trees

Author

Raman, Indhumathi

Subjects
Mathematics - Combinatorics, 05C30
Abstract

In this paper, we give a new representation of the Fibonacci numbers. This is achieved using Fibonacci trees. With the help of this representation, the nth Fibonacci number can be calculated without having any knowledge about the previous Fibonacci numbers., Comment: 4 pages and 1 figure. Gives a closed form representation of Fibonacci numbers

Published
2013

14. Computational Completeness of Simple Semi-conditional Insertion-Deletion Systems

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Stepney, Susan, editor, and Verlan, Sergey, editor

Published
2018
Full Text
View/download PDF

15. Minimizing Rules and Nonterminals in Semi-conditional Grammars: Non-trivial for the Simple Case

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Oladele, Rufus O., Raman, Indhumathi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Durand-Lose, Jérôme, editor, and Verlan, Sergey, editor

Published
2018
Full Text
View/download PDF

18. Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Pighizzini, Giovanni, editor, and Câmpeanu, Cezar, editor

Published
2017
Full Text
View/download PDF

19. Computational Completeness of Path-Structured Graph-Controlled Insertion-Deletion Systems

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Carayol, Arnaud, editor, and Nicaud, Cyril, editor

Published
2017
Full Text
View/download PDF

24. Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Amos, Martyn, editor, and CONDON, ANNE, editor

Published
2016
Full Text
View/download PDF

25. Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

Author

Fernau, Henning, Kuppusamy, Lakshmanan, Raman, Indhumathi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Câmpeanu, Cezar, editor, Manea, Florin, editor, and Shallit, Jeffrey, editor

Published
2016
Full Text
View/download PDF

32. On Embedding of Certain Recursive Trees and Stars into Hypercube

Author

Raman, Indhumathi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ghosh, Subir Kumar, editor, and Tokuyama, Takeshi, editor

Published
2013
Full Text
View/download PDF

40. On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

Author

Fernau, Henning, Kuppusamy, Lakshmanan, and Raman, Indhumathi

Abstract

A graph-controlled insertion-deletion (GCID) system is a regulated extension of an insertion-deletion system. Such a system has several components and each component has some insertion-deletion rules. A rule is applied to a string in a component and the resultant string is moved to the target component specified in the rule. We discuss the generative power of the GCID systems of size $(k;n,i',i'';m,j',j'')$ for all values of $n,m \in \{1,2\}$ and $i',i'',j',j'' \in \{0,1\}$, where the parameters in the size denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right \mbox{context} for insertion; the last three parameters follow a similar representation with respect to deletion. We prove that GCID systems with sizes $(3;2,0,0;1,1,0)$, $(3;2,0,0;1,0,1)$, $(3;1,1,0;2,0,0)$ and $(3;1,0,1;2,0,0)$ describe the family of recursively enumerable languages ($\mathrm{RE}$). We then show that for all $i',i'',j',j'' \in \{0,1\}$ with $i'+i''+j'+j'' \neq 0$, ins-del systems of size $(1;2,i',i'';2,j',j'')$ describe $\mathrm{RE}$. Further for GCID systems of certain sizes that are not known to describe $\mathrm{RE}$, we describe the linear languages and as well some closure classes of them., Journal of Automata, Languages and Combinatorics, Volume 22, Numbers 1-3, 2017, 61-92

Published
2017
Full Text
View/download PDF

44. Embedding certain height-balanced trees and completepm-ary trees into hypercubes

Author

S. A. Choudum and Raman Indhumathi

Subjects
Tree rotation, Discrete mathematics, Vertex (graph theory), Combinatorics, Binary tree, Computational Theory and Mathematics, Link/cut tree, Weight-balanced tree, Discrete Mathematics and Combinatorics, Embedding, Hypercube, Theoretical Computer Science, Mathematics
Abstract

A height-balanced tree is a rooted binary tree T in which for every vertex v@?V(T), the heights of the left and right subtrees of v, differ by at most one. In this paper, we embed two subclasses of height-balanced trees into hypercubes with unit dilation. We also prove that for certain values of p and for all m>=1, a complete p^m-ary tree of height h is embeddable into a hypercube of dimension O(mh) with dilation O(m) using the embedding results of the above height-balanced trees. These results improve and extend the results of Gupta et al. (2003) [10].

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results