ReidenbachUnambiguous_FinalVersion.pdf (200.75 kB)
Download fileUnambiguous morphic images of strings
journal contribution
posted on 2008-07-25, 07:42 authored by Dominik FreydenbergerDominik Freydenberger, Daniel Reidenbach, Johannes C. SchneiderMotivated 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