Переменные древовидные автоматы

В теории автоматов автомат попеременного дерева (ATA) является расширением недетерминированного конечного автомата , так же как попеременный конечный автомат расширяет недетерминированный конечный автомат (NFA).

Вычислительная сложность

Проблема пустоты (решение, является ли язык входного ATA пустым) и проблема универсальности для ATA являются EXPTIME-полными . ^{[ 1 ]} Проблема членства (проверка того, принимается ли входное дерево входным AFA) находится в PTIME. ^{[ 1 ]}.

Ссылки

^ Перейти обратно: ^а ^б Х. Комон, М. Доше, Р. Жилерон, К. Лёдинг, Ф. Жакмар, Д. Люжье, С. Тисон и М. Томмаси, Методы и приложения древовидных автоматов [1] (теорема 7.5.1 и последующее замечание)

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

[comon2008tree-1] Перейти обратно: ^а ^б Х. Комон, М. Доше, Р. Жилерон, К. Лёдинг, Ф. Жакмар, Д. Люжье, С. Тисон и М. Томмаси, Методы и приложения древовидных автоматов [1] (теорема 7.5.1 и последующее замечание)

[ 1 ]