The HOM Problem is EXPTIME-Complete

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Jun 2012 Spain Publisher:IEEEJournal:2012 27th Annual IEEE Symposium on Logic in Computer Science

Authors: Creus López, Carles; Gascon Caro, Adrian; Godoy Balil, Guillem; Ramos Garrido, Lander;

doi: 10.1109/lics.2012.36 , 10.1137/140999104

handle: 2117/102817 , 2117/19252

The HOM Problem is EXPTIME-Complete

- Summary
- Subjects
- Metrics

Abstract

The HOM problem questions whether the image of a given regular tree language through a given tree homomorphism is also regular. Decidability of HOM is an important theoretical question which was open for a long time. Recently, HOM has been proved decidable with a triple exponential time algorithm. In this paper we obtain an exponential time algorithm for this problem, and conclude that it is EXPTIME-complete. The proof builds upon previous results and techniques on tree automata with constraints.

Country

Spain

Related Organizations

Universitat Politècnica de Catalunya
Spain
University of Edinburgh
United Kingdom
Universitat Polite`cnica de Catalunya
Spain

Keywords

Màquines, Teoria de, Transducers, HOM problem, Formal languages and automata, Statistical decision, tree automata, Machine theory, regular languages, Tree automata, Tree homomorphisms, transducers, Complexitat computacional, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica, Teoria de, Màquines, homomorphisms, Homomorphisms, Regular languages, 004, Computational complexity, Formal languages, Decision problem, :Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC], Grammars and rewriting systems, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Problema de decisió, Llenguatges formals

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	5
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average