|
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 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.
|
|
|
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)
Results:
|
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")
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
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
Education 
|
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
|
Professor 2007-Present.
Lecture course on Applied 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"
|
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
Recommended 
* Valery Churkin. Finite-dimensional 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
|
- Family Fotos
