Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
It has recently been shown that several computational models - trellis automata, recursive functions and Turing machines - admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is shown that resolved systems with two variables and two equations are as expressive as more complicated systems, while one-variable equations are "almost" as expressive. Additionally, language equations with added quotient with regular languages are shown to be able to denote every arithmetical set.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers |
| Редакторы | Maurice Margenstern |
| Страницы | 292-303 |
| Число страниц | 12 |
| Том | 3354 |
| DOI | |
| Состояние | Опубликовано - 2005 |
| Опубликовано для внешнего пользования | Да |
| Событие | 4th International Conference on Machines, Computations, and Universality, MCU 2004 - Saint Petersburg, Российская Федерация Продолжительность: 21 сен 2004 → 24 сен 2004 |
| Название | Lecture Notes in Computer Science |
|---|---|
| Издатель | Springer Nature |
| ISSN (печатное издание) | 0302-9743 |
| конференция | 4th International Conference on Machines, Computations, and Universality, MCU 2004 |
|---|---|
| Страна/Tерритория | Российская Федерация |
| Город | Saint Petersburg |
| Период | 21/09/04 → 24/09/04 |
ID: 78926142