교대 트리 오토마타

Alternating tree automata

오토마타 이론에서 교대 트리 오토마톤(ATA)은 교대 유한 오토마톤이 비결정적 유한 오토마톤(NFA)을 확장하는 것과 마찬가지로 비결정적 트리 오토마톤의 확장이다.

계산의 복잡성

공허 문제(입력 ATA의 언어가 공허한지 판단)와 ATA의 보편성 문제는 EXPTIME-complete입니다.[1]멤버십 문제(입력 트리가 입력 AFA에 의해 받아들여지는지 테스트)는 PTIME에 있습니다[1].

레퍼런스

  1. ^ a b H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D.루기즈, STison et M.Tomasi, Tree Automata 기술 및 응용 프로그램 [1] (Theorem 7.5.1 이후 주석)


P np NP

이 이론적인 컴퓨터 공학 관련 기사는 짧은 글이다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.