Ambiguity of the Multiple Interpretations on Regular Languages

• Autorzy: Alarcón P. P. , Arroyo F. , Bordihn H. , Mitrana V. , Müller M.

Identyfikatory

DOI

10.3233/FI-2015-1200

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

multiple interpretation scheme; regular language; o-ambiguity; internal ambiguity; external; ambiguity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 85--95
• Opis fizyczny: Bibliogr. 15 poz., tab.

Twórcy

autor

Alarcón P. P.

• Department of Organization and Structure of Information Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain

autor

Arroyo F.

• Department of Languages Projects and Computer Information Systems Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain

autor

Bordihn H.

• Department of Computer Science University of Potsdam August-Bebel-Str. 89, 14482 Potsdam, Germany

autor

Mitrana V.

• Department of Organization and Structure of Information Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain

autor

Müller M.

• Department of Computer Science University of Kiel Christian-Albrechts-Platz 4, 24098 Kiel, Germany

Bibliografia

• [1] Angluin, D.: Finding patterns common to a set of strings, Journal of Computer and System Sciences 21, 1980, 46–62.
• [2] Filè, G.: The relation of two patterns with comparable languages, in Proc. STACS 1988, Lecture Notes in Computer Science 294, 1988, 184–192.
• [3] Herman, G., Rozenberg, G.: Developmental Systems and Languages, North-Holland, Amsterdam, 1975.
• [4] Jiang, T., Kinber, E., Salomaa, A., Salomaa, K., Yu, S.: Pattern languages with and without erasing, International Journal of Computer Mathematics 50, 1994, 147–163.
• [5] Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata, Information Processing Letters 40, 1991, 25–31.
• [6] Kari, L., Mateescu, A., P˘aun, G., Salomaa, A.: Multi-pattern languages, Theoretical Computer Science, 141, 1995, 253–268.
• [7] Karhumäki, J., Rytter, W., Jarominek, S.: Efficient constructions of test sets for regular and context-free languages, Proc. MFCS 1991, Lecture Notes in Computer Science 520, 1991, 249–258.
• [8] Kudlek, M., Martín-Vide, C., Mitrana, V.: Multiple pattern interpretations, GRAMMARS, 5, 2002, 223–238.
• [9] Kuich,W., Maurer, H.: On the inherent ambiguity of simple tuple languages, Computing 7, 1971, 194–203.
• [10] Langton, C.G. (ed.) Artificial Life, Santa Fe Institute Studies in the Science of Complexity VI. Addison-Wesley, Reading MA, 1989.
• [11] Lothaire, M.: Algebraic combinatorics on words, Cambridge University Press, 2002
• [12] Martín-Vide, C., Mitrana, V.: Remarks on arbitrary multiple pattern interpretations, Information Processing Letters 101, 2007, 209–214.
• [13] Restivo, A., Salemi, S.: Words and patterns, Proc. Developments in Language Theory, Lecture Notes in Computer Science 2295, 2002, 117–129.
• [14] Rodeh, M.: A fast test for unique decipherability based on suffix trees (Corresp.) IEEE Transactions on Information Theory 28, 1982, 648–651.
• [15] Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Springer, Berlin, vol. I-III, 1997.