Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of equational decision problems for finite height(ortho)complemented modular lattices
129
0
0.0
(
0
)
Authors
Christian Herrmann
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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, the border can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q;<); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.
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 infinite words. Many classical decision problems are studied in formal language theory and in automata theory and arise now naturally about recognizable languages of infinite pictures. We first review in this paper some recent results of [Fin09b] where we gave the exact degree of numerous undecidable problems for Buchi-recognizable languages of infinite pictures, which are actually located at the first or at the second level of the analytical hierarchy, and highly undecidable. Then we prove here some more (high) undecidability results. We first show that it is $Pi_2^1$-complete to determine whether a given Buchi-recognizable languages of infinite pictures is unambiguous. Then we investigate cardinality problems. Using recent results of [FL09], we prove that it is $D_2(Sigma_1^1)$-complete to determine whether a given Buchi-recognizable language of infinite pictures is countably infinite, and that it is $Sigma_1^1$-complete to determine whether a given Buchi-recognizable language of infinite pictures is uncountable. Next we consider complements of recognizable languages of infinite pictures. Using some results of Set Theory, we show that the cardinality of the complement of a Buchi-recognizable language of infinite pictures may depend on the model of the axiomatic system ZFC. We prove that the problem to determine whether the complement of a given Buchi-recognizable language of infinite pictures is countable (respectively, uncountable) is in the class $Sigma_3^1 setminus (Pi_2^1 cup Sigma_2^1)$ (respectively, in the class $Pi_3^1 setminus (Pi_2^1 cup Sigma_2^1)$).
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 probability function, equational axioms are provided for expected value, variance, covariance, and correlation squared, each defined for conditional values. Finite support summation is introduced as a binding operator on meadows which simplifies formulating requirements on probability mass functions with finite support. Conditional values are related to probability mass functions and to random variables. The definitions are reconsidered in a finite dimensional setting.
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 needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
