Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-21T18:38:26.716Z Has data issue: false hasContentIssue false
  • English
  • Français

FOUNDATIONS OF ONLINE STRUCTURE THEORY

Published online by Cambridge University Press:  15 April 2019

NIKOLAY BAZHENOV ,
ROD DOWNEY ,
ISKANDER KALIMULLIN  and
ALEXANDER MELNIKOV
NIKOLAY BAZHENOV
Affiliation:
LABORATORY OF COMPUTABILITY THEORY AND APPLIED LOGIC SOBOLEV INSTITUTE OF MATHEMATICS NOVOSIBIRSK, RUSSIA and DEPARTMENT OF MATHEMATICS AND MECHANICS NOVOSIBIRSK STATE UNIVERSITY NOVOSIBIRSK, RUSSIAE-mail: [email protected]
ROD DOWNEY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALANDE-mail: [email protected]
ISKANDER KALIMULLIN
Affiliation:
DEPARTMENT OF MATHEMATICS KAZAN FEDERAL (VOLGA REGION) UNIVERSITY KAZAN, RUSSIAE-mail: [email protected]
ALEXANDER MELNIKOV
Affiliation:
SCHOOL OF NATURAL AND COMPUTATIONAL SCIENCES MASSEY UNIVERSITY AUCKLAND, NEW ZEALANDE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

Keywords

