Tree automata with global constraints

DOI10.1142/S012905411000743XMaRDI QIDQ3586405zbMATH OpenOpenAlexFDO

Authors Emmanuel Filiot, Jean-Marc Talbot, Sophie Tison

Publication date 6 September 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s012905411000743x

zbMATH Keywords

treesautomataequality constraints

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Tree Automata with Global Constraints
• On positive TAGED with a bounded number of constraints
• Decidable classes of tree automata mixing local and global constraints modulo flat theories
• Bottom-Up Tree Automata with Term Constraints
• The emptiness problem for tree automata with at least one global disequality constraint is NP-hard

Cites work

• Automata for XML -- a survey
• Automata for reduction properties solving
• Closure properties and decision problems of dag automata
• Decidability of systems of set constraints with negative constraints
• Marked PCP is decidable
• TQL: a query language for semistructured data based on the ambient logic
• Tree automata with equality constraints modulo equational theories
• Tree automata with one memory set constraints and cryptographic protocols

Cited in

(16)

• Projection for Büchi Tree Automata with Constraints between Siblings
• Emptiness and finiteness for tree automata with global reflexive disequality constraints
• Parameter reduction and automata evaluation for grammar-compressed trees
• Bottom-Up Tree Automata with Term Constraints
• Visibly Tree Automata with Memory and Constraints
• Tree Automata with Global Constraints
• Automated Induction with Constrained Tree Automata
• Tree automata, (dis-)equality constraints and term rewriting. What's new?
• scientific article; zbMATH DE number 7360252 (Why is no real title available?)
• Equality and disequality constraints on direct subterms in tree automata
• Parameterized complexity of basic decision problems for tree automata
• The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
• scientific article; zbMATH DE number 7559156 (Why is no real title available?)
• The HOM problem is EXPTIME-complete
• On positive TAGED with a bounded number of constraints
• Decidable classes of tree automata mixing local and global constraints modulo flat theories

This page was built for publication: Tree automata with global constraints

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