TREE AUTOMATA WITH GLOBAL CONSTRAINTS

DOI10.1142/S012905411000743XzbMath1205.68199OpenAlexW1997436239MaRDI QIDQ3586405

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

automataequality constraintstrees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

The emptiness problem for tree automata with at least one global disequality constraint is NP-hard ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Tree Automata, (Dis-)Equality Constraints and Term Rewriting ⋮ Unnamed Item ⋮ The HOM Problem is EXPTIME-Complete ⋮ Parameterized complexity of basic decision problems for tree automata ⋮ Projection for Büchi Tree Automata with Constraints between Siblings ⋮ Emptiness and finiteness for tree automata with global reflexive disequality constraints

Cites Work

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

This page was built for publication: TREE AUTOMATA WITH GLOBAL CONSTRAINTS