ReidenbachUnambiguous_FinalVersion.pdf (200.75 kB)
Download file

Unambiguous morphic images of strings

Download (200.75 kB)
journal contribution
posted on 25.07.2008, 07:42 by Dominik FreydenbergerDominik Freydenberger, Daniel ReidenbachDaniel Reidenbach, Johannes C. Schneider
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.

Publisher

© Springer Verlag

Publication date

2005

Notes

This is a journal article. It was published in Lecture Notes in Computer Science [© Springer Verlag] and the definitive version is available at: www.springerlink.com

ISSN

0302-9743

Language

en

Usage metrics

Keywords

Exports