文献

J-GLOBAL ID：202202251025293519   整理番号：22A0735083

部分語のための周期性補題【JST・京大機械翻訳】

A periodicity lemma for partial words

著者 (5件)： Kociumaka Tomasz (Department of Computer Science, Bar Ilan University, 5290002 Ramat Gan, Israel) ,  Kociumaka Tomasz (Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland) ,  Radoszewski Jakub (Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland) ,  Rytter Wojciech (Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland) ,  Walen Tomasz (Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland)
資料名： Information and Computation  (Information and Computation)
巻： 283  ページ： Null  発行年： 2022年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ここでは,L(h,p,q)が最小長さであるような関数L(h,p,q)を調べ,周期性補助定理の自然拡張がhホールと(いわゆる強い)周期p,qを持つ部分単語に対して有効であることを保証する。一連の論文において,pとqに関する長さ関数のための公式を,各固定h≦7に対して提供した。そのような公式の一般構造を解読し,O(h)片を持つ区分的線形関数で表現される任意のパラメータhに対する長さ関数の完全な特性化を与えた。また,O(log p+log q)時間における長さ関数を評価する方法を示し,それは,以前に知られている最良のO(p+q)時間アルゴリズムの改善である。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *関数 ,  パラメータ ,  キャラクタリゼーション ,  単語
準シソーラス用語： *周期性 ,  線形関数 ,  *補題 , 【Automatic Indexing@JST】

著者キーワード (4件)： 部分語 ,  ファインとウィルフの周期性 ,  連分数 ,  標準Sturmian語

分類 (5件)： 火山地質学一般  (DE07070L) ,  物理化学一般  (CB01010X) ,  信号理論  (ND02020G) ,  非線形光学  (BD05000T) ,  通信網  (ND07030A)

タイトルに関連する用語 (2件)： 周期性 ,  補題