On strongly \(M\)-unambiguous prints and Şerbǎnuţǎ's conjecture for Parikh matrices
type: Item
instance of: scholarly article
title: On strongly \(M\)-unambiguous prints and Şerbǎnuţǎ's conjecture for Parikh matrices
zbMATH Open document ID: 1392.68334
author: Wen Chean Teh
author: Adrian Atanasiu
author: Ghajendran Poovanandran
published in: Theoretical Computer Science
publication date: 2018-03-12T00:00:00Z
review text: Parikh vectors record the number of occurrences of letters in words. Parikh matrices, which extend Parikh vectors, also preserve information on the number of occurrences of certain subwords. The injectivity problem, which relates to Parikh matrices, has been open for almost a decade. The problem is to characterize \(M\)-equivalent words, i.e., words that share the same Parikh matrix (a word is \(M\)-unambiguous if it is not \(M\)-equivalent to any distinct word). The authors relate this problem to the notion of print of a word and strong \(M\)-equivalence, an order-independent alternative to \(M\)-equivalence. They first generalize some work of Serbanuta on prints and \(M\)-unambiguity to strong \(M\)-equivalence. Then they show that for any alphabet, there exist only finitely many strongly \(M\)-unambiguous prints. They finally disprove a conjecture of Şerbănuţă [\textit{V. N. Şerbănuţă} and \textit{T. F. Şerbănuţă}, Fundam. Inform. 73, No. 1--2, 265--283 (2006; Zbl 1104.68058)] saying that the \(M\)-unambiguity of a word implies the \(M\)-unambiguity of the word's print. The authors also discuss a number of open problems.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6849002
zbMATH Keywords: injectivity problem
zbMATH Keywords: subword
zbMATH Keywords: print word
zbMATH Keywords: \(M\)-equivalence
zbMATH Keywords: strong \(M\)-equivalence
reviewed by: F. Blanchet-Sadri
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.11.016
OpenAlex ID: W2769085146
Wikidata QID: Q123121911
cites work: BINARY AMIABLE WORDS
cites work: Parikh matrices and amiable words
cites work: Q4329174
cites work: A New Operator over Parikh Languages
cites work: An introduction to the Heisenberg group and the sub-Riemannian isoperimetric problem
cites work: Some characterizations of Parikh matrix equivalent binary words
cites work: Product of Parikh matrices and commutativity
cites work: MATRIX INDICATORS FOR SUBWORD OCCURRENCES AND AMBIGUITY
cites work: A sharpening of the Parikh mapping
cites work: Subword histories and Parikh matrices
cites work: On Context-Free Languages
cites work: Strong (2 ⋅ t) and Strong (3 ⋅ t) Transformations for Strong M-Equivalence
cites work: Connections between subwords and certain matrix mappings
cites work: Independence of certain quantities indicating subword occurrences
cites work: Criteria for the matrix equivalence of words
cites work: ON PARIKH MATRICES, AMBIGUITY, AND PRINTS
cites work: Q3409998
cites work: On Core Words and the Parikh Matrix Mapping
cites work: Parikh Matrices and Parikh Rewriting Systems
cites work: Parikh matrices and strong \(M\)-equivalence
cites work: Separability of \(M\)-equivalent words by morphisms
cites work: On a conjecture about Parikh matrices
cites work: Core words and Parikh matrices
DOI: 10.1016/J.TCS.2017.11.016
Recommended article: ON PARIKH MATRICES, AMBIGUITY, AND PRINTS
Recommended article: PARIKH MATRICES, AMIABILITY AND ISTRAIL MORPHISM
Recommended article: Q4905133
Recommended article: Parikh matrices and strong \(M\)-equivalence
Recommended article: Order of weak \(M\)-relation and Parikh matrices
Recommended article: MATRIX INDICATORS FOR SUBWORD OCCURRENCES AND AMBIGUITY
Recommended article: A New Operator over Parikh Languages
Recommended article: Strong (2 ⋅ t) and Strong (3 ⋅ t) Transformations for Strong M-Equivalence
Recommended article: Separability of \(M\)-equivalent words by morphisms
Recommended article: SUBWORD OCCURRENCES, PARIKH MATRICES AND LYNDON IMAGES
description: scientific article; zbMATH DE number 6849002