Přednáší: Professor Lakshmanan Kuppusamy, School of
Computer Science & Engineering VIT, Vellore
Místo: Zasedací místnost Ústavu informatiky, Bezručovo náměstí 1150/13, Opava
Čas: Čtvrtek 28. 11. 2019, 13:00
Abstrakt: 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. Descriptional
complexityinvestigates 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
eective use of Geert 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.