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 submatrices of a Parikh sequence matrix have nonnegative minors. Finally, we generalize the concept of subword histories and show that each generalized subword history is equivalent to a linear one.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Generalized Parikh Matrices for Tracking Subsequence Occurrences

  • Szilárd Zsolt Fazekas,
  • Xinhao Huang

摘要

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 submatrices of a Parikh sequence matrix have nonnegative minors. Finally, we generalize the concept of subword histories and show that each generalized subword history is equivalent to a linear one.