Publication of V.L. Selivanov

Papers refereed by journal standards

1. On computability of some classes of numberings. Prob. Methods and Cybernetics, v.12-13, Kazan University, Kazan,1976, 157--170 (Russian).

2. On numberings of families of total recursive functions. Algebra and Logic, 15, N 2 (1976), 205--226 (Russian, there is an English translation).

3. Two theorems on computable numberings. Algebra and Logic, 15, N 4 (1976), --484 (Russian, there is an English translation).

4. Numberings of canonically computable families of finite sets. Sib. Math. J., 18, N 6 (1977), 1373--1381 (Russian, there is an English translation).

5. On index sets of classes of numberings. Prob. Methods and Cybernetics, v.14, Kazan University, Kazan,1978, 90--103 (Russian).

6. On index sets of computable classes of finite sets. In: Algorithms and Automata, Kazan University, Kazan,1978, 95--99 (Russian).

7. Some remarks on classes of recursively enumerable sets. Sib. Math. J., 19, N 1 (1978), 109--115.

8. On the structure of degrees of index sets. Algebra and Logic, 18, N 4 (1979), 286--299.

9. On a class of reducibilities in recursion theory. Prob. Methods and Cybernetics, v.14, Kazan University, Kazan, v. 18 (1982), 83--101 (Russian).

10. On index sets in the Kleene-Mostowski hierarchy. Trans. Inst. Math., Novosibirsk, N 2 (1982), 135--158 (Russian).

11. On the structure of degrees of generalized index sets. Algebra and Logic, , N 4 (1982), 316--330.

12. Effective analogs of A-, B-, and C-sets with applications to index sets. Prob. Methods and Cybernetics, v.14, Kazan University, Kazan, v. 19 (1983), --128 (Russian).

13. Hierarchies of hyperarithmetical sets and functions. Algebra and Logic, , N 6 (1983), 473---491.

14. Index sets in the hyperarithmetical hierarchy. Sib. Math. J., N 3 (1984), --488.

15. On a hierarchy of limiting computations. Sib. Math. J., 25, No 5 (1984), --806.

16. On Ershov hierarchy. Sib. Math. J., 26, N 1 (1985), --116.

17. Automorphism groups of numbered sets. Math. Notes, 41, © 4 (1987), 592--597 (Russian, there is an English translation).

18. Ershov hierarchy and Turing jump. Algebra and Logic, 27 N 4 (1988), --300.

19. Index sets of factor-objects of the Post numbering. Algebra and Logic, , N 3 (1988), 215--224.

20. On algorithmic complexity of algebraic systems. Math. Notes, , No 5-6 (1988) p.944950.

21. Applications of precomplete numberings to tt-type degrees and to index sets. Algebra and Logic, 12, N 1 (1989), 51--56.

22. Arithmetical hierarchy and ideals of numbered boolean algebras (jointly with S.P. Odintsov). Sib. Math. J., 30, N 6 (1989), 140--149 (Russian, there is an English translation).

23. Fine hierarchies of arithmetical sets and definable index sets. Trans. Inst. Math., Novosibirsk, 12 (1989), 165--185 (Russian).

24. Index sets of classes of hyperhypersimple sets. Algebra and Logic, 29, N 2 (1990), 220--240 (Russian, there is an English translation).

25. A fine hierarchy of formulas. Algebra and Logic, 30, N 5 (1991), 568--582 (Russian, there is an English translation).

26. Fine hierarchies and definable index sets. Algebra and Logic, 30, N 6 (1991), 463--475.

27. Jumps of some classes of sets. Math. Notes, , No 6 (1991), p.1299--1300.

28. Precomplete numberings and functions without fixed points. Math. Notes, Math. Notes, 51, No 1 (1992), p.95--99.

29. (.PDF) Recursiveness of omega-operations. Math. Logic Quaterly, 40, N 2 (1994), --206.

30. (.PDF) Fine hierarchies and Boolean terms. The Journal of Symbolic Logic, 60, N 1 (1995), 289--317.

