GOLDEFUS, Filip, Tomáš MASOPUST a Alexander MEDUNA. Left-forbidding cooperating distributed grammar systems. Theoretical Computer Science. Amsterdam, North Holland: Elsevier Science Publishers, 2010, roč. 411, 40-42, s. 3661-3667. ISSN 0304-3975. |
Další formáty:
BibTeX
LaTeX
RIS
@article{891315, author = {Goldefus, Filip and Masopust, Tomáš and Meduna, Alexander}, article_location = {Amsterdam, North Holland}, article_number = {40-42}, keywords = {Cooperating distributed grammar system; Cooperating derivation mode; Left-forbidding grammar; Generative power; Descriptional complexity}, language = {eng}, issn = {0304-3975}, journal = {Theoretical Computer Science}, title = {Left-forbidding cooperating distributed grammar systems}, url = {http://dx.doi.org/10.1016/j.tcs.2010.06.010}, volume = {411}, year = {2010} }
TY - JOUR ID - 891315 AU - Goldefus, Filip - Masopust, Tomáš - Meduna, Alexander PY - 2010 TI - Left-forbidding cooperating distributed grammar systems JF - Theoretical Computer Science VL - 411 IS - 40-42 SP - 3661-3667 EP - 3661-3667 PB - Elsevier Science Publishers SN - 03043975 KW - Cooperating distributed grammar system KW - Cooperating derivation mode KW - Left-forbidding grammar KW - Generative power KW - Descriptional complexity UR - http://dx.doi.org/10.1016/j.tcs.2010.06.010 N2 - A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages. ER -
GOLDEFUS, Filip, Tomáš MASOPUST a Alexander MEDUNA. Left-forbidding cooperating distributed grammar systems. \textit{Theoretical Computer Science}. Amsterdam, North Holland: Elsevier Science Publishers, 2010, roč.~411, 40-42, s.~3661-3667. ISSN~0304-3975.
|