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 first-order 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 Pseudo-finite 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 first-order 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 pseudo-finite 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 order-generic queries.
Annals of Pure and Applied Logic, 97(1- 3):85- 125, 1999
as to the collapse theorem. It is investigated so called P-reducible theories. It is proved that, for the P-reducible theories, a version of Pseudo-finite Homogeneity Property holds. So the collapse theorem holds for P-reducible 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 order-generic 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 Pseudo-finite 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, order-generic 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 Pseudo-finite 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 pre-fix 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 state-safety problem is undecidable.
We provide very general conditions on the FO theory of an ordered domain that ensure collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of ordered domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all o-minimal 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 finitely-representable states. We show, however, that these results cannot be transferred to arbitrary infinite states.
We prove that safe Datalog-programs 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 pre-fix 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 order-generic 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 first-order (FO) queries that are invariant under order-preserving "permutations" - such queries are called order-generic. It has recently been discovered that for some domains order-generic FO queries fail to express more than pure order queries. For example, every order-generic 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 order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all the o-minimal 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 finitely-representable 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 quasi-o-minimal domains.
In Logical Foundation of Computer Science, 4th International Symposium, LFCS'97, Yaroslavl, Russia, July 1997, Proceedings, volume 1234 of LNCS, pages 21- 32. Springer-Verlag, 1997.
O.V. Belegradek, A.P. Stolboushkin, and M.A. Taitslin.
On order-generic 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 Datalog-program is said to be safe iff its bottom-up processing terminates on all valid inputs. We prove that safe Datalog-programs do not have effective syntax in the sense that there is no recursively enumerable set S of safe Datalog-programs such that every safe Datalog-program 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 state-finiteness, which is, given a query and a database state, to decide upon finiteness of the query in this state.
This settles two long-standing 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 polynomial-time 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 Ln 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 Ln+1 in more expressive over A than Ln.
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 first-order tests as well as quantifier-free 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 (BR-nets). Linear Logic to describe the behaviour of BR-nets 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. Springer-Verlag, 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. Springer-Verlag, 1995.
By "initial segments of P" we mean classes DTime(nk). The question of whether for any fixed signature the first-order 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 Immerman-Vardi-style 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.
- Chapter 1. Finite Automata and Regular Languages.
- Chapter 2. Push-Down Automata and Context-Free Languages.
- Chapter 3. Predicate Calculus.
- Chapter 4. Programs, Recursive Functions, and Turing Machines.
- Chapter 5. Undecidable Problems and Incompleteness of arithmetic: Thue semi-systems; Post Correspondence Problem; Associative calculi; Church Thesis; Formulating formal arithmetic; Functions representable in formal arithmetic; Incompleteness of formal arithmetic.
- Chapter 6. Computational Complexity of algorithms: The notion of computational complexity. Time and space complexity. Determinism and nondeterminism; Emulating the nondeterministic machines with deterministic. Hierarchy theorem. Main complexity classes; Reducibility of languages. Universal problems; Describing classes of time complexity in terms of stack machines; The complexity of certain problems in the theory of languages.
- Chapter 7. PTIME Computable Global Predicates: Databases, relational databases as finite structures of relational signatures. Query languages and formulae of logical languages; Algorithmic definability of global predicates; Polynomial complexity of recursive algorithms; Completeness of recursive algorithms for the class of PTIME computable global predicates.
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 first-order 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 first-order theories.
M.A. Taitslin.
On free W-groups.
Uspehi Matematicheskih Nauk, 16(2):221, 1961.
Russian.
D.M. Smirnov and M.A. Taitslin.
On finitely approximable abelian W-groups.
Uspehi Matematicheskih Nauk, 16(2):221- 222, 1961.
Russian.
M.A. Taitslin.
On finite approximability of W-groups.
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 first-order 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. Springer-Verlag, 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. Springer-Verlag, 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. Springer-Verlag, 1993.
D.A. Archangelsky, M.I. Dekhtyar, and M.A. Taitslin.
Polynomial algorithms for BR-nets 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.