文献

J-GLOBAL ID：201902282187496987   整理番号：19A2607967

決定論的,交代的およびBoole有限オートマトン上の正方形【JST・京大機械翻訳】

Square on Deterministic, Alternating, and Boolean Finite Automata

著者 (2件)： Jiraskova Galina (Mathematical Institute, Slovak Academy of Sciences, Gresakova 6, 040 01 Kosice, Slovakia) ,  Krajnakova Ivana (Mathematical Institute, Slovak Academy of Sciences, Gresakova 6, 040 01 Kosice, Slovakia)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 30  号： 6-7  ページ： 1117-1134  発行年： 2019年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 著者らは,決定論的,交互的,およびBooleオートマトンによって表現される言語に関する正方形演算の状態複雑性を調査した。[数式:原文を参照]のような各kに対して,n状態決定論的有限オートマトンにより受理された二値言語を記述し,その二乗の状態複雑性に関する上限[数式:原文を参照]を満たすk最終状態を持つ。[数式:原文を参照]の場合,対応する上限は満たされないことを示した。それらの半分が最終的な[数式:原文を参照]状態を持つ正方形に対する二値決定論的証拠を用いて,交互およびBooleオートマトン上での二乗演算の複雑さに対するタイトな上限[数式:原文を参照]および[数式:原文を参照]を得た。Copyright 2019 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *オートマトン ,  言語 ,  *有限オートマトン ,  演算
準シソーラス用語： *決定論 , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (3件)： 交代 ,  有限オートマトン ,  正方形