Parikh matrices: Subword indicators and degrees of ambiguity
: Arto Salomaa
: Hans-Joachim Böckenhauer, Dennis Komm, Walter Unger
Publisher: Springer Verlag
: 2018
: Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: Lecture Notes in Computer Science
: 11011
: 100
: 112
: 978-3-319-98354-7
: 978-3-319-98355-4
: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-98355-4_7
The quantity |w|u" role="presentation">|w|u, the number of occurrences of a word u as a (scattered) subword of a word w gives important numerical information about the word w. Properly chosen values |w|u" role="presentation">|w|u, for different u’s, characterize the word w completely. Certain upper triangular matrices, customarily referred to as Parikh matrices have turned out to be very useful for computing numbers |w|u" role="presentation">|w|u.
This partially expository paper discusses some highlights and open
problems of the theory of Parikh matrices and subword occurrences.
Special emphasis is on subword indicators and degrees of ambiguity.
