Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@article{BUT49471,
  author="Tomáš {Masopust}",
  title="On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components",
  annote="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.",
  address="NEUVEDEN",
  chapter="49471",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="International Journal of Foundations of Computer Science",
  number="2",
  volume="20",
  year="2009",
  month="january",
  pages="331--340",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}