
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
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 k_{1},..., k_{n}>k
such that A is true at k_{1},..., k_{n}. Let all occurrences of the variable p in the formula
A(p,q_{1},..., q_{m}) be positive.

THEOREM.
There exist a formula W(q_{1},..., q_{m}), 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 wellknown Fixed Point Theorem is generalized from the modal case to the graded case.
THEOREM.
For any graded formula A(p,q_{1},..., q_{m}) 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.


In this paper we give a classification of fixed point theorems.
It is wellknown 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 formuladefinable, an explicit
definition also exists. There are two reasons for investigating of
fixed points.
a) If fixed points are not formuladefinable 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, 92103
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, selfextracting archived psfile
m.exe)
Detailed proofs, a lot of examples.



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

* Embeddings of Implicative Lattices and Superintuitionistic Logics, Algebra and Logic, 26, N3 (1987), 178205
(Springerlink)
Results:
1) Every finitely generated implicative lattice is embeddable to a twogenerated 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 L_{a} and a continuum set
of finitely preapproximable logics M_{a} such that KC < M_{a} < L_{a} < 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")
Selected projects
* INTAS "Algebraic and deduction methods in nonclassical 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
Research Interests  Mathematical Logic, NonClassical Logics, Modal and Temporal Logics, FixedPoint Logics, Teaching
Position  Single ,
Institute of Mathematics of Siberian Branch of Russian Academy of Sciences, Department of Mathematical Logic
Leading Researcher 2002Present,
Senior Researcher 19932002,
Researcher 19881993,
Junior Researcher 19871988

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
Education
Institute of Mathematics of Siberian Branch of Russian Academy of Sciences (19841987)
 Kandidat (PhD), 1988.
Thesis: Superintuitionistic Logics with Finiteness Conditions.
Thesis Adviser  Larisa Maksimova

Novosibirsk State University, Mathematical Faculty (19791984)  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
(19781979) Mathematics Teacher  Vladimir Rybakov

Teaching Experience
Professor 2007Present.
Lecture course on Applied Logic

Docent (associate professor) 1997Present, Senior Lecturer 19951997, Assistant 19951995.
Lecture course on Applied Logic for Master students 2003, Lecture course on Modal Logic 2002,
Seminars in Mathematical Logic and Recursion Theory, weekly seminar "NonStandard Logics"

Docent (associate professor) 1997Present, Senior Lecturer 19931997, Assistant 19901993.
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
Recommended
* Valery Churkin. Finitedimensional Linear Operators (draft, in Russian)
* Valery Churkin. Polynomial systems and ideals (draft, in Russian)
Contacts
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
