Improved normal form for grammars with one-sided contexts

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

4 Цитирования (Scopus)


Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("Defining contexts in context-free grammars", LATA 2012), further extending the author's ("Conjunctive grammars", DCAGRS 2000) earlier work on propositional connectives in grammars. These grammars allow two types of context specifications: for a substring w of a string uwv, a left context operator ◁D states that u is of the form described by D, while the extended left context operator ⊴E states that uw is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, while left contexts may be applied only for individual symbols, so that all rules are of the form A → B1C1 &⋯& BnCn or A → a & ◁D. This eliminates circular dependencies in the grammar and allows simplifying the known parsing algorithm. Some further improvements to the algorithm accelerate it from time O(n3) to time O(n3/log n).

Язык оригиналаанглийский
Название основной публикацииDescriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings
Число страниц12
СостояниеОпубликовано - 2013
Опубликовано для внешнего пользованияДа
Событие15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013 - London, ON, Канада
Продолжительность: 22 июл 201325 июл 2013

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

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


конференция15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013
ГородLondon, ON

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

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


Подробные сведения о темах исследования «Improved normal form for grammars with one-sided contexts». Вместе они формируют уникальный семантический отпечаток (fingerprint).