EUVIMEDEUVIMED entdecken
Crossref

From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity

Arto Salomaa

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →