Subword Balance in Binary Words, Languages and Sequences

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

Abstrakty

EN

We investigate binary words and languages having a balanced structure of (scattered) subwords. We introduce a "difference function" D for binary words. For D=0, the resulting language is properly context-sensitive. Parikh matrices constitute a useful technical tool in the study, we investigate also the independence of their entries. The investigation is extended to concern w-words and periodicity. For the Fibonacci word, the D-values are in many ways connected with the Fibonacci numbers.

Słowa kluczowe

EN

subword; scattered subwords; counting subwords; parikh matrix; periodicity; Fibonacci word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 4690482--4690482
• Opis fizyczny: bibliogr. 21 poz.

Twórcy

autor

Salomaa A.

• Turku Centre for Computer Science, Joukahaisenkatu 3-5B, 20520 Turku, Finland,

Bibliografia

• [1] Berstel, J. and Karhumäki, J., Combinatorics on words - a tutorial. In P˘aun, G., Rozenberg, G. and Salomaa, A. (eds.): Current Trends in Theoretical Computer Science. The Challenge of a New Century, Vol. 2, World Scientific Publishing Company, Singapore (2004) 415-475.
• [2] Ding, C. and Salomaa, A., On some problems of Mateescu concerning subword occurrences. Fundamenta Informaticae (2006), to appear.
• [3] Dudik, M. and Schulman, L.J., Reconstruction from subsequences. J. Combin. Th. A 103 (2002) 337-348.
• [4] Fossé, S. and Richomme, G., Some characterizations of Parikh matrix equivalent binary words. Inform. Proc. Lett. 92 (2004) 77-82.
• [5] Kuich, W. and Salomaa, A. Semirings, Automata, Languages. Springer-Verlag, Berlin, Heidelberg, New York, 1986.
• [6] Manvel, B.,Meyerowitz, A., Schwenk, A., Smith, K., Stockmeyer, P., Reconstruction of sequences. Discrete Math. 94 (1991) 209-219.
• [7] Mateescu, A., Salomaa, A., Salomaa, K. and Yu, S., A sharpening of the Parikh mapping. Theoret. Informatics Appl. 35 (2001) 551-564.
• [8] Mateescu, A., Salomaa, A. and Yu, S., Subword histories and Parikh matrices. J. Comput. Syst. Sci. 68 (2004) 1-21.
• [9] Mateescu, A. and Salomaa, A., Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci 15 (2004) 277-292.
• [10] Parikh, R.J., On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570-581.
• [11] Rozenberg, G. and Salomaa, A., TheMathematical Theory of L Systems. Academic Press, New York (1980).
• [12] Rozenberg, G. and Salomaa, A. (eds.), Handbook of Formal Languages 1-3. Springer-Verlag, Berlin, Heidelberg, New York (1997).
• [13] Sakarovitch, J. and Simon, I., Subwords. In M. Lothaire: Combinatorics on Words, Addison-Wesley, Reading, Mass. (1983) 105-142.
• [14] Salomaa, A., Counting (scattered) subwords. EATCS Bulletin 81 (2003) 165-179.
• [15] Salomaa, A., On the injectivity of Parikh matrix mappings. Fundamenta Informaticae 64 (2005) 391-404.
• [16] Salomaa, A., Connections between subwords and certain matrix mappings. Theoretical Computer Science. 340 (2005) 188-203.
• [17] Salomaa, A., On languages defined by numerical parameters. TUCS Technical Report 663 (2005), submitted for publication.
• [18] Salomaa, A., Independence of certain quantities indicating subword occurrences. TUCS Technical Report 748 (2006), submitted for publication.
• [19] Salomaa, A. and Yu, S., Subword conditions and subword histories. TUCS Technical Report 633 (2004), Information and Computation, to appear.
• [20] Şerbǎnut¸˘a, T.-F., Extending Parikh matrices. Theoretical Computer Science 310 (2004) 233-246.
• [21] Şerbǎnut¸˘a, V.G. and Şerbǎnut¸˘a, T.F., Injectivity of the Parikh matrix mappings revisited. Fundamenta Informaticae (2006), to appear.