文章基本信息

标题：Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
本地全文：下载
作者：Julien Destombes ; Andrei Romashchenko
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-17
DOI：10.4230/LIPIcs.STACS.2019.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on Z^2 with very low block complexity: the number of globally admissible patterns of size n x n grows only as a polynomial in n.
关键词：Sofic shifts; Block complexity; Kolmogorov complexity