Generalized Parikh Matrices For Tracking Subsequence Occurrences
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917713547362304 |
|---|---|
| author | Fazekas, Szilárd Zsolt Huang, Xinhao |
| author_facet | Fazekas, Szilárd Zsolt Huang, Xinhao |
| contents | We introduce and study a generalized Parikh matrix mapping based on tracking the occurrence counts of special types of subsequences. These matrices retain more information about a word than the original Parikh matrix mapping while preserving the homomorphic property. We build the generalization by first introducing the Parikh factor matrix mapping and extend it to the Parikh sequence matrix mapping. We establish an interesting connection between the generalized Parikh matrices and the original ones and use it to prove that certain important minors of a Parikh sequence matrix have nonnegative determinant. Finally, we generalize the concept of subword histories and show that each generalized subword history is equivalent to a linear one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized Parikh Matrices For Tracking Subsequence Occurrences Fazekas, Szilárd Zsolt Huang, Xinhao Formal Languages and Automata Theory 68Q45 F.4.3 We introduce and study a generalized Parikh matrix mapping based on tracking the occurrence counts of special types of subsequences. These matrices retain more information about a word than the original Parikh matrix mapping while preserving the homomorphic property. We build the generalization by first introducing the Parikh factor matrix mapping and extend it to the Parikh sequence matrix mapping. We establish an interesting connection between the generalized Parikh matrices and the original ones and use it to prove that certain important minors of a Parikh sequence matrix have nonnegative determinant. Finally, we generalize the concept of subword histories and show that each generalized subword history is equivalent to a linear one. |
| title | Generalized Parikh Matrices For Tracking Subsequence Occurrences |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2407.04462 |