Affiliations: Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. pedrop.alarcon@eui.upm.es | Department of Languages Projects and Computer Information Systems, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. farroyo@eui.upm.es | Department of Computer Science, University of Potsdam, August-Bebel-Str. 89, 14482 Potsdam, Germany. henning@cs.uni-potsdam.de | Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. victor.mitrana@upm.es | Department of Computer Science, University of Kiel, Christian-Albrechts-Platz 4, 24098 Kiel, Germany. mimu@informatik.uni-kiel.de
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.
