Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433787 | Theoretical Computer Science | 2016 | 10 Pages |
Abstract
Based on Salomaa's characterization of M-equivalence, Atanasiu conjectured that a certain natural generalization of ME-equivalence solves the injectivity problem of Parikh matrices for the ternary alphabet. This paper refutes his conjecture but continues to study the interesting proposed Thue system. Characterization of certain irreducible elementary transformations under this system is obtained. Furthermore, these transformations are further scrutinized in terms of their replaceability by simpler ones.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wen Chean Teh, Adrian Atanasiu,