اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Finiteness Problem for classes of modular lattices
100
0
0.0
(
0
)
تأليف
Christian Herrmann
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Finiteness Problem is shown to be unsolvable for any sufficiently large class of modular lattices.
قيم البحث
اقرأ أيضاً
We study the computational complexity of satisfiability problems for classes of simple finite height (ortho)complemented modular lattices $L$. For single finite $L$, these problems are shown tobe $mc{NP}$-complete; for $L$ of height at least $3$, equ
ivalent to a feasibility problem for the division ring associated with $L$. Moreover, it is shown that the equational theory of the class of subspace ortholattices as well as endomorphism *-rings (with pseudo-inversion) of finite dimensional Hilbert spaces is complete for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This results extends to the category of finite dimensional Hilbert spaces, enriched by pseudo-inversion.
This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness
and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure.
The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Gi
ven a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.
Henle, Mathias, and Woodin proved that, provided that $omegarightarrow(omega)^{omega}$ holds in a model $M$ of ZF, then forcing with $([omega]^{omega},subseteq^*)$ over $M$ adds no new sets of ordinals, thus earning the name a barren extension. Moreo
ver, under an additional assumption, they proved that this generic extension preserves all strong partition cardinals. This forcing thus produces a model $M[mathcal{U}]$, where $mathcal{U}$ is a Ramsey ultrafilter, with many properties of the original model $M$. This begged the question of how important the Ramseyness of $mathcal{U}$ is for these results. In this paper, we show that several classes of $sigma$-closed forcings which generate non-Ramsey ultrafilters have the same properties. Such ultrafilters include Milliken-Taylor ultrafilters, a class of rapid p-points of Laflamme, $k$-arrow p-points of Baumgartner and Taylor, and extensions to a class of ultrafilters constructed by Dobrinen, Mijares and Trujillo. Furthermore, the class of Boolean algebras $mathcal{P}(omega^{alpha})/mathrm{Fin}^{otimes alpha}$, $2le alpha<omega_1$, forcing non-p-points also produce barren extensions.
We prove a strong non-structure theorem for a class of metric structures with an unstable pair of formulae. As a consequence, we show that weak categoricity (that is, categoricity up to isomorphisms and not isometries) implies severa
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
