Defining contexts in context-free grammars

Mikhail Barash, Alexander Okhotin

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

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


Conjunctive grammars (Okhotin, 2001) are an extension of the standard context-free grammars with a conjunction operation, which maintains most of their practical properties, including many parsing algorithms. This paper introduces a further extension to the model, which is equipped with quantifiers for referring to the left context, in which the substring being defined does occur. For example, a rule A → a & ◁B defines a string a, as long as it is preceded by any string defined by B. The paper gives two equivalent definitions of the model-by logical deduction and by language equations-and establishes its basic properties, including a transformation to a normal form, a cubic-time parsing algorithm, and another recognition algorithm working in linear space.

Язык оригиналаанглийский
Название основной публикацииLanguage and Automata Theory and Applications - 6th International Conference, LATA 2012, Proceedings
Число страниц13
СостояниеОпубликовано - 12 мар 2012
Событие6th International Conference on Language and Automata Theory and Applications, LATA 2012 - A Coruna, Испания
Продолжительность: 5 мар 20129 мар 2012

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

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


конференция6th International Conference on Language and Automata Theory and Applications, LATA 2012
ГородA Coruna

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

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

Fingerprint Подробные сведения о темах исследования «Defining contexts in context-free grammars». Вместе они формируют уникальный семантический отпечаток (fingerprint).