文献

J-GLOBAL ID：201702244038190187   整理番号：17A1185877

プレフィックス正規語とプレフィックス正規形について【Powered by NICT】

On prefix normal words and prefix normal forms

著者 (5件)： Burcsi Peter (Dept. of Computer Algebra, Eotvos Lorand Univ., Budapest, Hungary) ,  Fici Gabriele (Dip. di Matematica e Informatica, University of Palermo, Italy) ,  Liptak Zsuzsanna (Dip. di Informatica, University of Verona, Italy) ,  Ruskey Frank (Dept. of Computer Science, University of Victoria, Canada) ,  Sawada Joe (School of Computer Science, University of Guelph, Canada)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 659  ページ： 1-13  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 1プレフィックス正規語が因子は同じ長さのプレフィックス以上1Sを持たないという性質を持つ二元語である同様に定義される0プレフィックス正常ワード。これらの語を索引つき二進乱雑パターンマッチの文脈,目的は,単語が与えられた数の1Sと0Sの(与えられたParikhベクトル)と因子を持っているかどうかを決定することで生じる。各バイナリー語が単語の因子のParikhベクトルのセットを有している。プレフィックス正規語を用いて,その要因のParikhベクトルの同じセットを持つ二進語の同値類の特性化を提供する。プレフィックス正規語の言語は文脈自由ではなく,前ネックレスの言語,Lyndon語の出力のプレフィックスであるに含まれる厳密であることを証明した。pnw(n),十分に大きなn,2~ 4√nlgn≦pnw(n)≦2~n lgn+1,ことを示し,長さnのプレフィックス正規語の数の計数結果を与えた。固定密度(1Sの数)に対して,長さnと密度Dのプレフィックス正規語の数の通常の母関数は有理関数であることを示した。最後に,pnw(n)に関する実験結果を与え,さらに特性を検討し,述べる未解決の問題。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： パターンマッチング ,  母関数 ,  単語 ,  キャラクタリゼーション ,  *ベクトル ,  言語
準シソーラス用語： 有理関数 ,  計数 ,  *プレフィックス , 【Automatic Indexing@JST】

著者キーワード (7件)： プレフィックス正規語 ,  プレフィックス正規形 ,  二元言語 ,  二成分乱雑パターンマッチング ,  前ネックレス ,  Lyndon語 ,  数え上げ

分類 (1件)： 数理言語学  (JB05000V)

タイトルに関連する用語 (1件)： プレフィックス