On the Injectivity of Parikh Matrix Mappings

• Autorzy: Salomaa A.
• Języki publikacji: EN

Abstrakty

EN

We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called g-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

Słowa kluczowe

EN

subword; scattered subwords; number of subwords; parikh matrix; ambiguity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 391--404
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Salomaa A.

• Turku Centre for Computer Science TUCS, Lemminkäisenkatu 14, FIN-20520 Turku, Finland,

Bibliografia

• [1] M. Berinde, Interview with Solomon Marcus. European Mathematical Society Newsletter, 50 (2003), 15–16.
• [2] A. Carpi, A. De Luca,Words and special factors. Theoretical Computer Science, 259 (2001), 145–182.
• [3] S. Foss´e, G. Richomme, Some characterizations of Parikh matrix equivalent binary words. Manuscript (2003).
• [4] W. Kuich, A. Salomaa, Semirings, Automata, Languages. Springer-Verlag, Berlin, Heidelberg, New York, 1986.
• [5] J. Mănuch, Characterization of a word by its subwords. In G. Rozenberg and W. Thomas, Eds., Developments in Language Theory, World Scientific Publ. Co., 2000, 210–219.
• [6] A. Mateescu, A. Salomaa, K. Salomaa, S. Yu, A sharpening of the Parikh mapping. Theoret. Informatics Appl., 35 (2001), 551–564.
• [7] A. Mateescu, A. Salomaa, S. Yu, Subword histories and Parikh matrices. J. Comput. Syst. Sci., 68 (2004), 1–21.
• [8] A. Mateescu, A. Salomaa, Matrix indicators for subword occurrences and ambiguity. TUCS Technical Report 536 (2003), Int. J. Found. Comput.Sci, to appear.
• [9] R.J. Parikh, On context-free languages. J. Assoc. Comput. Mach., 13 (1966), 570–581.
• [10] G. Rozenberg, A. Salomaa, Eds., Handbook of Formal Languages 1–3. Springer-Verlag, Berlin, Heidelberg, New York, 1997.
• [11] J. Sakarovitch, I. Simon, Subwords. In M. Lothaire: Combinatorics on Words, Addison-Wesley, Reading, Mass., 1983, 105–142.
• [12] A. Salomaa, Counting (scattered) subwords. EATCS Bulletin, 81 (2003), 165–179.
• [13] T.-F. Şerbănuţă, Extending Parikh matrices. Theoretical Computer Science, 310 (2004), 233–246