A survey of previous research of V.L. Selivanov

A SURVEY OF PREVIOUS RESEARCH OF V.L. SELIVANOV

My research started in 1974 and is devoted to Mathematical Logic, Computer Science and Didactics of Mathematics and Informatics. The main focus of research was computability, ranging from the general computability theory to automata theory. The research might be subdivided into the following areas (many of which are indeed closely interrelated):

1. computable numberings and degrees of unsolvability;
2. precomplete and complete numberings;
3. hierarchies in computability theory and logic;
4. positive structures, in particular positive boolean algebras;
5. index sets of some important numberings;
6. hierarchies in complexity theory;
7. hierarchies of omega-languages related to computer science;
8. hierarchies of regular star-free languages;
9. didactics of mathematics and informatics;
10. information technologies in education.

Next I shall shortly characterize results in each of these areas.

1) In this field, I a) proved that any nontrivial semilattice of computable numberings is not a lattice; b) constructed an example of a discrete but not effectively discrete family of total recursive functions having the unique (up to equivalence) computable numbering; c) constructed an example of a non-discrete family of recursively enumerable sets having the unique (up to equivalence) computable numbering. Any of these results was an answer to a well-known problem on computable numberings. These theorems were central results of my candidate dissertation (PhD thesis) and are published in papers 1-5 (see Section 1 of the list of my publications). I has proved also several facts on degrees of unsolvability, e.g. classified the possible versions of tt-reducibilities (this fact was indepentantly obtained by V.K. Bulitko) and completely described relationships between Ershov hierarchy and the high-low hierarchy of degrees of unsolvability (independently this was done by C. Jockusch and R. Shore). This is reflected in papers 9, 16, 19, 27. The result b) above was used by several people working on learning theory, including R. Freiwald, E. Kinber and R. Wiehagen.

2) It is well-known that Ershov difference hierarchy is closely related to the so called m-jump operator. I defined and investigated several generalizations of this operator. It turned out that these generalized operators are closely related to the theory of complete numberings developed by A.I. Mal'cev and Y.L. Ershov, and to the study of structures of m-degrees of index sets of the numberings of recursively enumerable sets and of partial recursive functions. These results led to simplification and generalization of results of L. Hay about index sets and were developed further by several mathematicians including J. Mohrherr. They are published in papers 8, 11, 13, 15.

I developed also a relativized version of the theory of precomplete and complete numberings which led to priority-free proofs of several known results about the structure of tt-type degrees and about the m-degrees of index sets in such structures. This approach led also to several new results in this field which are also proved very easily (using a version of the Kleene fixed-point theorem in place of the complicated priority constructions). This research is reflected in papers 18, 21, 28, 32 and in the conference proceedings 1. The paper 36 contains a comprehensive survey of the theory of precomplete numberings and its applications.

3) In the hierarchy theory, using the operations mentioned in 2), I defined a refinement of the arithmetic hierarchy called the fine hierarchy and proved that it containes many known hierarchies and has some rather strong closure properties with respect to refinements. These results informally mean that the fine hierarchy is in some sence the finest possible. Later, using set-theoretic operations introduced by W. Wadge, I gave a set-theoretical description of the fine hiearachy. This led to the possibility of defining this hierarchy in very different contexts, e.g. in the context of logic and descriptive set theory. In the last case, I afterwards proved that the fine hierarchy is, in some exact sence, the finite version of the Wadge hierarchy of Borel sets-the well-known and important object of descriptive set theory. The corresponding publications are papers 13, 15, 22, 25, 26, 30, 31. In the preprint 13 I have rather comprehensively described the difference hierarchy in f-spaces (and also in some domains).

The results from 2), 3) were central results of my Doctoral dissertation (an analog of habilitation thesis).

