Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
A variant of Circuit Value Problem over the basis of Peirce's arrow (NOR) is introduced, in which one of the inputs of every k-th gate must be the (k - 1)-th gate. The problem, which remains P-complete, is encoded as a simple formal language over a two-letter alphabet. It is shown that this language can be naturally and succinctly represented by language equations from several classes. Using this representation, a small conjunctive grammar and an even smaller LL(1) Boolean grammar for this language are constructed.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings |
| Страницы | 267-278 |
| Число страниц | 12 |
| Состояние | Опубликовано - 1 дек 2007 |
| Событие | 5th International Conference on Machines, Computations, and Universality, MCU 2007 - Orleans, Франция Продолжительность: 10 сен 2007 → 13 сен 2007 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 4664 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 5th International Conference on Machines, Computations, and Universality, MCU 2007 |
|---|---|
| Страна/Tерритория | Франция |
| Город | Orleans |
| Период | 10/09/07 → 13/09/07 |
ID: 41143911