The HOM problem is decidable

DOI10.1145/1806689.1806757MaRDI QIDQ2875176zbMATH OpenOpenAlexFDO

Authors Guillem Godoy, Omer Giménez, Lander Ramos, Carme Àlvarez

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1806689.1806757

zbMATH Keywords

homomorphismsregular languagestransducerstree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The HOM problem is decidable
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• The HOM Problem is EXPTIME-Complete
• The HOM problem is EXPTIME-complete
• scientific article; zbMATH DE number 1330134

Cited in

(14)

• Isomorphism of regular trees and words
• Weighted tree automata with constraints
• Crossing the syntactic barrier: hom-disequalities for \({\mathcal H}_1\)-clauses
• Tree automata, (dis-)equality constraints and term rewriting. What's new?
• Parameter reduction and automata evaluation for grammar-compressed trees
• Paths, tree homomorphisms and disequalities for H₁-clauses
• The HOM problem is decidable
• Projection for Büchi Tree Automata with Constraints between Siblings
• The HOM Problem is EXPTIME-Complete
• The HOM problem is EXPTIME-complete
• scientific article; zbMATH DE number 7724207 (Why is no real title available?)
• Solving the Weighted HOM-Problem With the Help of Unambiguity
• The weighted HOM-problem over fields
• Weighted HOM-problem for nonnegative integers

This page was built for publication: The HOM problem is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875176)