Publication result detail

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

MASOPUST, T.

Original Title

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

English Title

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

Type

WoS Article

Original 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.

English 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.

Keywords

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

Key words in English

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

Authors

MASOPUST, T.

RIV year

2010

Released

02.01.2009

ISBN

0129-0541

Periodical

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Volume

20

Number

2

State

Republic of Singapore

Pages from

331

Pages to

340

Pages count

10

URL

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

BibTex

@article{BUT49471,
  author="Tomáš {Masopust}",
  title="On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components",
  journal="INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE",
  year="2009",
  volume="20",
  number="2",
  pages="331--340",
  issn="0129-0541",
  url="http://dx.doi.org/10.1142/S0129054109006589"
}