The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
From MaRDI portal
Publication:344514
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Uses Software
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