Some publications of Michael Taitslin

Michael Taitslin.
Comparison of expressive power of some query languages
for databases.
Proceedings of the Steklov Institute of Mathematics, vol.274, Steklov Institute of Mathematics, Moscow ,
2011, pages 273–288.
A version of the SQL language and a version of the stratified Datalog
are considered, and it is proved that each of these languages can be
translated into the other.

Michael Taitslin.
Isomorphisms and strong finite projective classes of commutative semigroups.
Tributes, Volume 13, Proofs, Categories and Computations, Essays in Honor of Grigori Mints, Soloman Feferman and Wilfried Sieg, editors,
College Publications, London , 2010, pages 243  250.
In ``Sverdlovsk notebook" (Sverdlovsk, 1969), I proposed a question: Are any too firstorder equivalent
finitely generated commutative semigroups isomorphic?
In 1970, B.I.Zilber answered the question negatively. A question arises: In what language,
any equivalent over the language finitely generated commutative semigroups are isomorphic?
In the note, we propose such a language. Moreover, we prove that there is an algorithm which for a given finite set of generators,
a given finite set of defining relations of a commutative semigroup for the generators,
and a closed formula of the language decides whether the formula holds in the semigroup.

Sergey Dudakov, and Michael Taitslin.
The collapse result for database query languages.
Uspehi Matematicheskih Nauk, 61(2): 3  66, 2006.
Russian
In the survey, we present collapse results in database theory
obtained by members of the Tver State University seminar for
theoretical foundation of Computer Science.
The Isolation
and Pseudofinite Homogeneity properties
and universes without independent property are
in the focus of our investigations.
For these universes, we prove the Baldwin  Benedikt theorem
as to reducibility.
For reducible theories, we prove the Dudakov's theorem
which says that any such theory is bound.
For reducible and bound theories, we prove the relative
isolation property and the collapse theorem.
We note that the notions of reducibility and isolation are equivalent.
On the other hand, we present Dudakov's results
which show that the effective reducible theories with
an effective almost indiscernible sequence have
the effective translation of the locally generic extended queries
to restricted ones.
We also present a Dudakov's example of an expansion of Presburger
Arithmetic such that the firstorder theory of the expansion is decidable,
and the collapse theorem does not hold for the expansion. The example gives
a negative answer for known problems.

M.A. Taitslin.
A problem from PTIME and not from NLogSpace.
In Proceedings of Tver State University
series "Applied Mathematics", issue 2
Tver State University, Tver, 2005, pages 5  22
Russian
We propose a problem in PTIME which, we believe, is not in
in NLogSpace. If it is the case, it would
settle a long staying open problem of Stephen A.Cook posted in 1969.

M.A. Taitslin.
Restricted pseudofinite homogeneity and restricted isolation.
In Proceedings of Tver State University
series "Applied Mathematics", issue 1
Tver State University, Tver, 2003, pages 5  15
Russian
It is proposed a relativize version of results from
O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Extended ordergeneric queries.
Annals of Pure and Applied Logic, 97(1 3):85 125, 1999
as to the
collapse theorem. It is investigated so called Preducible theories. It is
proved that, for the Preducible theories, a version of Pseudofinite
Homogeneity Property holds. So the collapse theorem holds for Preducible
theories.

M.A. Taitslin.
Translation results in database theory.
In Complex systems: data processing, simulation, and
optimization
Tver State University, Tver, 2002, pages 5 23
Russian
It is investigated expansions of Presburger's arithmetics by a
weakly monotone unary function. For the expansions, it is
proposed a sufficient condition for truth of the collapse theorem.
The condition holds for the Semenov's functions and for other ones
proposed by the author. It is a natural way to organize a
quantifier elimination for such an expansion. So, if you can
organize a good quantifier elimination for such an expansion, then
the collapse theorem holds for the expansion.

M.A. Taitslin.
Collapse results in database theory.
Finite Model Theory Workshop, Bedlewo, Poland, 2003.

