A3 Vertaisarvioitu kirjan tai muun kokoomateoksen osa
Parikh matrices: Subword indicators and degrees of ambiguity
Tekijät: Arto Salomaa
Toimittaja: Hans-Joachim Böckenhauer, Dennis Komm, Walter Unger
Kustantaja: Springer Verlag
Julkaisuvuosi: 2018
Kokoomateoksen nimi: Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 11011
Aloitussivu: 100
Lopetussivu: 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.
