Publication Details

On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components

MASOPUST Tomáš. On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components. International Journal of Foundations of Computer Science, vol. 20, no. 2, 2009, pp. 331-340. ISSN 0129-0541.

Czech title

Terminálni derivační mód v kooperujících distributivních gramatických systémech se zakazujícími komponentami

Type

journal article

Language

english

Authors

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)

URL

http://dx.doi.org/10.1142/S0129054109006589 HTML

Keywords

Cooperating distributed grammar systems; terminating derivation mode; forbidding grammars; forbidding cooperating distributed grammar systems; generative power.

Abstract

This paper discusses the terminating derivation mode in cooperating distributed grammar systems where components are forbidding grammars instead of context-free grammars. Such systems are called forbidding cooperating distributed grammar systems, and it is demonstrated that the number of their components can be reduced to two without changing the generative power and that these systems are computationally complete. Without erasing productions, however, these systems are less powerful than context-sensitive grammars.

Published

2009

Pages

331-340

Journal

International Journal of Foundations of Computer Science, vol. 20, no. 2, ISSN 0129-0541

UT WoS

000265086600007

BibTeX

@ARTICLE{FITPUB8779,
   author = "Tom\'{a}\v{s} Masopust",
   title = "On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components",
   pages = "331--340",
   journal = "International Journal of Foundations of Computer Science",
   volume = 20,
   number = 2,
   year = 2009,
   ISSN = "0129-0541",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8779"
}