TREE AUTOMATA WITH GLOBAL CONSTRAINTS
From MaRDI portal
Publication:3586405
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
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