文献

J-GLOBAL ID：201802219161986914   整理番号：18A2060428

明確な有限オートマトン上の演算【JST・京大機械翻訳】

Operations on Unambiguous Finite Automata

著者 (3件)： Jirasek Jozef Jr. (Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada) ,  Jiraskova Galina (Mathematical Institute, Slovak Academy of Sciences, Gresakova 6, 040 01 Kosice, Slovakia) ,  Sebej Juraj (Institute of Computer Science, Faculty of Science, P. J. Safarik University, Jesenna 5, 040 01 Kosice, Slovakia)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 29  号： 5  ページ： 861-876  発行年： 2018年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 非決定論的有限オートマトンは,それがあらゆる入力ストリングに関するほとんどの受容計算を持つならば,明白である。著者らは,あいまいな有限オートマトンによって表現される言語に関する基本的規則的操作の状態複雑性を調査した。反転(n),交差([数式:原文を参照]),左と右の指数([数式:原文を参照]),正の閉鎖([数式:原文を参照]),星([数式:原文を参照]),シャッフル([数式:原文を参照]),および連結([数式:原文を参照])に対するタイトな上限を得た。緊密性を証明するために,著者らは,交差と左右のための二値アルファベット,星と正の閉鎖のための三元アルファベット,シャッフルのための5文字アルファベット,および連接のための7文字アルファベットを使用した。相補性のために,著者らは[数式:原文を参照]に対する自明な上限[数式:原文を参照]を減少させた。また,結合と正方形に対するいくつかの部分的結果を得た。Copyright 2018 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 曖昧さ ,  言語 ,  相補性 ,  *有限オートマトン
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 明確な有限オートマトン ,  規則的運用 ,  状態の複雑さ

分類 (1件)： オートマトン理論  (JB04000O)

タイトルに関連する用語 (1件)： 有限オートマトン