TY  - JOUR
A1  - Csuhaj-Varjú, Erzsébet
A1  - Dassow, Juergen
A1  - Vaszil, György
T1  - Variants of competence-based derivations in CD grammar systems
N2  - In this paper we introduce and study some new cooperation protocols for cooperating distributed (CD) grammar systems. These derivation modes depend on the number of different nonterminals present in the sentential form obtained when a component finished a derivation phase. This measure describes the competence of the grammar on the string (the competence is high if the number of the different nonterminals is small). It is also a measure of the efficiency of the grammar on the given string (a component is more efficient than another one if it is able to decrease the number of nonterminals in the string to a greater extent). We prove that if the underlying derivation mode is the t-mode derivation, then some variants of these systems determine the class of random context ET0L languages. If these CD grammar systems use the k step limited derivations as underlying derivation mode, then they are able to generate any recursively enumerable language.
Y1  - 2010
UR  - http://www.worldscinet.com/ijfcs/ijfcs.shtml
U6  - https://doi.org/10.1142/S0129054110007428
SN  - 0129-0541
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Dassow, Juergen
A1  - Holzer, Markus
T1  - Extending regular expressions with homomorphic replacement
N2  - We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem.
Y1  - 2010
UR  - http://www.rairo-ita.org/
U6  - https://doi.org/10.1051/Ita/2010013
SN  - 0988-3754
ER  -