ﻻ يوجد ملخص باللغة العربية
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.
The Finiteness Problem is shown to be unsolvable for any sufficiently large class of modular lattices.
Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes coincides with an important dichotomy in universal algebra; in particular, t
Altenbernd, Thomas and Wohrle have considered in [ATW02] acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Buchi and Muller ones, firstly used for
An equational axiomatisation of probability functions for one-dimensional event spaces in the language of signed meadows is expanded with conditional values. Conditional values constitute a so-called signed vector meadow. In the presence of a probabi
In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is n