×

The unambiguity of segmented morphisms. (English) Zbl 1202.68225

Harju, Tero (ed.) et al., Developments in language theory. 11th international conference, DLT 2007, Turku, Finland, July 3–6, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73207-5/pbk). Lecture Notes in Computer Science 4588, 181-192 (2007).
Summary: A segmented morphism \(\sigma_n\Delta^* \longrightarrow \{\mathtt{a},\mathtt{b}\}^*\), \(n \in \mathbb N\), maps each symbol in \(\Delta \) onto a word which consists of \(n\) distinct subwords in \(\mathtt{a}\mathtt{b}^+\mathtt{a}\). In the present paper, we examine the impact of \(n\) on the unambiguity of \(\sigma _{n }\) with respect to any \(\alpha \in \Delta ^{ + }\), i.e. the question of whether there does not exist a morphism \(\tau \) satisfying \(\tau (\alpha ) = \sigma _{n }(\alpha )\) and, for some symbol \(x\) in \(\alpha\), \(\tau (x) \neq \sigma _{n }(x)\). To this end, we consider the set \(U(\sigma _{n })\) of those \(\alpha \in \Delta ^{ + }\) with respect to which \(\sigma _{n }\) is unambiguous, and we comprehensively describe its relation to any \(U(\sigma _{m })\), \(m \neq n\). Our paper thus contributes fundamental (and, in parts, fairly counter-intuitive) results to the recently initiated research on the ambiguity of morphisms.
For the entire collection see [Zbl 1119.68010].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Link