4) In the beginning of 1990ies, I obtained general results on positive numbered boolean algebras (part of them in a joint paper with S.P. Odintsov). Main results state that this class of boolean algebras always has a good computable numbering (an analog of the numbering of the r.e. sets) and there exists a unique (up to effective isomorphism) universal positive boolean algebra (an analog of the creative set). I characterised also many natural and important index sets in the numbering of positive boolean algebras (using some earlier results by S. Lempp on index sets of classes of hyperhypersimple sets). Later some of these results were extended by me to a very general context of recursively axiomatizable quasivarieties. This body of research has different applications, e.g. to classification of many natural index sets in the lattice of r.e. sets, in the semilattice of r.e. m-degrees, in the Lindenbaum algebra of sentences (the papers 23, 24, 26, 31, 32). Some of those results were later used by several other mathematicians, including S. Lempp, M. Peretiat'kin, and R. Solomon.

5) Some of results in this direction were already mentioned earlier (all the topics 1) — 5) are closely related one to another). Among others one could mention the complete investigation of possibility of proving analogs of the famous Rice-Shapiro theorem for other levels of the arithmetic hierarchy (as well as of some of its refinements). Another principal result is a complete description of m-degrees of index sets of the predicates first-order definable in the Lindenbaum algebra of sentences of nontrivial signatures. Note that this classification needs all levels of the fine hierarchy, i.e. it could not be achieved without inventing the fine hierarchy. The corresponding papers are 6-8, 10-12, 14, 22, 24, 26.

6) In the context of Structural Complexity Theory, I defined and considered some analogs of my hierarchies mentioned above. I was able to extend the well-known result of J. Kadin about the non-collapse of the Boolean hierarchy over NP to a much more rich hierarchy called the plus-hierarchy. This line of research is reflected in the conference proceedings 3, preprint 2 and papers 30, 34. The plus-hierarchy was later considered and applied by some other researchers including L. Hemaspaandra and K. Wagner.

7) I applied also the fine hierarchy to classification of regular omega-languages — a classical object of theoretical informatics. It turned out that the resulting classification coincides with the Wagner hierarchy of regular omega-languages. This result established a close relationship between descriptive set theory and the theory of regular omega-languages. It leads to quite different proofs of deep and complicated results of K. Wagner, as well as to several new results on regular omega-languages. This research is reflected in preprint 5, the conference paper 4 and the paper 33. Later I have got similar results also for the class of regular star-free omega-languages. These papers were, to the best of my knowledge, the first applications of modern descriptive set theory to the theory of omega-languages. This line of research was developed also by several French mathematicians including D. Perrin, J. Duparc and O. Finkel. Recently, I have classified Wadge degrees of omega-languages of deterministic Turing machines (Preprint 12). This answeres a question raised by J. Duparc.

8) In this field, I proposed a new, logical approach to the well-known in automata theory problem of decidability of the dot-depth hierarchy and of some its refinements. In this way, I obtained quite different and shorter proofs of several known results, and also obtained some new results on the analogs of the dot-depth problem. Some of these results were obtained independently and by other methods by C. Glasser, H. Schmitz and K. Wagner. Using some previous results on the so called leaf languages, I established also a deep interconnections of these automata-theoretic hierarchies to the complexity-theoretic ones discussed in 6). These results are published in the papers 35, 37, preprints 6, 7, 8 and the conference papers 5, 6.

9,10) In these fields, my main interest was to develop some new, more effecient methodics of teaching some areas of mathematics and informatics to students of different specialties and of different qualifications. For example, together with some of my former and current PhD students we developed some methodics for teaching basic skills of Microsoft Office for beginners, basics of algorithmics for schoolchildren, basics of visual programming and elements of computer modeling in secondary and high school. This line of research is reflected in Sections 6 and 7 of the list of publications.

The above-mentioned results in directions 1) — 8) were used and developed by several Soviet and Western mathematicians. Some of them are reflected in monographs and textbooks on computability theory, e.g. in books by M.M. Arslanov, A.N. D"egtev, Y.L. Ershov (in Russian), Y.L. Ershov and S.S. Goncharov, S.S. Goncharov, V.A. Uspenski and A.L. Sem"enov (in Russian, translated into English), R. I. Soare, P. G. Odifreddi, and also in Handbooks of Computability, of Recursive Mathematics and of Formal Languages. Some results from 7) are planned (as far as I know) to be included in the forthcoming book «Infinite Words» by D. Perrin and J.-E. Pin.

V.L. Selivanov

Novosibirsk, Russia

November 2002