×

Independence of certain quantities indicating subword occurrences. (English) Zbl 1100.68058

Summary: When words are characterized in terms of numerical quantities, awkward considerations due to the noncommutativity of words are avoided. The numerical quantity investigated in this paper is \(|w|_{u}\), the number of occurrences of a word \(u\) as a (scattered) subword of a word \(w\). Parikh matrices recently introduced have these quantities as their entries. According to the main result in this paper, no entry in a Parikh matrix, no matter how high the dimension, can be computed in terms of the other entries. Consequences concerning various inference problems between numbers \(|w|_{u}\) themselves, as well as of the word \(w\) from these numbers, are obtained.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. Ding, A. Salomaa, On some problems of Mateescu concerning subword occurrences, Fund. Inform. (2006), to appear.; C. Ding, A. Salomaa, On some problems of Mateescu concerning subword occurrences, Fund. Inform. (2006), to appear. · Zbl 1157.68379
[2] Dudík, M.; Schulman, L. J., Reconstruction from subsequences, J. Combin. Theory A, 103, 337-348 (2002) · Zbl 1039.68098
[3] Fossé, S.; Richomme, G., Some characterizations of Parikh matrix equivalent binary words, Inform. Process. Lett., 92, 77-82 (2004) · Zbl 1173.68550
[4] Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer: Springer Berlin, Heidelberg, New York · Zbl 0582.68002
[5] Manvel, B.; Meyerowitz, A.; Schwenk, A.; Smith, K.; Stockmeyer, P., Reconstruction of sequences, Discrete Math., 94, 209-219 (1991) · Zbl 0746.05045
[6] Mateescu, A.; Salomaa, A., Matrix indicators for subword occurrences and ambiguity, Internat. J. Found. Comput. Sci., 15, 277-292 (2004) · Zbl 1067.68117
[7] Mateescu, A.; Salomaa, A.; Salomaa, K.; Yu, S., A sharpening of the Parikh mapping, Theoret. Informatics Appl., 35, 551-564 (2001) · Zbl 1005.68092
[8] Mateescu, A.; Salomaa, A.; Yu, S., Subword histories and Parikh matrices, J. Comput. System Sci., 68, 1-21 (2004) · Zbl 1072.68085
[9] Parikh, R. J., On context-free languages, J. Assoc. Comput. Mach., 13, 570-581 (1966) · Zbl 0154.25801
[10] G. Rozenberg, A. Salomaa, (Eds.), Handbook of Formal Languages, Vols. 1-3, Springer, Berlin, Heidelberg, New York, 1997.; G. Rozenberg, A. Salomaa, (Eds.), Handbook of Formal Languages, Vols. 1-3, Springer, Berlin, Heidelberg, New York, 1997. · Zbl 0866.68057
[11] Sakarovitch, J.; Simon, I., Subwords, (Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA), 105-142
[12] Salomaa, A., Counting (scattered) subwords, EATCS Bull., 81, 165-179 (2003) · Zbl 1169.68491
[13] Salomaa, A., On the injectivity of Parikh matrix mappings, Fund. Inform., 64, 391-404 (2005) · Zbl 1102.68072
[14] Salomaa, A., Connections between subwords and certain matrix mappings, Theoret. Comput. Sci., 340, 188-203 (2005) · Zbl 1079.68054
[15] A. Salomaa, On languages defined by numerical parameters, TUCS Technical Report 663, 2005, submitted for publication.; A. Salomaa, On languages defined by numerical parameters, TUCS Technical Report 663, 2005, submitted for publication.
[16] A. Salomaa, S. Yu, Subword conditions and subword histories, TUCS Technical Report 633, 2004, Inform. and Comput., to appear.; A. Salomaa, S. Yu, Subword conditions and subword histories, TUCS Technical Report 633, 2004, Inform. and Comput., to appear. · Zbl 1171.68534
[17] Şerbănuţă, T.-F., Extending Parikh matrices, Theoret. Comput. Sci., 310, 233-246 (2004)
[18] V.G. Şerbănuţă, T.F. Şerbănuţă, Injectivity of the Parikh matrix mappings revisited, Fund. Inform. (2006), to appear.; V.G. Şerbănuţă, T.F. Şerbănuţă, Injectivity of the Parikh matrix mappings revisited, Fund. Inform. (2006), to appear.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.