The HOM problem is EXPTIME-complete

Autor: Adria Gascon Caro, Guillem Godoy, Lander Ramos, Carles Creus

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname

We define a new class of tree automata with constraints and prove decidability of the emptiness problem for this class in exponential time. As a consequence, we obtain several EXPTIME-completeness results for problems on images of regular tree langua

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c2d09bc938a3748cdc555673471f9e3
http://hdl.handle.net/2117/19252