Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings |
Publisher | Springer Nature |
Pages | 36-59 |
Number of pages | 24 |
ISBN (Print) | 9783319773124 |
DOIs | |
State | Published - 1 Jan 2018 |
Event | 12th International Conference on Language and Automata Theory and Applications, LATA 2018 - Ramat Gan, Israel Duration: 9 Apr 2018 → 11 Apr 2018 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 10792 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 12th International Conference on Language and Automata Theory and Applications, LATA 2018 |
---|---|
Country/Territory | Israel |
City | Ramat Gan |
Period | 9/04/18 → 11/04/18 |
ID: 33856773