The Ambiguity of Morphisms in Free Monoids and Its Impact on Algorithmic Properties of Pattern Languages (Paperback) (ISBN-13: 9783832514495)

his book systematically discusses a basic problem in combinatorics on words: the ambiguity of morphisms, i. e. the question of whether, for any finite string s and any given morphism h, there is another morphism g satisfying g(s)=h(s). These studies yield a characterisation of those strings for which there exists an unambiguous morphism; furthermore, they lead to various insights into the ambiguity of important selected example morphisms. Additional considerations are concerned with the ambiguity of so-called terminal-preserving morphisms. Due to its fundamental nature, the ambiguity of morphisms shows strong connections to other topics in discrete mathematics and computer science such as pattern inference and equality sets; in particular, it is significantly related to various properties of E-pattern languages. Therefore, the book provides a thorough survey on pattern languages and presents several profound advances in the understanding of this subject.

Author: Daniel Reidenbach
ISBN-10: 383251449X
ISBN-13: 9783832514495
Publisher: Logos Verlag Berlin
Language: English
Published: 01/31/2007
Pages: 175
Format: Paperback