Characterizations of CD Grammar Systems Working in Competence Mode by Multicounter Machine Resources

In this paper we focus on characterizations of

cooperating distributed grammar systems

(henceforth CDGSs) working in { ≤ 

k

, = 

k

, ≥ 

k

}-competence mode,

k

 ≥ 1, defined in [1], by means of time, space and several other resources of a multicounter machine such as number of counters, reversals or 0-tests. We show that CDGSs working in { ≤ 

k

, = 

k

, ≥ 

k

}-competence mode,

k

 ≥ 1, can be simulated by

one-way nondeterministic multicounter machines

in linear time and space, with a linear-bounded number of reversals. If we impose restrictions on the capacity of each counter to perform 0-testings, we find that CDGSs working in { ≤ 1, = 1} ∪ { ≥ 

k

|

k

 ≥ 1}-competence mode can be simulated by

one-way partially blind multicounter machines

in quasirealtime. It is known from [8] that quasirealtime partially blind multicounter machines accept the family of

Petri net languages

. Consequently, various decision problems for partially blind multicounter machines are decidable. With respect to them, several decidability results, for CDGSs working in competence mode, grammars and systems with regulated rewriting, that emerge from the above simulations are presented, too.