On positive TAGED with a bounded number of constraints

DOI10.1007/978-3-642-31606-7_29MaRDI QIDQ2914722zbMATH OpenOpenAlexFDO

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

Publication date 20 September 2012

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31606-7_29

Mathematics Subject Classification ID

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

Recommendations

• Tree automata with global constraints
• Tree Automata with Global Constraints
• Decidable classes of tree automata mixing local and global constraints modulo flat theories
• Bottom-Up Tree Automata with Term Constraints
• Equality and disequality constraints on direct subterms in tree automata

Cited in

(7)

• Parameterized complexity of basic decision problems for tree automata
• The parameterized complexity of chosen problems for finite automata on trees
• The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
• Tree Automata with Global Constraints
• Tree automata with global constraints
• TAGED Approximations for Temporal Properties Model-Checking
• Decidable classes of tree automata mixing local and global constraints modulo flat theories

This page was built for publication: On positive TAGED with a bounded number of constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914722)