From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity
Bulletin of Computer and Data Sciences · 2020
DOI: 10.71448/bcds2011-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bulletin of Computer and Data Sciences, 2020. Verfasst von Arto Salomaa.
Abstract (Originalsprache)
We study Parikh matrices as an order-sensitive refinement of Parikh vectors. We formalize the mapping \(PM_k\) and an indicator-based generalization \(PM_v\), showing via a simple encoding that every \(PM_v\) reduces to an ordinary Parikh matrix. Structurally, we revisit \(M\)-equivalence and (un)ambiguity (including the complete binary characterization and finiteness for prints), and identify cyclic shifts and disjoint transpositions as Parikh-friendly permutations. Algorithmically, \(M\)-equivalence is decidable in polynomial time, while recognition and unambiguity admit natural exponential procedures; superdiagonals exhibit substantial independence. Finally, we construct binary families with exponentially large \(M\)-equivalence classes and relate their counts to Gaussian binomials, ruling out polynomial upper bounds on ambiguity degree.
Zitieren
APA
Salomaa, A. (2020). From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity. Bulletin of Computer and Data Sciences. https://doi.org/10.71448/bcds2011-3
Vancouver
Salomaa A. From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity. Bulletin of Computer and Data Sciences. 2020. doi:10.71448/bcds2011-3
BibTeX
@article{Salomaa2020,
author = {Salomaa, Arto},
title = {From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity},
journal = {Bulletin of Computer and Data Sciences},
year = {2020},
doi = {10.71448/bcds2011-3}
}
EUVIMED