On Some Problems of Mateescu Concerning Subword Occurrences

• Autorzy: Ding C. , Salomaa A.
• Języki publikacji: EN

Abstrakty

EN

The paper investigates inference based on quantities |w|u, the number of occurrences of a word u as a scattered subword of w. Parikh matrices recently introduced are useful tools for such investigations. We introduce and study universal languages for Parikh matrices. We also obtain results concerning the inference from numbers |w|u to w, as well as from certain entries of a Parikh matrix to other entries.

Słowa kluczowe

EN

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

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 65--79
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Ding C.

autor

Salomaa A.

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

Bibliografia

• [1] A. Atanasiu, C. Martin-Vide, A. Mateescu: On the injectivity of the Parikh matrix mapping. Fund. Informaticae, 49 (2002), 289-299.
• [2] M. Dudik, L.J. Schulman: Reconstruction from subsequences. J. Combin. Th. A, 103 (2002), 337-348.
• [3] S. Fossé, G. Richomme: Some characterizations of Parikh matrix equivalent binary words. Inform. Proc. Lett., 92 (2004), 77-82.
• [4] W. Kuich, A. Salomaa: Semirings, Automata, Languages. Springer, Berlin, Heidelberg, New York, 1986.
• [5] B. Manvel, A. Meyerowitz, A. Schwenk, K. Smith, P. Stockmeyer: Reconstruction of sequences. Discrete Math., 94 (1991), 209-219.
• [6] A. Mateescu: Algebraic aspects of Parikh matrices. In Theory is Forever (J. Karhumäki, H. Maurer, G. Pǎun, G. Rozenberg, Eds.), LNCS 3113, Springer, 2004, 170-180.
• [7] A. Mateescu, A. Salomaa: Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci, 15 (2004), 277-292.
• [8] A. Mateescu, A. Salomaa, K. Salomaa, S. Yu: A sharpening of the Parikh mapping. Theoret. Informatics Appl., 35 (2001), 551-564.
• [9] A. Mateescu, A. Salomaa, S. Yu: Subword histories and Parikh matrices. J. Comput. Syst. Sci., 68 (2004), 1-21.
• [10] R.J. Parikh: On context-free languages. J. Assoc. Comput. Mach., 13 (1966), 570-581.
• [11] G. Rozenberg, A. Salomaa: Handbook of Formal Languages, vol. 1-3. Springer, Berlin, Heidelberg, New York, 1997.
• [12] J. Sakarovitch, I. Simon: Subwords. In Combinatorics on Words (M. Lothaire, Ed.), Addison-Wesley, Reading, Mass., 1983, 105-142.
• [13] A. Salomaa: Counting (scattered) subwords. EATCS Bulletin, 81 (2003), 165-179.
• [14] A. Salomaa: On the injectivity of Parikh matrix mappings. Fundamenta Informaticae, 64 (2005), 391-404.
• [15] A. Salomaa: Connections between subwords and certain matrix mappings. Theoretical Computer Science, 340 (2005), 188-203.
• [16] A. Salomaa, S. Yu: Subword conditions and subword histories. TUCS Technical Report 633, 2004, Information and Computation, to appear.
• [17] A. Salomaa: On languages defined by numerical parameters. TUCS Technical Report 663, 2005, submitted for publication.
• [18] T.-F. Şerbǎnutǎ: Extending Parikh matrices. Theoretical Computer Science, 310 (2004), 233-246.