Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.
| Язык оригинала | английский |
|---|---|
| Страницы (с-по) | 27-58 |
| Число страниц | 32 |
| Журнал | Theory of Computing Systems |
| Том | 46 |
| Номер выпуска | 1 |
| DOI | |
| Состояние | Опубликовано - 1 янв 2009 |
ID: 41141736