The unambiguity of segmented morphisms
Dominik Freydenberger
Daniel Reidenbach
2134/5102
https://repository.lboro.ac.uk/articles/journal_contribution/The_unambiguity_of_segmented_morphisms/9402203
This paper studies the ambiguity of morphisms in free monoids. A morphism
σ is said to be ambiguous with respect to a string α if there exists a morphism
τ which differs from σ for a symbol occurring in α, but nevertheless satisfies
τ(α) = σ(α); if there is no such τ then σ is called unambiguous. Motivated
by the recent initial paper on the ambiguity of morphisms, we introduce the
definition of a so-called segmented morphism σn, which, for any n ∈ N, maps
every symbol in an infinite alphabet onto a word that consists of n distinct
factors in ab+a, where a and b are different letters. For every n, we consider
the set U(σn) of those finite strings over an infinite alphabet with respect to
which σn is unambiguous, and we comprehensively describe its relation to any
U(σm), m ≠ n.
Thus, our work features the first approach to a characterisation of sets of
strings with respect to which certain fixed morphisms are unambiguous, and
it leads to fairly counter-intuitive insights into the relations between such sets.
Furthermore, it shows that, among the widely used homogeneous morphisms,
most segmented morphisms are optimal in terms of being unambiguous for a
preferably large set of strings. Finally, our paper yields several major improvements
of crucial techniques previously used for research on the ambiguity of
morphisms.
2009-08-05 15:21:50
Combinatorics on words
Morphisms
Ambiguity
Pattern languages
Computation Theory and Mathematics
Information and Computing Sciences not elsewhere classified