Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
Conjunctive grammars over an alphabet ∑ = {a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X = φ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings |
| Страницы | 191-202 |
| Число страниц | 12 |
| DOI | |
| Состояние | Опубликовано - 2009 |
| Опубликовано для внешнего пользования | Да |
| Событие | 4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Российская Федерация Продолжительность: 18 авг 2009 → 23 авг 2009 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 5675 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 4th International Computer Science Symposium in Russia, CSR 2009 |
|---|---|
| Страна/Tерритория | Российская Федерация |
| Город | Novosibirsk |
| Период | 18/08/09 → 23/08/09 |
ID: 78935797