Reducing the Ambiguity of Parikh Matrices.pdf (283.07 kB)
Download file

Reducing the ambiguity of Parikh matrices

Download (283.07 kB)
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.

History

School

  • Science

Department

  • Computer Science

Published in

Language and Automata Theory and Applications (LATA 2020)

Pages

397 - 411

Source

14th International Conference on Language and Automata Theory and Applications (LATA 2020)

Publisher

Springer

Version

AM (Accepted Manuscript)

Rights holder

© Springer Nature Switzerland AG

Publisher statement

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-40608-0_28.

Acceptance date

25/11/2019

Publication date

2020-02-25

Copyright date

2020

ISBN

9783030406073; 9783030406080

Book series

Lecture Notes in Computer Science, vol 12038

Language

en

Editor(s)

Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron

Location

Milan, Italy

Event dates

4th March 2020 - 6th March 2020

Depositor

Dr Daniel Reidenbach. Deposit date: 29 November 2019

Usage metrics

Categories

Exports