%0 Conference Proceedings
%T Descriptional Complexity of Matrix Simple Semi-conditional Grammars
%+ Trier University
%+ Vellore Institute of Technology (VIT)
%+ Department of Applied Mathematics and Computational Sciences [Nadu]
%A Fernau, Henning
%A Kuppusamy, Lakshmanan
%A Raman, Indhumathi
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 111-123
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_8
%K Simple semi-conditional grammars
%K Matrix grammars
%K Computational completeness
%K Geffert normal forms
%K Descriptional complexity
%Z Computer Science [cs]Conference papers
%X Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. In simple semi-conditional (SSC) grammars, the derivations are controlled by a permitting string or by a forbidden string associated to each rule. The maximum length i of permitting strings and the maximum length j of forbidden strings are called the degree of such grammars. Matrix SSC grammars (MSSC) put matrix grammar control on SSC rules. We consider the computational completeness of MSSC grammars with degrees (2, 1), (2, 0) and (3, 0). The results are important in the following aspects. (i) With permitting strings alone, it is unknown if SSC grammars are computational complete, while MSSC grammars describe $$\textsf {RE}$$ even with severe further restrictions on their descriptional complexity. (ii) Matrix grammars with appearance checking with three nonterminals are computationally complete; however, the length is unbounded. With our constructions for MSSC grammars, we can even bound the length.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387307/document
%2 https://inria.hal.science/hal-02387307/file/480958_1_En_8_Chapter.pdf
%L hal-02387307
%U https://inria.hal.science/hal-02387307
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612