Primary 03D4503C57Secondary 03D7503D80primitive recursiononline computationpunctual set theory
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 25 , Issue 2 , June 2019 , pp. 141 - 181
Copyright
Copyright © The Association for Symbolic Logic 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alaev, P. E., Atomless Boolean algebras computable in polynomial time. Siberian Electronic Mathematical Reports, vol. 13 (2016), pp. 1035–1039.Google Scholar
Alaev, P. E., Structures computable in polynomial time. I. Algebra Logic, vol. 55 (2017), no. 6, pp. 421–435.CrossRefGoogle Scholar
Alaev, P. E., Structures computable in polynomial time. II. Algebra Logic, vol. 56 (2018), no. 6, pp. 429–442.CrossRefGoogle Scholar
Ash, C. and Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, North-Holland, Amsterdam, 2000.Google Scholar
Bazhenov, N., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., and Ng, K. M., Automatic and polynomial-time algebraic structures. The Journal of Symbolic Logic, to appear.Google Scholar
Bazhenov, N., Kalimullin, I., Melnikov, A., and Ng, K. M., Punctual presentations of finitely generated structures, submitted.Google Scholar
Borel, É., Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo, vol. 27 (1909), no. 1, pp. 247–271.CrossRefGoogle Scholar
Borodin, A. and El-Yaniv, R., Online Computation and Competitive Analysis, Cambridge University Press, New York, 1998.Google Scholar
Cenzer, D. A., Downey, R. G., Remmel, J. B., and Uddin, Z., Space complexity of abelian groups. Archive for Mathematical Logic, vol. 48 (2009), no. 1, pp. 115–140.CrossRefGoogle Scholar
Cenzer, D. A. and Remmel, J. B., Polynomial-time versus recursive models. Annals of Pure and Applied Logic, vol. 54 (1991), no. 1, pp. 17–58.CrossRefGoogle Scholar
Cenzer, D. A. and Remmel, J. B., Polynomial-time abelian groups. Annals of Pure and Applied Logic, vol. 56 (1992), no. 1–3, pp. 313–363.CrossRefGoogle Scholar
Cenzer, D. A. and Remmel, J. B., Complexity theoretic model theory and algebra, Handbook of Recursive Mathematics, vol. 1 (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998, pp. 381–513.CrossRefGoogle Scholar
Church, A., On the concept of a random sequence. Bulletin of the American Mathematical Society, vol. 46 (1940), no. 2, pp. 130–135.CrossRefGoogle Scholar
Dedekind, R., Was sind und was sollen die Zahlen? 8te unveränderte Aufl, Friedr. Vieweg & Sohn, Braunschweig, 1960.Google Scholar
Dehn, M., Über unendliche diskontinuierliche Gruppen. Mathematische Annalen, vol. 71 (1911), no. 1, pp. 116–144.CrossRefGoogle Scholar
Dobritsa, V. P., Some constructivizations of abelian groups. Siberian Mathematical Journal, vol. 24 (1983), no. 2, pp. 167–173.CrossRefGoogle Scholar
Downey, R., Computability theory and linear orderings, Handbook of Recursive Mathematics, vol. 2 (Ershov, Yu. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W., editors), Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976.Google Scholar
Downey, R., Turing and randomness, The Turing Guide (Copeland, B. J., Bowen, J. P., Sprevak, M., and Wilson, R., editors), Oxford University Press, Oxford, 2017, pp. 427–436.Google Scholar
Downey, R., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., and Turetsky, D., Graphs are not universal for online computablility, preprint.Google Scholar
Downey, R., Hirschfeldt, D., and Khoussainov, B., Uniformity in the theory of computable structures. Algebra Logika, vol. 42 (2003), no. 5, pp. 566–593, 637.CrossRefGoogle Scholar
Downey, R. G., Kach, A. M., Lempp, S., Lewis-Pye, A. E. M., Montalbán, A., and Turetsky, D. D., The complexity of computable categoricity. Advances in Mathematics, vol. 268 (2015), pp. 423–466.CrossRefGoogle Scholar
Downey, R. G. and McCartin, C., Some new directions and questions in parameterized complexity, Developments in Language Theory (Calude, C. S., Calude, E., and Dinneen, M. J., editors), Lecture Notes in Computer Science, vol. 3340, Springer, Berlin, 2004, pp. 12–26.CrossRefGoogle Scholar
Epstein, D. B. A., Cannon, J. W., Holt, D. F., Levy, S. V. F., Paterson, M. S., and Thurston, W. P., Word Processing in Groups, Jones and Bartlett Publishers, Boston, MA, 1992.CrossRefGoogle Scholar
Ershov, Y. and Goncharov, S., Constructive Models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.CrossRefGoogle Scholar
Ershov, Y. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W. (eds.), Handbook of Recursive Mathematics, vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998.Google Scholar
Fröhlich, A. and Shepherdson, J., Effective procedures in field theory. Philosophical Transactions of the Royal Society of London. Series A, vol. 248 (1956), pp. 407–432.CrossRefGoogle Scholar
Garey, M. R. and Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979.Google Scholar
Goncharov, S., Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997.Google Scholar
Goncharov, S. S. and Nurtazin, A. T., Constructive models of complete solvable theories. Algebra Logic, vol. 12 (1973), no. 2, pp. 67–77.CrossRefGoogle Scholar
Grigorieff, S., Every recursive linear ordering has a copy in DTIME-SPACE(n, log(n)). The Journal of Symbolic Logic, vol. 55 (1990), no. 1, pp. 260–276.CrossRefGoogle Scholar
Harizanov, V. S., Pure computable model theory, Handbook of Recursive Mathematics, vol. 1 (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114.CrossRefGoogle Scholar
Harrington, L., Recursively presentable prime models. The Journal of Symbolic Logic, vol. 39 (1974), pp. 305–309.CrossRefGoogle Scholar
Harrison-Trainor, M., Melnikov, A., Miller, R., and Montalbán, A., Computable functors and effective interpretability. The Journal of Symbolic Logic, vol. 82 (2017), no. 1, pp. 77–97.CrossRefGoogle Scholar
Hermann, G., Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Mathematische Annalen, vol. 95 (1926), no. 1, pp. 736–788.CrossRefGoogle Scholar
Kalimullin, I., Melnikov, A., and Ng, K. M., Algebraic structures computable without delay. Theoretical Computer Science, vol. 674 (2017), pp. 73–98.CrossRefGoogle Scholar
Kalimullin, I. S., Melnikov, A. G., and Ng, K. M., Different versions of categoricity without delays. Algebra Logika, vol. 56 (2017), no. 2, pp. 256–266.CrossRefGoogle Scholar
Kalimullin, I. S., Melnikov, A. G., and Ng, K. M., The diversity of categoricity without delay. Algebra Logic, vol. 56 (2017), no. 2, pp. 171–177.CrossRefGoogle Scholar
Kalimullin, I., Melnikov, A., and Zubkov, M., Punctual degrees and lattice embeddings, preprint.Google Scholar
Kharlampovich, O., Khoussainov, B., and Miasnikov, A., From automatic structures to automatic groups. Groups, Geometry, and Dynamics, vol. 8 (2014), pp. 157–198.CrossRefGoogle Scholar
Khoussainov, B., A quest for algorithmically random infinite structures, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Association for Computing Machinery, New York, 2014, p. 56, Article No. 9.Google Scholar
Khoussainov, B. and Nerode, A., Automatic presentations of structures, Logic and Computational Complexity (Indianapolis, IN, 1994) (Leivant, D., editor), Lecture Notes in Computer Science, vol. 960, Springer, Berlin, 1995, pp. 367–392.Google Scholar
Kierstead, H. A., An effective version of Dilworth’s theorem. Transactions of the American Mathematical Society, vol. 268 (1981), pp. 63–77.Google Scholar
Kierstead, H. A., On line coloring k-colorable graphs. Israel Journal of Mathematics, vol. 105 (1998), no. 1, pp. 93–104.CrossRefGoogle Scholar
Kierstead, H. A., Recursive and on-line graph coloring, Handbook of Recursive Mathematics, vol. 2 (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 1233–1269.Google Scholar
Kierstead, H. A., Penrice, S. G., and Trotter, W. T. Jr., On-line coloring and recursive graph theory. SIAM Journal on Discrete Mathematics, vol. 7 (1994), pp. 72–89.CrossRefGoogle Scholar
Ko, K.-I. and Friedman, H., Computational complexity of real functions. Theoretical Computer Science, vol. 20 (1982), no. 3, pp. 323–352.CrossRefGoogle Scholar
Lovász, L., Saks, M., and Trotter, W. T. Jr., An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, vol. 75 (1989), pp. 319–325.CrossRefGoogle Scholar
Macpherson, D., A survey of homogeneous structures. Discrete Mathematics, vol. 311 (2011), no. 15, pp. 1599–1634CrossRefGoogle Scholar
Mal′cev, A., Constructive algebras. I. Uspekhi Matematicheskikh Nauk, vol. 16 (1961), no. 3(99), pp. 3–60.Google Scholar
Mal′cev, A., On recursive abelian groups. Doklady Akademii Nauk SSSR, vol. 146 (1962), pp. 1009–1012.Google Scholar
Melnikov, A. G., Eliminating unbounded search in computable algebra, Unveiling Dynamics and Complexity (Kari, J., Manea, F., and Petre, I., editors), Lecture Notes in Computer Science, Springer, Cham, 2017, pp. 77–87.CrossRefGoogle Scholar
Melnikov, A. G. and Ng, K. M., The back-and-forth method and computability without delay. Israel Journal of Mathematics, in press.Google Scholar
Metakides, G. and Nerode, A., Effective content of field theory. Annals of Mathematical Logic, vol. 17 (1979), no. 3, pp. 289–320.CrossRefGoogle Scholar
Metakides, G. and Nerode, A., The introduction of nonrecursive methods into mathematics, The L. E. J. Brouwer Centenary Symposium (Noordwijkerhout, 1981) (Troelstra, A. S. and van Dalen, D., editors), Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1982, pp. 319–335.CrossRefGoogle Scholar
Millar, T., Omitting types, type spectrums, and decidability. The Journal of Symbolic Logic, vol. 48 (1983), no. 1, pp. 171–181.CrossRefGoogle Scholar
von Mises, R., Grundlagen der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, vol. 5 (1919), no. 1–2, pp. 52–99.CrossRefGoogle Scholar
Osherson, D., Stob, M., and Weinstein, S., Systems that Learn, MIT Press, Cambridge, MA, 1986.Google Scholar
Remmel, J. B., Graph colorings and recursively bounded ${\rm{\Pi }}_1^0$-classes. Annals of Pure and Applied Logic, vol. 32 (1986), pp. 185–194.CrossRefGoogle Scholar
Tait, W. W., Finitism. The Journal of Philosophy, vol. 78 (1981), pp. 524–546.CrossRefGoogle Scholar
Tsankov, T., The additive group of the rationals does not have an automatic presentation. Journal of Symbolic Logic, vol. 76 (2011), no. 4, pp. 1341–1351.CrossRefGoogle Scholar
Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230–265.Google Scholar
Weihrauch, K., Computable Analysis, Texts in Theoretical Computer Science, An EATCS Series, Springer-Verlag, Berlin, 2000.CrossRefGoogle Scholar