PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Ambiguity of the Multiple Interpretations on Regular Languages

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
85--95
Opis fizyczny
Bibliogr. 15 poz., tab.
Twórcy
  • Department of Organization and Structure of Information Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain
autor
  • Department of Languages Projects and Computer Information Systems Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain
autor
  • Department of Computer Science University of Potsdam August-Bebel-Str. 89, 14482 Potsdam, Germany
autor
  • Department of Organization and Structure of Information Polytechnic University of Madrid Crta. de Valencia km. 7 - 28031 Madrid, Spain
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-34ab9e93-a4ed-4c41-ba96-cda570c5f734
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.