31. (.PDF) Fine hierarchy and definability in the Lindenbaum algebra. In: Logic: from foundations to applications, Proceedings of the Logic Colloquium-93 in Keele. Oxford, 1996, 425--452.

32. (.PDF) On recursively enumerable structures. Annals of pure and applied logic, (1996), 243--258.

33. (.PDF) Fine hierarchy of regular omega-languages. Theor. Computer Science, 191 (1998), 37--59.

34. (.PDF) Refining the polynomial hierarchy. Algebra and Logic, 38 (1999), --475 (Russian, there is an English translation).

35. (.PDF) On decidability of classes of hierarchies of regular aperiodic languages. // Algebra and Logic//,41, N 5 (2002), 610--631 (Russian, there is an English translation).

36. (.PDF) Precomplete numberings. Proc. of Int. Conferences on Math. Logic honoring Yu.L. Ershov and A.I. Mal'tsev, Novosibirsk, 2002, 104--143.

37. (.PDF) Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. // Theoret. Informatics Appl.//, 36 (2002), 29--42.

38. (.PDF) Positive structures. In: Computability and Models, Perspectives East and West, S. Barry Cooper and Sergei S. Goncharov, eds., Kluwer Academic/Plenum Publishers, New York, 2003, --350.

39. (.PDF) Wadge degrees of omega-languages of deterministic Turing machines. // Theoretical Informatics and Applications//, 37 (2003), 67--83.

40. (.PDF) Boolean hierarchies of partitions over reducible base. // Algebra and Logic//, 43, N 1 (2004), 77--109 (Russian, there is an English translation).

41. (.PDF) Difference hierarchy in varphi-spaces. // Algebra and Logic//, 43, N 4 (2004), 425--444 (Russian, there is an English translation).

42. (.PDF) A reducibility for the dot-depth hierarchy (jointly with K.W. Wagner). // Theoretical Computer Science//, 345, N 2-3 (2005), 448--472.

43. (.PDF) Classifying countable boolean terms. // Algebra and Logic//, 44, N 2 (2005), 173--197 (Russian, there is an English translation).

44. (.PDF) Hierarchies in varphi-spaces and applications. // Math. Logic Quarterly//, 51, N 1 (2005), 45--61.

45. (.PDF) Variations on the Wadge reducibility. // Siberian Advances in Math.//, , N 3 (2005), 44--80.

46. (.PDF) Towards a descriptive set theory for domain-like structures. // Theoretical Computer Science//, 365 (2006), 258--282.

47. (.PDF) Hierarchies of Delta^0_2-measurable k-partitions. // Math. Logic Quarterly, 53//, (2007),446--461.

48. (.PDF) The quotient algebra of labeled forests modulo h-equivalence. // Algebra and Logic, 46, N 2//, (2007), 120--133.

49. (.PDF) Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests (jointly with O.V. Kudinov). // Journal of Logic and Computation, 17//, (2007), 1135--1151.

Papers in proceedings of leading international conferences

1. Index sets of factor-objects of the Post numbering. In: Proc. of the Int. Conference in Foundations of Computation Theory in Kazan. Lecture Notes in Computer Science, v. 278. Berlin: Springer, 1987, 396--400.

2. Computing degrees of definable classes of sentences. In: Proc. of Int. Conference in Algebra in Honor of A. I. Malcev in Novosibirsk. Contemporary Mathematics, v. , part 3 (1992), 657--666.

3. (.PDF) Two refinements of the polynomial hierarchy. In: Proc. of 11-th Int. Symposium on Theor. Aspects of Computer Science STACS-94 in Caen, France, Lecture Notes in Computer Science, v. 775. Berlin: Springer, 1994, 439--448.

4. Fine hierarchy of regular omega-languages. In: Proceedings of the Int. Joint Conf. on the Theory and Practice of Software Development TAPSOFT-95 in Aarhus, Denmark, Lecture Notes in Computer Science, v. 915. Berlin: Springer, , 277--287.

5. (.PDF) A logical approach to decidability of hierarchies of regular star-free languages. In: Proc. of 18-th Int. Symposium on Theor. Aspects of Computer Science STACS-2001 in Dresden, Germany, Lecture Notes in Computer Science, v. 2010. Berlin: Springer, 2001, 539--550.

6. (.PDF) Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. Conference on Foundations of Computation Theory in Riga, Latvia, Lecture Notes in Computer Science, v. 2138. Berlin: Springer, 2001, 323--334.

7. (.PDF) Wadge degrees of omega-languages of deterministic Turing machines. Conf. STACS-03, Lecture Notes in Computer Science, v. 2607. Berlin: Springer, 2003, 97--108.

8. (.PDF) A reducibility for the dot-depth hierarchy (jointly with K.W. Wagner). Conf. MFCS-04, Lecture Notes in Computer Science, v. 3153. Berlin: Springer, 2004, 783--793.

9. Variations on Wadge reducibility. Sixth Int. Workshop on Computability and Complexity in Analysis, Informatik Berichte, Uni-Hagen, 320-8/2004, --156.

10. (.PDF) Some reducibilities on regular sets. Conf. «Computability in Europe-2005» (Eds. S.B. Cooper, B. Loewe and Leen Torenvliet), Lecture Notes in Computer Science, v. 3526. Berlin: Springer, 2005, 430--440.

11. The algebra of labeled forests modulo homomorphic equivalence. Conference Computability in Europe-06, University of Swansea report series, 2006, 241--250.

12. (.PDF) Undecidability in the homomorphic quasiorder of finite labeled forests (joint with O.V. Kudinov). Conf.Computability in Europe-2006 (Eds. A. Beckman et.al.), Lecture Notes in Computer Science, v. 3988. Berlin: Springer, 2006, 289--296.

13. (.PDF) A useful undecidable theory. Conference Computability in Europe-07,(Eds. S.B. Cooper, B. Loewe and A. Sorbi), Lecture Notes in Computer Science, v. 4497. Berlin: Springer, 2007, 685-694.

14. (.PDF) Definability in the homomorphic quasiorder of finite labeled forests (joint with O.V. Kudinov). Conf.Computability in Europe-2007 (Eds. S.B. Cooper, B. Loewe and A. Sorbi), Lecture Notes in Computer Science, v. 4497. Berlin: Springer, 2007, 436-445.

15. (.PDF) Fine hierarchy of regular aperiodic omega-languages. Conf. DLT-2007 (Eds. T. Harju, J. Karhumaeki and A. Lepisto), Lecture Notes in Computer Science}, v. 4588. Berlin: Springer, 2007, 399-410.

Abstracts in proceedings of other conferences

1. On degrees of some index sets. Abstracts of USSR Student Conf., Mathematics, Novosibirsk, 1975, 20--21 (Russian).

2. On index sets. Abstracts of 4th USSR Conf. on Math. Logic, Kishinev, 1976, 134 (Russian).

3. Some remarks on computable numberings. Abstracts of 4th USSR Conf. on Math. Logic, Kishinev, 1976, 133 (Russian).

4. On multiple $m$-reducibility of index sets. Abstracts of 5th USSR Conf. on Math. Logic, Novosibirsk, 1979, 137 (Russian).

5. Index sets in hyperarithmetical hierarchy. Abstracts of 6th USSR Conf. on Math. Logic, Tbilisi, 1982, 164 (Russian).

6. On Ershov hierarchy. Abstracts of 6th USSR Conf. on Math. Logic, Tbilisi, 1982, 165 (Russian).

7. On truth-table reducibilities of index sets. Abstracts of 7th USSR Conf. on Math. Logic, Novosibirsk, 1984, 162 (Russian).

8. On algorithmic complexity of algebraic systems. Abstracts of USSR Conf. on Applied Logic, Novosibirsk, 1985, 193--195 (Russian).

9. On $m$-degrees of index sets. Abstracts of 8th USSR Conf. on Math. Logic, Moscow, 1986, 172 (Russian).

10. Hierarchies and index sets. Abstracts of 8th Congress of Logic, Methodology and Philosophy of Science. Moscow, 1987, v. 1, 167--169.

11. Degrees of unsolvability of index sets of levels of Ershov hierarchy. Abstracts of 2nd USSR Conf. on Applied Logic, Novosibirsk, 1988, 148 (Russian).

12. Fine hierarchies and definable index sets. Abstracts of 9th USSR Conf. on Math. Logic, Leningrad, 1988, 148 (Russian).

13. Arithmetical hierarchy and ideals of numbered Boolean algebras (jointly with S. P. Odintsov). Abstracts in Theory of models and algebraic systems, Int. Conf. on Algebra, Novosibirsk, 1989, 143.

14. Fine hierarchies and definable index sets. Abstracts of 3-d logic biennial, Sofia,1990, 64.

15. On definable index sets. Abstracts of 9th Congress of Logic, Methodology and Philosophy of Science. Uppsala, 1991, v. 1, 64.

16. Universal Boolean algebras with applications. Abstracts of Int. Conf. in Algebra, Novosibirsk, 1991, 127 (Russian).

17. Ershov hierarchy in the Baire space. Abstracts of 2nd Congress on Industrial and Applied Math., Novosibirsk, 1998, v. 3, 127.

18. On two conjectures of W. Wadge. Abstracts of Int. Conf. in Honor of Yu. L. Ershov, Novosibirsk, 2000, 139.

Preprints and accepted papers

1. Truth-table reducibilities of index sets. Dep. in VINITI by Sib. Math. J., 1986, No 4682-B, 18pp.

2. Fine hierarchies and Boolean terms. Preprint N 5, 1993, the University of Heidelberg, Chair of Mathematical Logic, 28 p. (appeared in JSL).

3. Fine hierarchy and definability in the Lindenbaum algebra. Preprint ML9412, University of Amsterdam, ILLC, 1994, 30 pp.

4. Fine hierarchy of regular omega-languages. Preprint N 14, 1994, the University of Heidelberg, Chair of Mathematical Logic, 13 p. (appeared in TCS).

5. On recursively enumerable structures. Preprint N 10, 1994, the University of Heidelberg, Chair of Mathematical Logic, 20 p. (appeared in APAL).

6. Precomplete numerations with applications, Preprint No 13, 1994, the University of Heidelberg, Chair of Mathematical Logic, 59 pp.

7. Refining the polynomial hierarchy, Preprint No 9, the University of Heidelberg, Chair of Mathematical Logic, 1994, 20 p. (appeared in Algebra and Logic).

8. A logical approach to decidability of hierarchies of regular star-free languages. Preprint 68 of A.P. Ershov Institute of Informatics Systems, 2000, p.

9. On hierarchies of regular star-free languages (Russian, jointly with A. G. Schukin). Preprint 69 of A.P. Ershov Institute of Informatics Systems, 2000, 28 p.

10. Boolean hierarchy of partitions over reducible bases. Technical report No 276, Institute of Informatics, University of W"rzburg, 2001, 15 pp. (published in Algebra and Logic).

11. Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. Technical report No 275, Institute of Informatics, University of W"urzburg, 2001, 14 pp. (published in Theoretical Informatics and Applications).

12. Difference hierarchy in f-spaces. Preprint 02-02, Informatik-Berichte, University of Siegen, 2002, 11 pp. (published in Algebra and Logic).

13. Wadge degrees of $omega$-languages of deterministic Turing machines, Preprint 02-01, Informatik-Berichte, University of Siegen, 2002, 17 pp. (published in Theoretical Informatics and Applications).

14. A reducibility for the dot-depth hierarchy (jointly with K. Wagner). University of W"urzburg, Technical Report 313, 2003, 21 pp. (published in TCS)

15. Classifying countable boolean terms. Preprint 01-03, Informatik-Berichte, University of Siegen, 2003, 14 pp. (published in Algebra and Logic).

16. Some hierarchies and reducibilities on regular languages. University of W"urzburg, Technical Report 349, 2004, 21 pp. (submitted to Theoretical Informatics and Applications)

17. Variations on Wadge reducibility. Preprint -04, Informatik-Berichte, University of Siegen, 2004, 34 pp. (published by Siberian Advances in Math.).

18. Classifying omega-Regular Partitions. University of W"urzburg, Institute of Informatics, Technical Report 396, 2006, 11 pp.

19. Fine hierarchy of regular aperiodic omega-languages. Technical report No 390, Institute of Informatics, University of W"urzburg, 2006, 21 pp.

20. The algebra of labeled forests modulo homomorphic equivalence. University of Siegen, Schriften zur Theoretischen Informatik, Bericht N -01, 18 pp. (published by Conference Computability in Europe-06).

21. Towards a descriptive set theory for domain-like structures. University of Siegen, Schriften zur Theoretischen Informatik, Bericht N 05-02, 29 pp. (appeared in Theoretical Computer Science).

22. Undecidability in the homomorphic quasiorder of finite labeled forests (joint with O.V. Kudinov). University of Siegen, Schriften zur Theoretischen Informatik, Bericht N 06-02, 8 pp. (published by Conference Computability in Europe-06).

Manuscripts

1. On computable numberings. Abstract of PhD thesis, University of Novosibirsk, 1979, 16 pp. (Russian).

2. On computable numberings. PhD thesis, University of Novosibirsk, 1979, pp. (Russian).

3. Hierarchical classification of arithmetical sets and index sets. Abstract of the Habilitation thesis, Institute of Mathematics SD RAS, Novosibirsk, 1989, 24 pp. (Russian).

4. Hierarchical classification of arithmetical sets and index sets. Habilitation thesis, Institute of Mathematics, Siberian Division RAS, Novosibirsk, 1989, 170 pp. (Russian).

5. Hierarchies, Numerations, Index Sets. Handwritten notes, 1992, pp.

Books and tutorials

1. Tensors (jointly with E. V. Skvortsov). Methodical Notes, Kazan State Institute of Chemical Technology, 1983, 16 pp. (Russian).

2. A tutorial on mathematical logic. Methodical Notes, Novosibirsk State Pedagogical Institute, 1988, 35 pp. (Russian).

3. A tutorial on number systems. Methodical Notes, Novosibirsk State Pedagogical Institute, 1990, 27 pp. (Russian).

4. A short course of mathematical logic. Novosibirsk State Pedagogical Institute, 1992, 84 pp. (Russian).

5. Exercises in Pascal-programming (jointly with V. N. Timkin). Methodical Notes, Novosibirsk State Pedagogical University, 1993, 35 pp. (Russian).

6. A short course of mathematical logic (jointly with A. A. Uhrmann and A. B. Khutoretski). Novosibirsk State Pedagogical University, 1997, 160 pp. (Russian).

7. Lectures on probability and statistics. Novosibirsk State Pedagogical University, 2001, 133 pp. (Russian).

8. A method of teaching to basics of computer modeling (jointly with E.T. Selivanova). Novosibirsk State Pedagogical University, 2002, 165 pp. (Russian).

9. Organizing research of students and schoolchildren in informatics (jointly with A.P. Grishaeva and E.T. Selivanova). Novosibirsk State Pedagogical University, 2003, 101 pp. (Russian).

10. Introduction to programming in Delphi (jointly with D.G. Pupinin and V.N. Timkin). Novosibirsk State Pedagogical University, 2004, 294 pp. (Russian).

Publications on didactics of mathematics and informatics

1. Conferences in informatics as a form of creative activity of pupils (jointly with A.A. Moskvitin, A.A. Shreiner and V.N. Timkin). Methodical Notes. Novosibirsk, 1996, 38 p. (Russian).

2. Dynamical systems and fractals in informatics curriculum. Abstracts of nd Congress on Industrial and Applied Math., Novosibirsk, 1998, v. 3, 254 (Russian).

