2015年2月
Abelian properties of Parry words
THEORETICAL COMPUTER SCIENCE
- 巻
- 566
- 号
- 開始ページ
- 26
- 終了ページ
- 38
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2014.11.024
- 出版者・発行元
- ELSEVIER SCIENCE BV
Abelian complexity of a word u is a function that counts the number of pairwise non-abelian-equivalent factors of u of length n. We prove that for any c-balanced Parry word u, the values of the abelian complexity function can be computed by a finite-state automaton. The proof is based on the notion of relative Parikh vectors. The approach works for any function F (n) that can be expressed in terms of the set of relative Parikh vectors corresponding to the length n. For example, we show that the balance function of a c-balanced Parry word is computable by a finite-state automaton as well. (C) 2014 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.tcs.2014.11.024
- ISSN : 0304-3975
- eISSN : 1879-2294
- Web of Science ID : WOS:000349198000003