文献

J-GLOBAL ID：202002231137239614   整理番号：20A0181280

準線形空間を伴う1ウェイおよび2ウェイの交代マルチ-カウンタ・オートマトン

1-Way versus 2-Way Alternating Multi-Counter Automata with Sublinear Space

著者 (2件)： YOSHINAGA Tsunehiro (徳山工高専) ,  SAKAMOTO Makoto (Univ. Miyazaki)
資料名： 徳山工業高等専門学校研究紀要(Web)  (Research Reports of National Institute of Technology, Tokuyama College (Web))
号： 42  ページ： 1-4 (WEB ONLY)  発行年： 2018年12月 
JST資料番号： U1082A  ISSN： 2432-5627  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： ・マルチ-カウンタ・オートマトンに関する基本事項の解説。
・交代マルチ-カウンタ・オートマトン(AMCA)の定義。
・準線形空間制約付きの1ウェイおよび2ウェイAMCAの受容パワーの検討。
・strong-1ACA,weak-1ACA,strong-2ACA,weak-2ACA(nACAは,交代nカウンタ・オートマトン)を導入し,それらの受容パワーを検討したほか,それらのnACA間に成り立つ数学的関係を証明。

シソーラス用語： *オートマトン理論 ,  *計数器 ,  準線形理論 ,  計算量 ,  数学的性質 ,  受容
準シソーラス用語： カウンタ ,  計算の複雑さ ,  準線形空間

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

タイトルに関連する用語 (5件)： 線形空間 ,  交代 ,  マルチ ,  カウンタ ,  オートマトン