ReidenbachSchneider_DLT10_RestrictedAmbiguityOfErasingMorphisms[1].pdf (193.48 kB)

Restricted ambiguity of erasing morphisms

Download (193.48 kB)
conference contribution
posted on 08.09.2010, 15:20 by Daniel Reidenbach, Johannes C. Schneider
A morphism h is called ambiguous for a string s if there is another morphism that maps s to the same image as h; otherwise, it is called unambiguous. In this paper, we examine some fundamental problems on the ambiguity of erasing morphisms. We provide a detailed analysis of so-called ambiguity partitions, and our main result uses this concept to characterise those strings that have a morphism of strongly restricted ambiguity. Furthermore, we demonstrate that there are strings for which the set of unambiguous morphisms, depending on the size of the target alphabet of these morphisms, is empty, finite or infinite. Finally, we show that the problem of the existence of unambiguous erasing morphisms is equivalent to some basic decision problems for nonerasing multi-pattern languages.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHNEIDER, J.C., 2010. Restricted ambiguity of erasing morphisms. 14th International Conference on Developments in Language Theory, DLT 2010, August 17-20, 2010, London, Ontario, Canada.

Publisher

© Springer Verlag

Version

AM (Accepted Manuscript)

Publication date

2010

Notes

This conference paper was subsequently published as: REIDENBACH, D. and SCHNEIDER, J.C., 2010. Restricted ambiguity of erasing morphisms. IN: Gao, Y. ... et al (eds). Proceedings of the 14th International Conference on Developments in Language Theory, DLT 2010. Lecture Notes in Computer Science, Vol. 6224, pp.387-398.

ISSN

0302-9743

Book series

Lecture Notes in Computer Science;6224

Language

en

Usage metrics

Loughborough Publications

Keywords

Exports