Ambiguity of the Multiple Interpretations on Regular Languages

作者：Pablo Alarcon Pedro; Arroyo Fernando; Bordihn Henning; Mitrana Victor^*; Mueller Mike

来源：Fundamenta Informaticae, 2015, 138(1-2): 85-95.

DOI：10.3233/FI-2015-1200

• Multiple interpretation scheme
• regular language
• o-ambiguity
• internal ambiguity
• external ambiguity

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.

• 出版日期2015