2009
On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components
MASOPUST, TomášZákladní údaje
Originální název
On the Terminating Derivation Mode in Cooperating Distributed Grammar Systems with Forbidding Components
Název česky
Terminálni derivační mód v kooperujících distributivních gramatických systémech se zakazujícími komponentami
Autoři
Vydání
International Journal of Foundations of Computer Science, World Scientific, 2009, 0129-0541
Další údaje
Typ výsledku
Článek v odborném periodiku
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.512
Označené pro přenos do RIV
Ne
Organizační jednotka
Fakulta informatiky
UT WoS
Klíčová slova anglicky
Cooperating distributed grammar systems; terminating derivation mode; forbidding grammars; forbidding cooperating distributed grammar systems; generative power
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 29. 6. 2009 15:39, doc. RNDr. Tomáš Masopust, Ph.D., DSc.
V originále
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.
Česky
Článek diskutuje terminální derivační mód v kooperujících gramatických systémech, kde komponentami jsou zakazující gramatiky namísto bezkontextových gramatik. Takové systémy se pak nazývají zakazující kooperující gramatické systémy. Článek demonstruje, že počet komponent těchto systémů může být zredukován na dvě a že tyto systémy jsou výpočetně úplné. Bez vymazávacích pravidel jsou pak slabší než kontextové gramatiky.