Loading…
Reducing the ambiguity of Parikh matrices: theoretical considerations and tools
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 thesis, we investigate how considering the Parikh matrices of various transformations of a given word can...
Saved in:
| Main Author: | |
|---|---|
| Format: | Default Thesis |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://dx.doi.org/10.26174/thesis.lboro.18865808.v1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1818166133156478976 |
|---|---|
| author | Laura Hutchinson |
| author_facet | Laura Hutchinson |
| author_sort | Laura Hutchinson (4378327) |
| collection | Figshare |
| description | 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 thesis, 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.We also provide and discuss a tool that handles many different Parikh matrix calculations. The user may utilise this software to find Parikh matrices, the words associated to a Parikh matrix, and words that share a Parikh matrix, as well as to perform calculations around the two concepts introduced in this thesis. We discuss various algorithms that may be used to find words that share a Parikh matrix and perform worst case time complexity analysis on each of these. Finally, we explain the functionality of the toolkit in greater detail, as well as explaining how each function is used. |
| format | Default Thesis |
| id | rr-article-18865808 |
| institution | Loughborough University |
| publishDate | 2022 |
| record_format | Figshare |
| spelling | rr-article-188658082022-02-03T13:13:53Z Reducing the ambiguity of Parikh matrices: theoretical considerations and tools Laura Hutchinson (4378327) Other information and computing sciences not elsewhere classified Parikh matrix Ambiguity Lyndon conjugate Toolkit development Combinatorics Information and Computing Sciences not elsewhere classified <div>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 thesis, 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.</div><div>We also provide and discuss a tool that handles many different Parikh matrix calculations. The user may utilise this software to find Parikh matrices, the words associated to a Parikh matrix, and words that share a Parikh matrix, as well as to perform calculations around the two concepts introduced in this thesis. We discuss various algorithms that may be used to find words that share a Parikh matrix and perform worst case time complexity analysis on each of these. Finally, we explain the functionality of the toolkit in greater detail, as well as explaining how each function is used.</div> 2022-02-03T13:13:53Z Text Thesis 10.26174/thesis.lboro.18865808.v1 https://figshare.com/articles/thesis/Reducing_the_ambiguity_of_Parikh_matrices_theoretical_considerations_and_tools/18865808 CC BY-NC-ND 4.0 |
| spellingShingle | Other information and computing sciences not elsewhere classified Parikh matrix Ambiguity Lyndon conjugate Toolkit development Combinatorics Information and Computing Sciences not elsewhere classified Laura Hutchinson Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title | Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title_full | Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title_fullStr | Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title_full_unstemmed | Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title_short | Reducing the ambiguity of Parikh matrices: theoretical considerations and tools |
| title_sort | reducing the ambiguity of parikh matrices: theoretical considerations and tools |
| topic | Other information and computing sciences not elsewhere classified Parikh matrix Ambiguity Lyndon conjugate Toolkit development Combinatorics Information and Computing Sciences not elsewhere classified |
| url | https://dx.doi.org/10.26174/thesis.lboro.18865808.v1 |