Tree Automata with Global Constraints

DOI10.1007/978-3-540-85780-8_25zbMath1161.68525OpenAlexW1944541449MaRDI QIDQ3533021

Emmanuel Filiot, Jean-Marc Talbot, Sophie Tison

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_25

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

The emptiness problem for tree automata with at least one global disequality constraint is NP-hard ⋮ One-variable context-free hedge automata ⋮ Rigid tree automata and applications ⋮ Unnamed Item ⋮ Rigid Tree Automata ⋮ TAGED Approximations for Temporal Properties Model-Checking

Cites Work

• Unnamed Item
• Automata for XML -- a survey
• Closure properties and decision problems of dag automata
• Equational formulae with membership constraints
• Tree automata with one memory set constraints and cryptographic protocols
• Decidability of systems of set constraints with negative constraints
• Automata for reduction properties solving
• Set constraints with projections
• Satisfiability of a Spatial Logic with Tree Variables
• Tree Automata with Equality Constraints Modulo Equational Theories
• Some new decidability results on positive and negative set constraints
• Equality and disequality constraints on direct subterms in tree automata
• Logics for Unranked Trees: An Overview
• Unranked Tree Automata with Sibling Equalities and Disequalities
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Anti-pattern Matching

This page was built for publication: Tree Automata with Global Constraints