DOI

The paper investigates some of the fundamental ideas of the context-free grammar theory, as they are applied to several extensions and subclasses of context-free grammars. For these grammar families, including multi-component grammars, tree-adjoining grammars, conjunctive grammars and Boolean grammars, a summary of the following properties is given: parse trees, language equations, closure under several operations, normal forms, parsing algorithms, representation in the FO(LFP) logic, representations by automata and by categorial grammars, homomorphic characterizations, hardest language theorems, pumping lemmata and other limitations, computational complexity.

Язык оригиналаанглийский
Название основной публикацииLanguage and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings
ИздательSpringer Nature
Страницы36-59
Число страниц24
ISBN (печатное издание)9783319773124
DOI
СостояниеОпубликовано - 1 янв 2018
Событие12th International Conference on Language and Automata Theory and Applications, LATA 2018 - Ramat Gan, Израиль
Продолжительность: 9 апр 201811 апр 2018

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

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

конференция

конференция12th International Conference on Language and Automata Theory and Applications, LATA 2018
Страна/TерриторияИзраиль
ГородRamat Gan
Период9/04/1811/04/18

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

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

ID: 33856773