Classes of Tree Homomorphisms with Decidable Preservation of Regularity

Guillem Godoy, Sebastian Maneth, Sophie Tison

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Decidability of regularity preservation by a homomorphism is a well known open problem for regular tree languages. Two interesting subclasses of this problem are considered: first, it is proved that regularity preservation is decidable in polynomial time when the domain language is constructed over a monadic signature, i.e., over a signature where all symbols have arity 0 or 1. Second, decidability is proved for the case where non-linearity of the homomorphism is restricted to the root node (or nodes of bounded depth) of any input term. The latter result is obtained by proving decidability of this problem: Given a set of terms with regular constraints on the variables, is its set of ground instances regular? This extends previous results where regular constraints where not considered.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computational Structures
Subtitle of host publication11th International Conference, FOSSACS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-78499-9
ISBN (Print)978-3-540-78497-5
Publication statusPublished - 2008


Dive into the research topics of 'Classes of Tree Homomorphisms with Decidable Preservation of Regularity'. Together they form a unique fingerprint.

Cite this