pith. sign in

arxiv: 1412.0839 · v1 · pith:R6JXXDKLnew · submitted 2014-12-02 · 💻 cs.FL

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

P.-C H\'eam (INRIA Nancy - Grand Est / LORIA / LIFC , FEMTO-ST) , V. Hugot (INRIA Lille - Nord Europe , LIFL) , O. Kouchnarenko (FEMTO-ST , INRIA Nancy - Grand Est / LORIA / LIFC) This is my paper
classification 💻 cs.FL
keywords disequalityautomataconstraintemptinessleastnp-hardproblemtree
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.