M.A. Taitslin.
A general condition for collapse results.
Annals of Pure and Applied Logic, 113(1 3):323 330, 2001.
In
O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Extended ordergeneric queries.
Annals of Pure and Applied Logic, 97(1 3):85 125, 1999
the collapse result theorem was proved for locally generic
queries over ordered domains with the Pseudofinite Homogeneity Property.
In a very interesting paper of Baldwin and Benedikt the collapse result
theorem was proved for locally generic queries over ordered domains without
the independence property. It means that over such a domain, ordergeneric
extended queries fail to express more than restricted queries.
I propose
a more general version for the theorem. Actually, for the
theories without the independence property, a version of the Pseudofinite
Homogeneity Property holds.

O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
On problems of databases over a fixed infinite universe.
In Logic, algebra, and computer science. Helena Rasiowa in
memoriam, volume 46 of Banach Center Publications, pages 23 62.
Banach Center, Institute of Mathematics, Polish Academy of Sciences,
Warszawa, 1999.
In the relational model of databases a database state is thought of as a finite
collection of relations between elements. For many applications it is
convenient to prefix an infinite domain where the finite relations
are going to be defined. Often, we also fix a set of domain functions and/or
relations. These functions/relations are infinite by their nature. Some
special problems arise if we use such an approach. In the paper we discuss
some of the problems.
We show that there exists a recursive domain with
decidable theory in which (1) there is no recursive syntax for finite
queries, and in which (2) the statesafety problem is undecidable.
We
provide very general conditions on the FO theory of an ordered domain that
ensure collapse of ordergeneric extended FO queries to pure order queries
over this domain: the Pseudofinite Homogeneity Property and a stronger
Isolation Property. We further distinguish one broad class of ordered
domains satisfying the Isolation Property, the socalled quasiominimal
domains. This class includes all ominimal domains, but also the ordered group
of integer numbers and the ordered semigroup of natural numbers, and some
other domains.
We generalize all the notions to the case of finitely
representable database states  as opposed to finite states  and develop
a general lifting technique that, essentially, allows us to extend any result
of the kind we are interested in, from finite to finitelyrepresentable
states. We show, however, that these results cannot be transferred to
arbitrary infinite states.
We prove that safe Datalogprograms do not have
any effective syntax.

O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Databases over a fixed infinite universe.
Programmirovanie (Programming and Computer Software),
24(1):6 17 (3 10), 1998.
Russian, English translation.
If we prefix an infinite domain where the elements of the keeping database
tables are going to be defined, the problems of finiteness of the answer to a
query and of dependence of query language expressibility on the universe
signature arise. In the paper we discuss some of the problems.

O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Extended ordergeneric queries.
Annals of Pure and Applied Logic, 97(1 3):85 125, 1999.
We consider relational databases organized over an ordered domain with some
additional relations  a typical example is the ordered domain of rational
numbers together with the operation of addition. In the focus of our study
are the firstorder (FO) queries that are invariant under orderpreserving
"permutations"  such queries are called ordergeneric. It has recently
been discovered that for some domains ordergeneric FO queries fail to
express more than pure order queries. For example, every ordergeneric FO
query over rational numbers with + can be rewritten without +. For some
other domains, however, this is not the case.
We provide very general
conditions on the FO theory of the domain that ensure the collapse of
ordergeneric extended FO queries to pure order queries over this domain: the
Pseudofinite Homogeneity Property and a stronger Isolation
Property. We further distinguish one broad class of domains satisfying the
Isolation Property, the socalled quasiominimal domains. This class
includes all the ominimal domains, but also the ordered group of integer
numbers and the ordered semigroup of natural numbers, and some other domains.
An important difference of this paper from the recent series of related
papers is that we generalize all the notions to the case of finitely
representable database states  as opposed to finite states  and develop a
general lifting technique that, essentially, allows us to extend any result
of the kind we are interested in, from finite to finitelyrepresentable
states. We show, however, that these results cannot be transfered to
arbitrary infinite states.

O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Generic queries over quasiominimal domains.
In Logical Foundation of Computer Science, 4th International
Symposium, LFCS'97, Yaroslavl, Russia, July 1997, Proceedings, volume 1234
of LNCS, pages 21 32. SpringerVerlag, 1997.
O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
On ordergeneric queries.
Technical report 96 01, DIMACS, 1996.
O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
Relational expressive power of local generic queries.
Technical report 95 56, DIMACS, 1995.
A.P. Stolboushkin and M.A. Taitslin.
Linear vs. order constraint queries over rational databases.
In Proc. 15th ACM Symp. on Principles of Database Systems,
pages 17 27, 1996.

D.A. Archangelsky and M.A. Taitslin.
A logic for information systems.
Studia Logica, 58(1):3 16, 1997.
A conception of an information system has been introduced by Pavlak. The study
has been continued in works of Pavlak and Orlowska and in works of Vakarelov.
They had proposed some basic relations and had constructed a formal system of
a modal logic that describes the relations and some of their Boolean
combinations. Our work is devoted to a generalization of this approach. A
class of relation systems and a complete calculus construction method for
these systems are proposed. As a corollary of our main result, our paper
contains a solution of a Vakarelov's problem: how to construct a formal
system that describes all the Boolean combinations of the basic relations.
But having considered an unrestricted in some sense relation set we also
present a more formal and general version of this field.
A.P. Stolboushkin and M.A. Taitslin.
Finite queries do not have effective syntax.
In Proc. 14th ACM Symp. on Principles of Database Systems,
pages 277 285, 1995.

A.P. Stolboushkin and M.A. Taitslin.
Safe stratified datalog with integer order does not have syntax.
ACM Trans. on Database Systems, 23(1):100 109, 1998.
Stratified Datalog with integer (gap)order is
considered. A Datalogprogram is said to be safe iff its bottomup processing
terminates on all valid inputs. We prove that safe Datalogprograms do not have
effective syntax in the sense that there is no recursively enumerable set S
of safe Datalogprograms such that every safe Datalogprogram is equivalent
to a program in S.

A.P. Stolboushkin and M.A. Taitslin.
Finite queries do not have effective syntax.
Information and Computation, 153(1):99 116, 1999.
A relational query is called finite, or sometimes safe, iff it
yields a finite answer in every database state.
The set of finite
queries of relational calculus is known to be unsolvable. However, in many
cases it is possible to impose syntactical restrictions on the class of
queries that guarantee finiteness and do not reduce the expressive power of
the calculus.
We show that unfortunately this is not always the case, as
we construct a recursive domain with decidable theory where any solvable (or
enumerable, for that matter) subclass of queries either contains an infinite
query, or misses a finite one.
Using the same example, we further show
undecidability of the problem of statefiniteness, which is, given a
query and a database state, to decide upon finiteness of the query in this
state.
This settles two longstanding open problems in the theory of
relational databases.

I.Kh. Musikaev and M.A. Taitslin.
Flat backtracking prolog for databases: a formal semantics, the
computational complexity and the expressibility.
International Journal of Foundations of Computer Science,
6(1):11 26, 1995.
We construct a polynomialtime algorithm for flat PROLOG. Our algorithm gives a
new flat PROLOG semantics equivalent to previous one. On the other hand, we
show the completeness of flat PROLOG for the polynomial time recognizing.
Thus we propose a description of the class PTIME in terms of the computer
language PROLOG. We also give a similar descriptions for PSPACE and EXPTIME.
For this purpose we consider the extension of flat PROLOG by the mechanism of
adding and deleting clauses during the program execution.

I.Kh. Musikaev and M.A. Taitslin.
Limitations of the program memory and the expressive power of dynamic
logics.
Information and Computation, 103(2):195 203, 1993.
For a dynamic logic L we study dynamic logic L_{n} for which programs allowed
in formulas cannot use more than n variables. We prove that there exists a
structure A of a finite signature such that for any natural n, the logic
L_{n+1} in more expressive over A than L_{n}.

