Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › глава/раздел › научная › Рецензирование
The paper studies resolved systems of language equations that allow the use of all Boolean operations in addition to concatenation. Existence and uniqueness of solutions are shown to be their nontrivial properties, these properties are given characterizations by first order formulae, and the position of the corresponding decision problems in the arithmetical hierarchy is determined. The class of languages defined by components of unique solutions of such systems is shown to coincide with the class of recursive languages.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | ICALP 2003: Automata, Languages and Programming |
| Страницы | 239-251 |
| Число страниц | 13 |
| Том | 2719 |
| Состояние | Опубликовано - 1 дек 2003 |
| Опубликовано для внешнего пользования | Да |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Издатель | Springer |
| ISSN (печатное издание) | 0302-9743 |
ID: 41144716