The emptiness problem for tree automata with at least one global disequality constraint is NP-hard

DOI10.1016/j.ipl.2016.09.007zbMath1393.68093arXiv1412.0839OpenAlexW221278049MaRDI QIDQ344514

Vincent Hugot, Olga Kouchnarenko, Pierre-Cyrille Héam

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.0839

zbMATH Keywords

algorithmsformal languagestree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• Timbuk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rigid tree automata and applications
• Emptiness and finiteness for tree automata with global reflexive disequality constraints
• On Positive TAGED with a Bounded Number of Constraints
• Visibly Tree Automata with Memory and Constraints
• Tree Automata with Global Constraints
• TREE AUTOMATA WITH GLOBAL CONSTRAINTS
• Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories
• Equality and disequality constraints on direct subterms in tree automata
• Rewriting Approximations for Fast Prototyping of Static Analyzers