The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
详细信息 查看全文
- 作者：P.-C. Hé ; ama ; pheam@femto-st.fr" class="auth_mail" title="E-mail the corresponding author ; V. Hugotb ; O. Kouchnarenkoa
- 关键词：Formal languages ; Tree automata ; Algorithms
- 刊名：Information Processing Letters
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：118
- 期：Complete
- 页码：6-9
- 全文大小：246 K
文摘
- •
Tree Automata with constraints are a relevant for modeling programs, protocols and XML-like documents.
- •
The Emptiness problem for TAG∧ is decidable but the only known algorithm is non elementary.
- •
Studying the complexity of sub-classes of TAG∧ is therefore a challenging problem.
- •
We prove that the emptiness problem for TAG∧ with at least one disequality constraint is NP-hard.