A3 Refereed book chapter or chapter in a compilation book
Parikh matrices: Subword indicators and degrees of ambiguity
Authors: Arto Salomaa
Editors: Hans-Joachim Böckenhauer, Dennis Komm, Walter Unger
Publisher: Springer Verlag
Publication year: 2018
Book title : Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Volume: 11011
First page : 100
Last page: 112
ISBN: 978-3-319-98354-7
eISBN: 978-3-319-98355-4
ISSN: 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.
