Lakshmanan K.: Descriptional Complexity of Some Regulated Rewriting Grammars
The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.
Author: prof. Lakshmanan Kuppusamy, School of Computer Science & Engineering, Department of Computational BioSciences, VIT University, India
Title: Descriptional Complexity of Some Regulated Rewriting Grammars
Abstract: It is well known that the set of context-free languages is a strict subset of the set of recursively enumerable languages. Analogously, a type-2 (or context-free) grammar cannot simulate a type-0 grammars. However, if we control or regulate the application of the context-free rules, then we can make the grammar to simulate a type-0 grammar. Several regulations are associated with these grammars and are called regulated rewriting grammars. Some of them are (i) Matrix rewriting grammars (ii) Graph-Controlled grammars (iii) Semi-Conditional grammars. The descriptional complexity investigates the economical measures required for a grammatical device, automaton, or a rewriting system for a succinct representation of a formal language class.
In this talk, we are going to concentrate on semi-conditional grammars and their variants simple semi-conditional and generalized forbidden grammars. In a semi-conditional grammar, the derivations are controlled by permitting string and/or forbidden string that are associated with each rule and is known as conditional rule. The maximum lengths of permitting strings of permitting and forbidden strings refer to the degree of the system. Besides degree, the number of nonterminals and the number of conditional rules are considered to be descriptional complexity measures. We will see the computational completeness results of the above said systems with minimal/succinct sizes of measures. Our proofs include some novel ideas and effective use of Geffert normal forms. In the sequel, we will review some results available in the literature; many of the results are contributed by Prof. Alexander Meduna and his research group.