Go back!

Sergey Mardaev

Official Homepage

Last modified: October 4, 2007

D.Sc., Leading Researcher, Institute of Mathematics of Siberian Branch of Russian Academy of Sciences, Novosibirsk

Selected papers

* Graded Modal Operators and Fixed Points, Vestnik NGU (Bulletin of the Novosibirsk State University), Mathematics, 6 (2006), N 1, 70-76 (in Russian)

1) Natural Numbers and Fixed Points
It is important to investigate logics based on natural numbers and least fixed points because these logics capture languages of classes automatons and Turing machines.

Consider the set of natural numbers (N,<) with the natural strict linear order. Language: propositional variables, logical connectives "and", "or", "not", counting quantifiers < n > (there are n greater elements) for every n. The valuation function assigns a value (a subset of N) to every variable. The connectives correspond to intersection, union, and complementation. A formula < n >A is true at k if there exist k1,..., kn>k such that A is true at k1,..., kn. Let all occurrences of the variable p in the formula A(p,q1,..., qm) be positive.

THEOREM. There exist a formula W(q1,..., qm), which defines the least fixed point of A (relative to p) in every such model, and an algorithm of constructing this formula.

2) Graded Modal Logic and Fixed Points
The well-known Fixed Point Theorem is generalized from the modal case to the graded case.
THEOREM. For any graded formula A(p,q1,..., qm) that is modalized in p, there exists a unique fixed point of A in every strictly partially ordered Kripke model with the ascending chain condition. There is a graded formula W, which defines the fixed point in every such model. The formula W contains only those graded modalities, which are contained in the formula A.


* Definable Fixed Points in Modal and Temporal Logics - A Survey, Journal of Applied Non-Classical Logics, v.17, N.3/2007, p.317-346.
In this paper we give a classification of fixed point theorems.

It is well-known that many predicates can be defined as the least fixed points of positive formulas. Such a definition is implicit, but if the least fixed point is formula-definable, an explicit definition also exists. There are two reasons for investigating of fixed points.

a) If fixed points are not formula-definable then, by adding the fixed point operator to the syntax, we can increase the expressive power of the language. There exist many investigations in this direction.

b) If fixed points are definable, then, formally, the expressive power does not increase. But usually an implicit definition is much shorter than an explicit one. So, it is more convenient to use.

We investigate the second case. We identify some classes of modal and temporal models, in which the least fixed points of positive formulas are definable. We also consider special positive formulas. To obtain an explicit definition, we need an algorithm for its construction. For each definability theorem stated in this paper, an algorithm for constructing the corresponding formula is given. Some other interesting phenomena are discovered - definability by formulas that do not preserve positivity of parameters and definability by finite sets of formulas. We also consider negative operators, graded modalities, construct not definable fixed points, and pose problems.

* Least Fixed Points in Modal Logic, Proceedings of International Conferences on Mathematical logic, edited by S.S.Goncharov a.o., Novosibirsk State University, Novosibirsk, 2002, 92-103
Some proofs (in English).

* Fixed Points of Modal Operators, Habilitation Thesis (Dissertation for the D.Sc.), Institute of Mathematics of Siberian Branch of Russian Academy of Sciences, Novosibirsk, 2001, 237 p. (in Russian, self-extracting archived ps-file m.exe)

Detailed proofs, a lot of examples.

* Two sequences of locally tabular superintuitionistic logics, Studia Logica, 50 (1991), N2, 333-342 (Springerlink)
Some results about chains of Heyting algebras

* Embeddings of Implicative Lattices and Superintuitionistic Logics, Algebra and Logic, 26, N3 (1987), 178-205 (Springerlink)
1) Every finitely generated implicative lattice is embeddable to a two-generated implicative lattice.
2) For every tabular superintuitionistic propositional logic L, which contains the logic KC of the weak law of excluded middle, there is a continuum set of prelocally tabular logics La and a continuum set of finitely preapproximable logics Ma such that KC < Ma < La < L for every index "a".

* Number of prelocally table superintuitionistic propositional logics, Algebra and Logic, 23, N1 (1984), 74–87 (Springerlink)
Simple construction of a continuum of prelocally table superintuitionistic propositional logics.

* Some my Springer papers (in "Algebra and Logic" and "Studia Logica")

List of publications (in Russian)

Selected projects

* INTAS "Algebraic and deduction methods in non-classical logic and their applications to computer science"

Selected Talks

* Maltsev Meeting 2006, November, Novosibirsk, Russia. Contributed talk "Counting Quantifiers and Fixed Points"

* The 9th Asian Logic Conference, August, 2005, Novosibirsk, Russia. Contributed talk "Graded modalities and fixed points"

* Maltsev Meeting 2005, November, Novosibirsk, Russia. Invited talk "Fixed Points in Modal Logic"

Curriculum Vitae

Born - 6th April 1962, Ulan-Ude, Soviet Union - Family Fotos

Research Interests - Mathematical Logic, Non-Classical Logics, Modal and Temporal Logics, Fixed-Point Logics, Teaching

Position - Single , Institute of Mathematics of Siberian Branch of Russian Academy of Sciences, Department of Mathematical Logic
Leading Researcher 2002-Present, Senior Researcher 1993-2002, Researcher 1988-1993, Junior Researcher 1987-1988

Habilitation (D.Sc.) - 2002, Institute of Mathematics of Siberian Branch of Russian Academy of Sciences. Thesis - Fixed Points of Modal Operators. Thesis consultant - Larisa Maksimova

Institute of Mathematics of Siberian Branch of Russian Academy of Sciences (1984-1987) - Kandidat (PhD), 1988. Thesis: Superintuitionistic Logics with Finiteness Conditions. Thesis Adviser - Larisa Maksimova
Novosibirsk State University, Mathematical Faculty (1979-1984) - MS. Master's Thesis: The number of prelocally tabular superintuitionistic propositional logic. Thesis Adviser - Larisa Maksimova
Novosibirsk academician M.A.Lavrentiev Physical and Mathematical School (1978-1979) Mathematics Teacher - Vladimir Rybakov

Teaching Experience

Buryat State University, Department of Algebra
Professor 2007-Present. Lecture course on Applied Logic

Novosibirsk State University, Department of Algebra and Logic
Docent (associate professor) 1997-Present, Senior Lecturer 1995-1997, Assistant 1995-1995. Lecture course on Applied Logic for Master students 2003, Lecture course on Modal Logic 2002, Seminars in Mathematical Logic and Recursion Theory, weekly seminar "Non-Standard Logics"

Specialized Scientific Study Center for Physics, Mathematics, Chemistry and Biology Education of Novosibirsk State University (Novosibirsk academician M.A.Lavrentiev Physical and Mathematical School), Department of Mathematics
Docent (associate professor) 1997-Present, Senior Lecturer 1993-1997, Assistant 1990-1993. Lecture Course "Abstract Machines" 1997, Lecture Course "Theory of Algorithms" 1988-? (I do not remember, sorry ), Seminars in Mathematics

* Pascal Michel (Busy Beavers), Mirek Wojtowicz (Cellular Automata), EqWorld, MCCME, Math.Etudes, MathPuzzle, Boris Tarakanov Music Archive, Werner Icking Music Archive


* Valery Churkin. Finite-dimensional Linear Operators (draft, in Russian)

* Valery Churkin. Polynomial systems and ideals (draft, in Russian)

Unofficial Homepage (under construction)


Address: Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Acad. Koptyug prospect 4, Novosibirsk 630090, Russia

Phone: (383) 3333197

Fax: (383) 3332598

email: mardaev@math.nsc.ru