I.Kh. Musikaev and M.A. Taitslin.
On dynamic theories of free algebras.
Math. USSR Sbornik, 66(2):313 327, 1990.
A certain canonical form is introduced for formulas of the logic
L_{
∞,
w
}(n),
and it is proved that every formula of this logic is equivalent
on free algebras to a canonical formula. Do only finitely many programs
suffice for expressing all queries expressible in dynamic logic and
involving
the free algebra under consideration? We answer the question negatively.
A.P. Stolboushkin and M.A. Taitslin.
Dynamic logics.
In V.A. Mel'nikov, editor, Cybernetics and Computer Technology,
volume 2, pages 180 230. Nauka, Moscow, USSR, 1986.
Russian.

A.P. Stolboushkin and M.A. Taitslin.
Deterministic dynamic logic is strictly weaker than dynamic logic.
Information and Control, 57(1):48 55, 1983.
Nondeterminism adds to the expressive power even in presence of quantifiers.
This answers Meyer's question. The proof holds in the presence of firstorder
tests as well as quantifierfree tests.

D.A. Archangelsky, M.I. Dekhtyar, and M.A. Taitslin.
Linear logic for nets with bounded resources.
Annals of Pure and Applied Logic, 78:3 28, 1996.
We introduce a new type of nets with bounded types of distibuted resources
(BRnets). Linear Logic to describe the behaviour of BRnets is defined. It
captures not only consumption of resources but their presence as well.
Theorem of soundness and completeness of the proposed axiomatization is
proved. The PTIME algorithm for the provability problem is proposed for some
particular cases.
D.A. Archangelsky, M.I. Dekhtyar, E.I. Kruglov, I.Kh. Musikaev, and M.A.
Taitslin.
Concurrency problem for Horn fragment of Girard's linear logic.
In Logical Foundation of Computer Science  St.Petersburg'94,
volume 813 of LNCS, pages 18 22. SpringerVerlag, 1994.
D.A. Arhangelsky and M.A. Taitslin.
Linear logic with fixed resources.
Annals of Pure and Applied Logic, 67:3 28, 1994.

