Affiliations: [a] CIRT, Fachbereich 4, Universität Trier, D-54286 Trier, Germany. [email protected] | [b] School of Computer Science and Engineering, VIT, Vellore-632 014, India. [email protected] | [c] Department of Computer Science, University of Ilorin, P.M.B.1515, Ilorin, Nigeria. [email protected] | [d] Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore-641 004, India. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore-641 004, India.
Abstract: A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j, resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i, j). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals.
