{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T20:12:47Z","timestamp":1771963967911,"version":"3.50.1"},"reference-count":0,"publisher":"TechForum Publishing Group","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. Comput. Data Sci."],"published-print":{"date-parts":[[2020,12,30]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.71448\/bcds2011-3","type":"journal-article","created":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T19:49:58Z","timestamp":1771962598000},"page":"19-26","source":"Crossref","is-referenced-by-count":0,"title":["From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity"],"prefix":"10.71448","volume":"1","author":[{"name":"Turku Centre for Computer Science, University of Turku, Quantum Building 392, 20014 Turun yliopisto, Finland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arto","family":"Salomaa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"52394","published-online":{"date-parts":[[2020,12,30]]},"container-title":["Bulletin of Computer and Data Sciences"],"original-title":[],"deposited":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T19:49:59Z","timestamp":1771962599000},"score":1,"resource":{"primary":{"URL":"https:\/\/bcds.ch\/from-parikh-vectors-to-parikh-matrices-structure-ambiguity-and-complexity\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,30]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,12,30]]},"published-print":{"date-parts":[[2020,12,30]]}},"URL":"https:\/\/doi.org\/10.71448\/bcds2011-3","relation":{},"ISSN":["3072-2926"],"issn-type":[{"value":"3072-2926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,30]]}}}