Motivated by the research on pattern languages, we study a fundamental combinatorial question on morphisms in free semigroups: With regard to any string α over some alphabet we ask for the existence
of a morphism σ such that σ(α) is unambiguous, i.e. there is no morphism ρ with ρ ≠ σ and ρ(α) = σ(α). Our main result shows that a rich and natural class of strings is provided with unambiguous morphic images.
History
School
Science
Department
Computer Science
Citation
FREYDENBERGER, D.D., REIDENBACH, D. and SCHNEIDER, J.C., 2005. Unambiguous morphic images of strings. Lecture Notes in Computer Science, 3572, pp. 248-259.