ReducingTheAmbiguityOfParikhMatrices_new.pdf (345.11 kB)
Download file

Reducing the ambiguity of Parikh matrices

Download (345.11 kB)
journal contribution
posted on 27.01.2021, 09:44 by Jeff DickJeff Dick, Laura Hutchinson, Robert MercasRobert Mercas, Daniel ReidenbachDaniel Reidenbach
The Parikh matrix mapping allows us to describe words using matrices. Whilst compact, this description comes with a level of ambiguity since a single matrix may describe multiple words. In this paper, we investigate 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 projection to a smaller alphabet as well as that of its Lyndon conjugate. Our results demonstrate that ambiguity can often be reduced using these concepts, and we give conditions on when they succeed.

Funding

DTP 2016-2017 Loughborough University

Engineering and Physical Sciences Research Council

Find out more...

History

School

  • Science

Department

  • Computer Science

Published in

Theoretical Computer Science

Volume

860

Pages

23-40

Publisher

Elsevier BV

Version

AM (Accepted Manuscript)

Rights holder

© Elsevier

Publisher statement

This paper was accepted for publication in the journal Theoretical Computer Science and the definitive published version is available at https://doi.org/10.1016/j.tcs.2021.01.025.

Acceptance date

18/01/2021

Publication date

2021-01-20

Copyright date

2021

ISSN

0304-3975

Language

en

Depositor

Dr Robert Mercas. Deposit date: 25 January 2021

Usage metrics

Read the paper on the publisher website

Categories

Exports