Автоматы с чередующимися деревьями - Википедия - Alternating tree automata
В теория автоматов, автомат с переменным деревом (ATA) является расширением недетерминированный древовидный автомат такой же как переменный конечный автомат расширяет недетерминированный конечный автомат (NFA).
Вычислительная сложность
Проблема пустоты (определение того, является ли язык входящего ATA пустым) и проблема универсальности для ATA: EXPTIME-завершено.[1] Проблема членства (проверка того, принимается ли входное дерево входным AFA) находится в PTIME.[1].
Рекомендации
| P ≟ NP | Этот теоретическая информатика –Связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |