DOI

It is shown that every conjunctive language is generated by a conjunctive grammar of a special form, in which every nonterminal A has at most one rule of the general form A ? a1&an, while the rest of the rules for A must be of the type A ? w, where w is a terminal string. For context-free grammars, a similar property does not hold (S. A. Greibach, W. Shi, S. Simonson, "Single tree grammars", 1992).

Язык оригиналаанглийский
Название основной публикацииSOFSEM 2009
Подзаголовок основной публикацииTheory and Practice of Computer Science - 35th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Страницы425-436
Число страниц12
DOI
СостояниеОпубликовано - 2009
Опубликовано для внешнего пользованияДа
Событие35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009 - Spindleruv Mlyn, Чехия
Продолжительность: 24 янв 200930 янв 2009

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том5404 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009
Страна/TерриторияЧехия
ГородSpindleruv Mlyn
Период24/01/0930/01/09

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 78935730