Parameterized complexity of basic decision problems for tree automata

DOI10.1080/00207160.2012.762451zbMath1286.68166OpenAlexW2056097558MaRDI QIDQ2855747

Agata Chorowska, Witold Charatonik

Publication date: 22 October 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2012.762451

zbMATH Keywords

parameterized complexity theoryclassical tree automatarigid tree automatat-DAG automatatree automata with global equality and disequality

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition ⋮ Algebraic state space approach to model and control combined automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automata for XML -- a survey
• Closure properties and decision problems of dag automata
• Abstracting cryptographic protocols with tree automata.
• The Parameterized Complexity of Chosen Problems for Finite Automata on Trees
• TREE AUTOMATA WITH GLOBAL CONSTRAINTS
• Rigid Tree Automata
• Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories
• Tree Automata with Memory, Visibility and Structural Constraints

This page was built for publication: Parameterized complexity of basic decision problems for tree automata