Emptiness and finiteness for tree automata with global reflexive disequality constraints

DOI10.1007/s10817-012-9270-5zbMath1314.68175OpenAlexW1989597513MaRDI QIDQ2351395

Carles Creus, Guillem Godoy, Adrià Gascón

Publication date: 23 June 2015

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-012-9270-5

zbMATH Keywords

decision problemstree automataglobal constraintsdisequality constraints

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (1)

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

Cites Work

• Unnamed Item
• Rigid tree automata and applications
• Ground reducibility is EXPTIME-complete
• Automata for reduction properties solving
• Two-variable logic on data trees and XML reasoning
• TREE AUTOMATA WITH GLOBAL CONSTRAINTS
• Term Rewriting and All That
• Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories
• Equality and disequality constraints on direct subterms in tree automata

This page was built for publication: Emptiness and finiteness for tree automata with global reflexive disequality constraints