Reducing the Ambiguity of Parikh Matrices.pdf (283.07 kB)
Reducing the ambiguity of Parikh matrices
conference contribution
posted on 2019-11-29, 13:43 authored by Jeff DickJeff Dick, Laura Hutchinson, Robert MercasRobert Mercas, Daniel ReidenbachThe Parikh matrix mapping allows us to describe words using matrices. Although compact, this description comes with a level of ambiguity since a single matrix may describe multiple words. This work looks at how considering the Parikh matrices of various transformations of a given word can decrease that ambiguity. More specifically, for any word, we study the Parikh matrix of its Lyndon conjugate as well as that of its projection to a smaller alphabet. Our results demonstrate that ambiguity can often be reduced using these concepts, and we give conditions on when they succeed.
History
School
- Science
Department
- Computer Science
Published in
Language and Automata Theory and Applications (LATA 2020)Pages
397 - 411Source
14th International Conference on Language and Automata Theory and Applications (LATA 2020)Publisher
SpringerVersion
- AM (Accepted Manuscript)
Rights holder
© Springer Nature Switzerland AGPublisher statement
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-40608-0_28.Acceptance date
2019-11-25Publication date
2020-02-25Copyright date
2020ISBN
9783030406073; 9783030406080Publisher version
Book series
Lecture Notes in Computer Science, vol 12038Language
- en
Editor(s)
Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio ZandronLocation
Milan, ItalyEvent dates
4th March 2020 - 6th March 2020Depositor
Dr Daniel Reidenbach. Deposit date: 29 November 2019Usage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC