Bakhodyr Khoussainov - Selected Publications#

1. B. Khoussainov, A. Nerode. Automatic presentations of structures. Proceedings of Logic and Computational Complexity Conference, p 367-393, 1994. (founding paper in the theory of automatic structures, an important topic in Logic in Computer Science).

2. C. Calude, P. Hertling, B. Khoussainov, Y. Wang. Recursively enumerable reals and Chaitin Omega numbers. Theor. Computer Science, 255, no. 1-2, p.125-149, 2001 (initiated a modern development of algorithmic randomness).

3. D. Hirschfeldt, B. Khoussainov, R. Shore. A. Slinko. Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, 115, no. 1-3, p.71-113, 2002 (developed new coding techniques in computable structure theory).

4. B. Khoussainov. A quest for algorithmically random infinite structures. Proceedings of joint Logic in Computer Science (LICS 2014) and Computer Science Logic (CSL 2014) conferences, p. 561-569, 2014 (solved the problem of defining algorithmically random structures).

5. B. Khoussainov and A. Miasnikov. Finitely presented expansions of groups, semigroups, and algebras. Trans. Amer. Math. Soc., vol. 366, no. 3, 1455-1474, 2014 (solved an old problem of Bergstra and Tucker in the setting of standard algebraic structures).

6. O. Kharlampovich, B. Khoussainov, A. Miasnikov. From automatic structures to automatic groups, Groups, Geometry, and Dynamical Systems, vol.8, no.1, p.157-198, 2014 (extends the theory of automatic groups answering Thurston's questions).

7. E. Fokina, B. Khoussainov, P. Semukhin, D. Turesky. Linear orders realised by c.e. equivalence relations. Journal of Symbolic logic, vol. 8, no. 2, 463-482, 2016 (initiates the study of c.e. structures).

8. C. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan. Deciding parity games in quasipolynomial time. STOC 2017, p.252-263, 2017
(STOC best paper award, among the most prestigious in the theory of computation worldwide).

9. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan. Deciding Parity Games in Quasi-polynomial Time. SIAM J. Comput. 51(2): 17-152, 2022. (European Association for Theoretical Computer Science, Nerode Prize).

10. Bakh Khoussainov, Toru Takisaka. Infinite Strings and their Large Scale Properties. J. Symb. Log. 87(2): 585-625 (2022)