Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
85--95
Opis fizyczny
Bibliogr. 15 poz., tab.
Twórcy
autor
- 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