Complexity of Lambek Calculi with Modalities and of Total Derivability in Grammars

Algebra and Logic - The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of...     

Sufficient conditions for effective translation of locally generic queries

This paper continues investigations into the database of queries of first-order language theory. It is known that for many decidable theories, the collapse result holds: each locally generic query is equivalent to some restricted query. But, until now, the problem of effective construction of this query remains almost unexplored. We use earlier results of the author on the construction of a method of effective obtaining this query. The method is rather general and applicable, for example, to the Presburger arithmetic and the real number theory.     

Pseudofinite homogeneity, isolation, and reducibility

It has been proved (by S. M. Dudakov and M. A. Taitslin) that the reducibility of some models of a theory implies the second pseudofinite homogeneity property for this theory. We prove the converse, namely, that any theory with the first or the second pseudofinite homogeneity property has a reducible model and, therefore, possesses the second isolation property. This also proves the equivalence of the second isolation property and the second pseudofinite homogeneity property, in contrast to the first pseudofinite homogeneity property, which is more general than the first isolation property (this was established by O. V. Belegradek, A. P. Stolboushin, and M. A. Taitslin).     

Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition

Earlier, Belegradek, Stolboushkin, and Taitslin proved that the collapse result holds in the theory of natural numbers with addition, i.e., each locally generic query using addition can be written without it. In this paper, we use the sufficient conditions of the collapse result obtained by Taitslin to prove that it holds in any extensions of the Presburger arithmetic by a unary function compatible with addition. The notion of a function compatible with addition was proposed by A. L. Semenov.