論文

査読有り
2015年2月

Abelian properties of Parry words

THEORETICAL COMPUTER SCIENCE
  • Ondrej Turek

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.

リンク情報
DOI
https://doi.org/10.1016/j.tcs.2014.11.024
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000349198000003&DestApp=WOS_CPL
URL
http://arxiv.org/abs/1406.1876
ID情報
  • DOI : 10.1016/j.tcs.2014.11.024
  • ISSN : 0304-3975
  • eISSN : 1879-2294
  • Web of Science ID : WOS:000349198000003

エクスポート
BibTeX RIS