On the Complexity of Automatic Complexity

Kjos-Hanssen, B

Kjos-Hanssen, B (reprint author), Univ Hawaii Manoa, Dept Math, 2565 McCarthy Mall, Honolulu, HI 96822 USA.

THEORY OF COMPUTING SYSTEMS, 2017; 61 (4): 1427

Abstract

Generalizing the notion of automatic complexity of individual words due to Shallit and Wang, we define the automatic complexity A(E) of an equivalence......

Full Text Link


Links

期刊讨论 | 中国SCI论文 | 期刊主页 | 投稿经验 | 杂志官网 | 投稿链接 | 作者需知 | PMC链接 | Pubmed全文检索