اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPermutation Complexity Related to the Letter Doubling Map
37
0
0.0
(
0
)
تأليف
Steven Widmer
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a countable set X (usually taken to be the natural numbers or integers), an infinite permutation, pi, of X is a linear ordering of X. This paper investigates the combinatorial complexity of infinite permutations on the natural numbers associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map. An upper bound for the complexity is found for general words, and a formula for the complexity is established for the Sturmian words and the Thue-Morse word.
قيم البحث
اقرأ أيضاً
Here, we study some measures that can be represented by infinite Riesz products of 1-periodic functions and are related to the doubling map. We show that these measures are purely singular continuous with respect to Lebesgue measure and that their di
stribution functions satisfy super-polynomial asymptotics near the origin, thus providing a family of extremal examples of singular measures, including the Thue--Morse measure.
3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation graphs.
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems -- from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus
quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.
We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(mathrm{tw}(G) + log n)}$, where $mathrm{tw}(G)$ is the treewidth of $G$. Our main result is that this bound is tight for graphs contained in minor-closed classes.
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequen
tial update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is textbf{P}-Hard.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
