اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDecidability of the HD0L ultimate periodicity problem
145
0
0.0
(
0
)
تأليف
Fabien Durand
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we prove the decidability of the HD0L ultimate periodicity problem.
قيم البحث
اقرأ أيضاً
The main result of this paper is the decidability of the membership problem for $2times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2times 2$ integer matrices $M_1,dots,M_n$ and $M$ decides
whether $M$ belongs to the semigroup generated by ${M_1,dots,M_n}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $mathrm{GL}(2,mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
In this paper I would like to witness the mathematical inventiveness of G. Rauzy through personnal exchanges I had with him. The objects that will emerge will be used to treat the decidability of the HD 0 L $omega$-equivalence and periodicity problems in the primitive case.
We prove that the uniform recurrence of morphic sequences is decidable. For this we show that the number of derived sequences of uniformly recurrent morphic sequences is bounded. As a corollary we obtain that uniformly recurrent morphic sequences are primitive substitutive sequences.
Characterizations graphs of some classes to induce periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. Here, we focus on the perio
dicity of the Grover walks on distance-regular graphs. The distance-regular graph can be regarded as a kind of generalization of the strongly regular graphs and the typical graph with an equitable partition. In this paper, we find some classes of such distance-regular graphs and obtain some useful necessary conditions to induce periodic Grover walks on the general distance-regular graphs. Also, we apply this necessary condition to give another proof for the strong regular graphs.
A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. v{C}erny conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most
$(n-1)^2$. We introduce the notion of aperiodically $1-$contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the v{C}erny conjecture holds for aperiodically $1-$contracting automata. As a special case, we prove some results for circular automata.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
