Creus, Carles, Gascon, Adrià, Godoy, Guillem and Ramos, Lander (2016) The HOM problem is EXPTIME-complete. SIAM Journal on Computing, 45 (4). pp. 1230-1260. doi:10.1137/140999104 ISSN 0097-5397.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

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 languages under tree homomorphisms, like set inclusion, regularity (HOM problem), and finiteness of set difference. Our result also has implications in term rewriting, since the set of reducible terms of a term rewrite system can be described as the image of a tree homomorphism. In particular, we prove that inclusion of sets of normal forms of term rewrite systems can be decided in exponential time. Analogous consequences arise in the context of XML typechecking, since types are defined by tree automata and some type transformations are homomorphic.

Item Type:	Journal Article
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	SIAM Journal on Computing
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0097-5397
Official Date:	2016
Dates:	Date Event 2016 Published 6 July 2016 Available 1 June 2016 Accepted
Volume:	45
Number:	4
Page Range:	pp. 1230-1260
DOI:	10.1137/140999104
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item