The Billaud Conjecture, first stated in 1993, is a fundamental problem on finite words and their heirs, i.e., the words obtained by a projection deleting a single letter. The conjecture states that every morphically primitive word, i.e., a word that is not a fixed point of any non-identity morphism, has at least one morphically primitive heir. The correctness of the conjecture has so far been established in a few special cases, which mainly restrict the alphabet size. In this paper we give a proof for the next such case, i.e., for alphabet size 4.

The Billaud Conjecture, which has been open since 1993, is a fundamental problem on finite words w and their heirs, i.e., the words obtained by deleting every occurrence of a given letter from w. It posits that every morphically primitive word, i.e., a word which is a fixed point of the identity morphism only, has at least one morphically primitive heir. In this paper, we introduce and investigate the related class of so-called Billaud words, i.e., words whose all heirs are morphically imprimitive. We provide a characterisation of morphically imprimitive Billaud words, using a new concept. We show that there are two phenomena through which words can have morphically imprimitive heirs, and we highlight that only one of those occurs in morphically primitive words. Finally, we examine our concept further, and we use it to rephrase and study the Billaud Conjecture in more detail.

A morphism g is ambiguous with respect to a word u if there exists a second morphism h≠g such that g(u)=h(u). Otherwise g is unambiguous with respect to u. Thus unambiguous morphisms are those for which the structure of the morphism is preserved in the image. Ambiguity has so far been studied for morphisms of free monoids, where several characterisations exist for the set of words u permitting an (injective) unambiguous morphism. In the present paper, we consider ambiguity of morphisms of free groups, and consider possible analogies to the existing characterisations in the free monoid. While a direct generalisation results in a trivial situation where all morphisms are ambiguous, we discuss some natural and well-motivated reformulations, and provide a characterisation of words in a free group that permit a morphism which is “as unambiguous as possible”.

A nonerasing morphism sigma is said to be weakly unambiguous with respect to a word w if sigma is the only nonerasing morphism that can map w to sigma(w), i.e., there does not exist any other nonerasing morphism tau satisfying tau(w) = sigma(w). In the present paper, we wish to characterise those words with respect to which there exists such a morphism. This question is nontrivial if we consider so-called length-increasing morphisms, which map a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions.

In the German-Brazilian cooperation project Cyclops, we are building an integrated solution in order to capture the exponentially growing medical knowledge. The system is being developed in close cooperation with private radiological hospitals in Germany and Brazil. One aim is easy knowledge exchange between the medical partners in both countries. In this paper, we describe POKMAT (Process-oriented Knowledge MAnagement Tool) and its application to medical examination guidelines. We focus on the support of examination processes and automatic report generation in a DICOM environment. In the future, the system will be extended to an organizational memory of the practice.