Affiliations: Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. [email protected] | Department of Languages Projects and Computer Information Systems, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. [email protected] | Department of Computer Science, University of Potsdam, August-Bebel-Str. 89, 14482 Potsdam, Germany. [email protected] | Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. [email protected] | Department of Computer Science, University of Kiel, Christian-Albrechts-Platz 4, 24098 Kiel, Germany. [email protected]
Note: [] Address for correspondence: Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. Work supported by the Alexander von Humboldt Foundation
Note: [] Work supported by the DFG grant 582014
Abstract: A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.
