On Some Problems of Mateescu Concerning Subword Occurrences

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Ding, Cunsheng | Salomaa, Arto

Affiliations: Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China. E-mail: cding@ust.hk | Turku Centre for Computer Science, Lemminkäisenkatu 14 A, 5th floor, FIN-20520 Turku, Finland. E-mail: asalomaa@utu.fi

Abstract: 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.

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, inference from subwords, ambiguity

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 65-79, 2006