Reducing the Ambiguity of Parikh Matrices

The 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 t...

Descripción completa

Detalles Bibliográficos
Autores principales: Dick, Jeffery, Hutchinson, Laura K., Mercaş, Robert, Reidenbach, Daniel
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206623/
http://dx.doi.org/10.1007/978-3-030-40608-0_28
_version_ 1783530445283000320
author Dick, Jeffery
Hutchinson, Laura K.
Mercaş, Robert
Reidenbach, Daniel
author_facet Dick, Jeffery
Hutchinson, Laura K.
Mercaş, Robert
Reidenbach, Daniel
author_sort Dick, Jeffery
collection PubMed
description The 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.
format Online
Article
Text
id pubmed-7206623
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066232020-05-08 Reducing the Ambiguity of Parikh Matrices Dick, Jeffery Hutchinson, Laura K. Mercaş, Robert Reidenbach, Daniel Language and Automata Theory and Applications Article The 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. 2020-01-07 /pmc/articles/PMC7206623/ http://dx.doi.org/10.1007/978-3-030-40608-0_28 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Dick, Jeffery
Hutchinson, Laura K.
Mercaş, Robert
Reidenbach, Daniel
Reducing the Ambiguity of Parikh Matrices
title Reducing the Ambiguity of Parikh Matrices
title_full Reducing the Ambiguity of Parikh Matrices
title_fullStr Reducing the Ambiguity of Parikh Matrices
title_full_unstemmed Reducing the Ambiguity of Parikh Matrices
title_short Reducing the Ambiguity of Parikh Matrices
title_sort reducing the ambiguity of parikh matrices
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206623/
http://dx.doi.org/10.1007/978-3-030-40608-0_28
work_keys_str_mv AT dickjeffery reducingtheambiguityofparikhmatrices
AT hutchinsonlaurak reducingtheambiguityofparikhmatrices
AT mercasrobert reducingtheambiguityofparikhmatrices
AT reidenbachdaniel reducingtheambiguityofparikhmatrices

Ejemplares similares