The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard

2014/12/02 by Pierre‐Cyrille Héam, Héam, P. -C, Vincent Hugot +3
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1412.0839

openalex publication_date 2014/12/02 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

The model of tree automata with equality and disequality constraints was introduced in 2007 by Filiot, Talbot and Tison. In this paper we show that if there is at least one disequality constraint, the emptiness problem is NP-hard.

Related

• Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
• Emptiness of zero automata is decidable
• Constraint Automata on Infinite Data Trees: From CTL(Z)/CTL*(Z) To Decision Procedures
• The Complexity of Checking Non-Emptiness in Symbolic Tree Automata
• A Survey on Satisfiability Checking for the μ-Calculus through Tree Automata