A.P. Stolboushkin and M.A. Taitslin.
Is first order contained in an initial segment of PTIME?
In Selected Papers, 8th EATCS Conference on Computer Science
Logic (CSL'94), volume 933 of LNCS, pages 242 248. SpringerVerlag,
1995.
By "initial segments of P" we mean classes DTime(n^{k}). The
question of whether for any fixed signature the firstorder definable
predicates in finite models of this signature are all in an initial segment
of P is shown to be related to other intriguing open problems in
complexity theory and logic, like P=PSpace. The
second part of the paper strengthens the result of Ph. Kolaitis of logical
definability of unambiguous computations.

A.P. Stolboushkin and M.A. Taitslin.
Normalizable linear orders and generic computations in finite models.
Archive for Mathematical Logic, 38(4):257 271, 1999.
We propose an approach that has to do with normalization of a given order
(rather than with defining a linear order from scratch). To this end, we show
that normalizability of linear order is a strictly weaker condition than
definability (say, in the least fixpoint logic), and still allows for
extending ImmermanVardistyle results to generic queries. It seems to be the
weakest such condition. We then conjecture that linear order is normalizable
in the least fixpoint logic for any finitely axiomatizable class of rigid
structures. We also suggest a series of reductions of the conjecture to
specialized classes of graphs, which we believe should simplify further work.

A.P. Stolboushkin and M.A. Taitslin.
Mathematical foundations of computer science, parts 1, 2, 3.
Tver State University, 1998.
Russian book, 367 pages.

M.A. Taitslin.
Model theory.
Novosibirsk State University, 1970.
Russian book, 214 pages.
Basic results. Ultraproducts. Jonson conditions. Universal and homogeneous
structures. Categoricity.

Ju.L. Ershov, E.A. Paljutin, and M.A. Taitslin.
Mathematical Logic.
Novosibirsk State University, 1973.
Russian book, 159 pages.
A textbook for beginners.

V.Ja. Beliaev and M.A. Taitslin.
On elementary properties of existentially closed structures.
Russian Mathematical Surveys, 34(2):39 94, 1979.

M.A. Taitslin.
On the isomorphism problem for commutative semigroups.
Math. USSR Sbornik, 22(1):104 128, 1974.
It is proved the recursive equivalence of the isomorphism problem for
commutative semigroups and the conjugacy problem for finite sequences of
elements in the groups GL(l,Z).

M.A. Taitslin.
Algorithmic problem for commutative semigroups.
Sov.Math.Dokl., 9(1):201 204, 1968.
It is proposed a universal algorithm to solve any problem which can be
formulated in the firstorder language using addition, generators and fixed
finite generated subsemigroups.

Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, and M.A. Taitslin.
Elementary theories.
Russian Mathematical Surveys, 20(4):35 105, 1965.
It is proposed many new approaches to prove decidability and undecidability of
firstorder theories.
M.A. Taitslin.
On free
Wgroups.
Uspehi Matematicheskih Nauk, 16(2):221, 1961.
Russian.
D.M. Smirnov and M.A. Taitslin.
On finitely approximable abelian
Wgroups.
Uspehi Matematicheskih Nauk, 16(2):221 222, 1961.
Russian.
M.A. Taitslin.
On finite approximability of
Wgroups.
Sibirsky Matematichesky journal, 3(1):95 102, 1962.
Russian.
M.A. Taitslin.
Undecidability of the elementary theory of commutative semigroups
with cancelation.
Sibirsky Matematichesky journal, 3(2):308 309, 1962.
Russian.
M.A. Taitslin.
Relatively elementary subspaces in compact Lie algebras.
Algebra i logika, 1(2):30 46, 1962.
Russian.
M.A. Taitslin.
Relatively elementary subspaces in compact Lie algebras.
Sov. Math. Dokl., 144(5):997 998, 1962.
Russian.
D.M. Smirnov and M.A. Taitslin.
On finitely approximable Abelian multi operators groups.
Uspehi Matematicheskih Nauk, 17(5):137 142, 1962.
Russian.
M.A. Taitslin.
Effective inseparability of the set of identically true and the set
of finitely refutable formulas of the elementary theory of the lattices.
Algebra i logika, 1(3):24 38, 1962.
Russian.
Ju.L. Ershov and M.A. Taitslin.
Undecidability of certain theories.
Algebra i logika, 2(5):37 41, 1963.
Russian.
M.A. Taitslin.
Undecidability of elementary theories of certain classes of finite
commutative associative rings.
Algebra i logika, 2(3):29 51, 1963.
Russian.
M.A. Taitslin.
Decidability of certain elementary theories.
Algebra i logika, 3(3):5 12, 1964.
Russian.
Ju.L. Ershov and M.A. Taitslin.
On elementary theories of classes of finite models.
Uspehi Matematicheskih Nauk, 19(2):194 195, 1964.
Russian.
M.A. Taitslin.
On elementary theories of free nilpotent algebras.
Algebra i logika, 3(5 6):57 63, 1964.
Russian.
M.A. Taitslin.
On the theory of finite rings with division.
Algebra i logika, 4(4):103 114, 1965.
Russian.
M.A. Taitslin.
On the elementary theory of classical Lie algebras.
Sov.Math.Dokl., 6:1373 1376, 1965.
M.A. Taitslin.
On elementary theories of commutative semigroups with cancelation.
Algebra i logika, 5(1):51 69, 1966.
Russian.
M.A. Taitslin.
On elementary theories of commutative semigroups.
Algebra i logika, 5(4):55 89, 1966.
Russian.
M.A. Taitslin.
Two remarks on commutative semigroups isomorphism.
Algebra i logika, 6(1):95 116, 1967.
Russian.
M.A. Taitslin.
Some further examples of undecidable theories.
Algebra i logika, 6(3):105 111, 1967.
Russian.
M.A. Taitslin.
On the isomorphism problem for commutative semigroups.
Sibirsky Matematichesky journal, 9(2):375 401, 1968.
Russian.
M.A. Taitslin.
Elementary lattice theories for ideals in polynomial rings.
Algebra and logic, 7:127 129, 1968.
M.A. Taitslin.
On simple ideals in polynomial rings.
Algebra and logic, 7:394 395, 1968.
M.A. Taitslin.
Equivalence of automata with respect to a commutative semigroup.
Algebra i logika, 8(5):553 600, 1969.
Russian.
M.A. Taitslin.
On elementary theories of lattices of subgroups.
Algebra i logika, 9(4):473 483, 1970.
Russian.
M.A. Taitslin.
A remark on categorical quasi varieties.
In 4 International Congress for logic, methodology and
philosophy of science, Abstracts, page 79. Center of Information and
Documentation in Social and Political Sciences, Bucharest, 1971.
A.I. Abakumov, E.A. Paljutin, M.A. Taitslin, and J.E. Shishmarev.
Categorical quasivarieties.
Algebra and logic, 11:1 20, 1972.
M.A. Taitslin.
Non almost strongly minimal totally categorical theory.
In Second Soviet Mathemat.Logic conf., pages 47 48, Moscow,
1972. Steklov math. Inst.
Russian.
O.V. Belegradek and M.A. Taitslin.
Two remarks on the varieties _{m, n}.
Algebra i logika, 11(5):501 508, 1972.
Russian.
M.A. Taitslin.
Existentially closed regular commutative semigroups.
Algebra and logic, 12(6):394 401, 1973.
A.D. Taimanov and M.A. Taitslin.
Elementary theories.
In Encyclopedia "Kibernetika". Institute of Cybernetics,
Ukrainian Academy of Sciences, Kiev, 1974.
Russian.
A.D. Taimanov and M.A. Taitslin.
Model theory.
In Encyclopedia "Kibernetika". Institute of Cybernetics,
Ukrainian Academy of Sciences, Kiev, 1974.
Russian.
A.D. Taimanov and M.A. Taitslin.
Model theory.
In Great Soviet Encyclopedia, volume 16. Soviet Encyclopedia,
Moscow, 1974.
Russian.
M.A. Taitslin.
Existentially closed commutative semigroups.
In 3 th Soviet Mathemat.Logic conf., pages 211 212,
Novosibirsk, 1974. Novosibirsk Inst.Math.
Russian.
M.A. Taitslin.
Existentially closed commutative rings.
In 3 th Soviet Mathemat.Logic conf., pages 213 215,
Novosibirsk, 1974. Novosibirsk Inst.Math.
Russian.
M.A. Taitslin.
Existentially closed structures.
In 5 International Congress of logic, methodology and philosophy
of science, Contributed Papers, pages II 21  II 22. The international
Union of History and Philosophy of Science, Division of Logic, Methodology
and Philosophy of Science, London, Ontario, Canada, 1975.
O.V. Belegradek and M.A. Taitslin.
Categorical varieties of groupoids.
In 13 th Soviet Algebra conf., pages 377 378, Gomel, 1975.
Russian.
V.Ya. Beliaev and M.A. Taitslin.
On elementary properties of existentially closed structures.
In 4 th Soviet Math. Logic conf., page 11, Kishinev, 1976.
Russian.
M.A. Taitslin.
Existentially closed commutative semigroups.
Fundamenta Mathematica, 94:231 243, 1977.
Russian.
M.A. Taitslin.
On algorithmical problem for matrices with integer numbers.
In Matematica i mekhanika, page 134. Kazakh State University,
Alma Ata, 1977.
Russian.
M.A. Taitslin.
A description of algebraic systems in the weak logic of order w
and in program logic.
In Teoria nereguliarnyh krivyh v razlichnyh geometricheskih
prostranstvah, pages 91 98. Kazakh State University, Alma Ata, 1979.
Russian.
M.A. Taitslin.
Program theories of periodical abelian groups.
In Teoria nereguliarnyh krivyh v razlichnyh geometricheskih
prostranstvah, pages 98 107. Kazakh State University, Alma Ata, 1979.
Russian.

M.A. Taitslin.
The isomorphism problem for the commutative semigroups has the
positive solution.
In Model theory and its applications, pages 75 81. Kazakh
State University, Alma Ata, 1980.
Russian.
It is proposed an algorithm to solve the isomorphism problem for commutative
semigroups.
Z.A. Boyarskaya, N.N. Repin, and M.A. Taitslin.
Deterministic dynamic logic is strictly weaker than dynamic logic.
In Problems of the theory of algebraic systems, pages 20 31.
Karaganda State University, Karaganda, 1981.
Russian.
A.D. Taimanov and M.A. Taitslin.
Model theory.
In Mathematical Encyclopedia, volume 3. Soviet Encyclopedia,
Moscow, 1981.
Russian.
M.A. Taitslin.
On a hierarchy of program logics.
In 6 th Soviet Math. Logic conf., page 181, Tbilici, 1982.
Russian.
M.A. Taitslin.
5 problems with program logics.
In Studies on model theory, pages 65 70. Kazakh State
University, Alma Ata, 1982.
Russian.
M.A. Taitslin.
A hierarchy of program logics.
Sibirsky Matematichesky journal, 24(3):184 192, 1983.
Russian.
M.A. Taitslin.
Dynamic theories of commutative semigroups.
In 17 th Soviet Algebra conf., part 2, page 229, Minsk, 1983.
Russian.
A.P. Stolboushkin and M.A. Taitslin.
The comparison of the expressive power of firstorder dynamic logics.
Theoretical Computer Science, 27:197 209, 1983.
Yu.L. Ershov and M.A. Taitslin.
Elementary theories.
In Mathematical Encyclopedia, volume 4. Soviet Encyclopedia,
Moscow, 1985.
Russian.
M.A. Taitslin.
On dynamic logics of many sort signatures.
In Slognostnye problemy matematicheskoy logiki, pages 75 80.
Kalinin State University, Kalinin, 1985.
Russian.
I.Kh. Musikaev and M.A. Taitslin.
Is it always enough a finite set of programs?
In 8 th Soviet Mathemat.Logic conf., page 128. Steklov
Math.Inst., Moscow, 1986.
Russian.
M.A. Taitslin.
On prolog computations.
In Logiko algebraicheskie konstrukcii, pages 80 84. Kalinin
State University, Kalinin, 1987.
Russian.
M.A. Taitslin.
Dynamic logics.
In 8 International Congress of logic, methodology and philosophy
of science, Abstracts, 5, part 1 (sections 1 6), pages 129 130. "Nauka",
Moscow, 1987.
D.A. Arhangelsky and M.A. Taitslin.
A logic for data description.
In 9 th Soviet Mathemat.Logic conf., page 6. Steklov
Math.Inst., Leningrad branch, Leningrad, 1988.
Russian.
D.A. Arhangelsky and M.A. Taitslin.
A logic for data description.
In Logical Foundation of Computer Science  Pereslavl Zalessky
'89, volume 363 of LNCS, pages 2 11. SpringerVerlag, 1989.
D.A. Arhangelsky and M.A. Taitslin.
Modal linear logic.
In Logical Foundation of Computer Science  Tver '92, volume
620 of LNCS, pages 1 9. SpringerVerlag, 1992.
D.A. Archangelsky and M.A. Taitslin.
Modal linear logic.
In Modeli, algoritmy, programy, pages 12 18. Tver State
University, Tver, 1993.
Russian.
I.Kh. Musikaev and M.A. Taitslin.
PSPACE global predicates and language prolog.
In Modeli, algoritmy, programy, pages 97 107. Tver State
University, Tver, 1993.
Russian.
M. Taitslin and D. Arkhangelsky.
The other linear logic.
In Formal Methods in Programming and Their Applications, volume
735 of LNCS, pages 251 255. SpringerVerlag, 1993.
D.A. Archangelsky, M.I. Dekhtyar, and M.A. Taitslin.
Polynomial algorithms for BRnets and for fragments of Girard's
linear logic.
In Proceedings of the Second International Conference
"Mathematical Algorithms" (Nizhny Novgorod, 26 June  1 July 1995), pages
14 22. Nizhny Novgorod State University, 1997.