کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653351 | 1632766 | 2016 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of short rectangles and periodicity
ترجمه فارسی عنوان
پیچیدگی مستطیل های کوتاه و دوره ای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The Morse–Hedlund Theorem states that a bi-infinite sequence ηη in a finite alphabet is periodic if and only if there exists n∈Nn∈N such that the block complexity function Pη(n)Pη(n) satisfies Pη(n)≤nPη(n)≤n. In dimension two, Nivat conjectured that if there exist n,k∈Nn,k∈N such that the n×kn×k rectangular complexity Pη(n,k)Pη(n,k) satisfies Pη(n,k)≤nkPη(n,k)≤nk, then ηη is periodic. Sander and Tijdeman showed that this holds for k≤2k≤2. We generalize their result, showing that Nivat’s Conjecture holds for k≤3k≤3. The method involves translating the combinatorial problem to a question about the nonexpansive subspaces of a certain Z2Z2 dynamical system, and then analyzing the resulting system.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 52, Part A, February 2016, Pages 146–173
Journal: European Journal of Combinatorics - Volume 52, Part A, February 2016, Pages 146–173
نویسندگان
Van Cyr, Bryna Kra,