文献

J-GLOBAL ID：202002241977794914   整理番号：20A0332787

部分微分変換器の平均状態計算量について【JST・京大機械翻訳】

On the Average State Complexity of Partial Derivative Transducers

著者 (4件)： Konstantinidis Stavros (Saint Mary’s University, Halifax, NS, Canada) ,  Machiavelo Antonio (CMUP & DM, Faculdade de Ciencias da Universidade do Porto, Porto, Portugal) ,  Moreira Nelma (CMUP & DCC, Faculdade de Ciencias da Universidade do Porto, Porto, Portugal) ,  Reis Rogerio (CMUP & DCC, Faculdade de Ciencias da Universidade do Porto, Porto, Portugal)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12011  ページ： 174-186  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 二次元正規表現は二つのアルファベット上の合理的関係を表す。本論文では,基本項が通常の正規表現(1D)の対である(一般的)2D表現に対して定義できる部分微分標準変換器([数式:原文を参照])の平均状態複雑性を研究した。最悪の場合には,[数式:原文を参照]の状態数は[数式:原文を参照]となり得るが,nは表現の大きさで,漸近的に,平均値は[数式:原文を参照]により上記から制限される。さらに,漸近的および平均的に,2D発現のアルファベットサイズは,その発現のサイズの半分である。すべての結果は,代数曲線によって暗黙的に定義されたパラメータ化された組合せクラスの生成関数を考慮した解析的組合せの枠組みにおいて得られる。特に,著者らは以前の研究で開発された方法を広いクラスの解析関数に一般化した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 正規表現 ,  *微分 ,  変換器 ,  解析関数 ,  一次元 ,  *計算量 ,  母関数 ,  パラメタリゼーション ,  二次元
準シソーラス用語： 代数曲線 , 【Automatic Indexing@JST】

分類 (1件)： 分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (4件)： 微分 ,  変換器 ,  平均 ,  計算量