Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Finiteness Problem for classes of modular lattices
100
0
0.0
(
0
)
Authors
Christian Herrmann
Ask ChatGPT about the research
No Arabic abstract
The Finiteness Problem is shown to be unsolvable for any sufficiently large class of modular lattices.
rate research
Read More
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$, equivalent 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. Given 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. Moreover, 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
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
