Subword histories and Parikh matrices
Subword histories and Parikh matrices
复制标题
DOI：
10.1016/j.jcss.2003.04.001
复制
发表时间：
2004-02-01
影响因子：
1.1
通讯作者：
Yu, S
中科院分区：
文献类型：
--
作者：
Mateescu, A;Salomaa, A;Yu, S
最近推出的 Parikh 矩阵提供了有关单词的更多信息，而不仅仅是每个字母出现的次数。在本文中，我们介绍了密切相关的子词历史概念，并获得了一系列一般结果：乘积消除、等价的可判定性和范式。我们还研究了证明此类结果有效性的总体方法。建立了子词出现的“柯西型”一般不等式。 (C) 2003 Elsevier Inc. 保留所有权利。
Parikh matrices recently introduced give much more information about a word than just the number of occurrences of each letter. In this paper we introduce the closely related notion of a subword history and obtain a sequence of general results: elimination of products, decidability of equivalence, and normal form. We also investigate overall methods for proving the validity of such results. A general inequality of "Cauchy type" for subword occurrences is established. (C) 2003 Elsevier Inc. All rights reserved.