3. Informatization of education: evolution, problems, prospects (jointly with E.T. Selivanova). Abstracts of UNESCO Conf. «Ecology of Man», Novosibirsk, 1998, v.2, part. 1, 170--177 (Russian).

4. LISP and PROLOG as teaching programs. Abstracts of Int. Conf. New Techn. in University Education (electronic version), Novosibirsk, 1998, 1 p.

5. On non-lesson forms of teaching informatics. Abstracts of Int. Conf. «New information technologies in university education», Novosibirsk, 1998, 111 (Russian).

6. Distance learning in high school (jointly with I.L. Gorbachev). Abstracts of Int. Conf. «New information technologies in university education», Novosibirsk, 1999, 201--202 (Russian).

7. Informatics for schoolchildren in form of UPK (example of commerce courses ZAO SOC), jointly with V.N. Timkin. Abstracts of Int. Conf. «New information technologies in university education», Novosibirsk, 1999, --136 (Russian).

8. On a more exact notion of executor and its use for teaching algorithmization (jointly with O.V. Anufriev). Abstracts of Int. Conf. «New information technologies in university education», Tomsk, 2000, 76--77 (Russian).

9. Presenting mathematics in the Internet (Russian, jointly with E.V. Kotov). Abstracts of Conf. «Higher Education-XXI and Culture». Kazan, KSTU, 2000, 37--38.

10. A technology for designing hypertext training appliences (Russian, jointly with E.V. Kotov). Abstracts of Conf. on Problems of Teaching Informatics in 21st Century, Kuibishev, 2001, 82--85.

11. On a more exact notion of executor and its use for teaching algorithmization (jointly with O.V. Anufriev). Proceedings of Novosibirsk State University (Pedagogics), v. 2 (2001), 81--90 (Russian).

12. On some problems of development of distance learning (Russian, jointly with I.G. Kaukin). Abstracts of Conf. on Problems of Teaching Informatics in 21st Century., Kuibishev, 2001, 118--121.

13. Requirements to personnel of information technologies department of a university. Abstracts of Int. Conf. «New information technologies in university education», Novosibirsk, 2001, 186--187 (Russian, jointly with I. G. Kaukin).

14. Teaching algorithmization with the use of executors. Informatics and Education, 9 (2001) 56--62 (Russian, jointly with O.V. Anufriev).

15. The method of templates and tasks in teaching of HTML fundamentas. Abstracts of Int. Conf. «New information technologies in university education», Novosibirsk, 2001, 121--122. (Russian, jointly with E.V. Kotov).

16. Computer modeling in the informatics curriculum. Abstracts of Int. Conf. «New information technologies in university education», Kemerovo, 2002, 148--149 (Russian, jointly with E.T. Selivanova).

17. Projects on computer modeling. Abstracts of 3rd Int. Conf. on Comp. Modeling, 2002, S-Petersburg, Polytechnic Univ., 15--17 (Russian, jointly with E.T. Selivanova).

18. The project of executor realization using a modular approach. Abstracts of Int. Conf. «New information technologies in university education», Kemerovo, 2002, 121--122 (Russian, jointly with O.V. Anufriev).

19. Forming the conditions for informatization of the secondary school (jointly with L.A. Dmitrieva). Int. Conf. «Perspective of Informatics systems. Informatics of Education», Novosibirsk, 2003, 24--25 (Russian).

20. Forming the educational space of school informatization (jointly with A.P. Grishaeva). Int. Conf. «Perspective of Informatics systems. Informatics of Education», Novosibirsk, 2003, 20--22 (Russian).

21. Organization and methodics of training of informatics teachers in pedagogical university (jointly with A.P. Grishaeva and E.T. Selivanova). Abstracts of Int. Conf. «New information technologies in university education», v. 1, Novosibirsk, 2003, --130 (Russian).

22. Problems and prospects of informatization of the school education space (jointly with A.P. Grishaeva). Int. Conf. «Quality of control over the education space of a region», part 1, Novosibirsk State Pedagogical University, 2003, 459--461 (Russian).