On M-unambiguity of Parikh matrices
Abstract
The Parikh matrix mapping was introduced by Mateescu et al. in 2001 as a canonical generalization of the classical Parikh mapping. The injectivity problem of Parikh matrices, even for ternary case, has withstanded numerous attempts over a decade by various researchers, among whom is Serbanuta. Certain M-ambiguous words are crucial in Serbanuta's findings about the number of M-unambiguous prints. We will show that these words are in fact strongly M-ambiguous, thus suggesting a possible extension of Serbanuta’s work to the context of strong M-equivalence. In addition, initial results pertaining to a related conjecture by Serbanuta will be presented.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2020.4.1.1
References
A. Atanasiu, Binary amiable words, Internat. J. Found. Comput. Sci. 18 (2007), 387–400.
A. Atanasiu, Parikh matrices, amiability and Istrail morphism, Internat. J. Found. Comput. Sci. 21 (2010), 1021–1033.
A. Atanasiu, R. Atanasiu and I. Petre, Parikh matrices and amiable words, Theoret. Comput. Sci. 390 (2008), 102–109.
S. Fosse and G. Richomme, Some characterizations of Parikh matrix equivalent binary words, Inform. Process. Lett. 92 (2004), 77–82.
K. Mahalingam and K.G. Subramanian, Product of Parikh matrices and commutativity, In- ternat. J. Found. Comput. Sci. 23 (2012), 207–223.
A. Mateescu, A. Salomaa, K.Salomaa and S. Yu, A sharpening of the Parikh mapping, Theor. Inform. Appl. 35 (2001), 551–564.
R.J. Parikh, On context-free languages, J. Assoc. Comput. Mach. 13 (1966), 570–581.
A. Salomaa, On the injectivity of Parikh matrix mappings, Fund. Inform. 64 (2005), 391–404.
A. Salomaa, Criteria for the matrix equivalence of words, Theoret. Comput. Sci. 411 (2010), 1818–1827.
V.N. S ̧erba ̆nu ̧ta ̆, On Parikh matrices, ambiguity, and prints, Internat. J. Found. Comput. Sci. 20 (2009), 151–165.
V.N. S ̧erba ̆nu ̧ta ̆ and T.F. S ̧erba ̆nu ̧ta ̆, Injectivity of the Parikh matrix mappings revisited, Fund. Inform. 73 (2006), 265–283.
W.C. Teh, Parikh matrices and strong M-equivalence, Internat. J. Found. Comput. Sci. 27 (2016), 545–556.
W.C. Teh, On core words and the Parikh matrix mapping, Internat. J. Found. Comput. Sci. 26 (2015), 123–142.
W. C. Teh, Parikh matrices and Parikh rewriting systems, Fund. Inform. 146(2016), 305–320.
W.C. Teh, Separability of M-equivalent words by morphisms, Internat. J. Found. Comput. Sci. 27 (2016), 39–52.
W.C. Teh and A. Atanasiu, On a conjecture about Parikh matrices, Theoret. Comput. Sci. 628 (2016), 30–39.
W.C. Teh, A. Atanasiu and G. Poovanandran, On strongly M-unambiguous prints and Serbanuta ̆s conjecture for Parikh matrices, Theoret. Comput. Sci. 719 (2018), 86–93.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.