|
$\Sigma TC$-порождаемые языки и проблемы относительной эквивалентности
Л. П. Лисовик
Аннотация:
Доказана разрешимость проблемы эквивалентности для машин Тьюринга ограниченного режима с выходной лентой относительно любого входного $\Sigma TC$-порождаемого языка. Такие языки порождаются обобщенными конечными преобразователями с конечноповоротными счетчиками над бесконечными размеченными деревьями. Доказана $\Sigma TC$-порождаемость многих языков (контекстно-свободных, распознаваемых гнездовыми машинами Тьюринга ограниченного режима и других). Показано, что для последовательностных преобразователей с двумя состояниями неразрешима проблема эквивалентности относительно регулярного языка.
Статья поступила: 05.05.1994
Образец цитирования:
Л. П. Лисовик, “$\Sigma TC$-порождаемые языки и проблемы относительной эквивалентности”, Дискрет. матем., 9:2 (1997), 139–160
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm470https://doi.org/10.4213/dm470 https://www.mathnet.ru/rus/dm/v9/i2/p139
|
Статистика просмотров: |
Страница аннотации: | 337 | PDF полного текста: | 201 | Первая страница: | 1 |
|