Skip Navigation


Journal of Logic and Computation Advance Access originally published online on September 24, 2008
Journal of Logic and Computation 2009 19(1):177-197; doi:10.1093/logcom/exn023
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Selivanov, V. L.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

This article appears in the following Journal of Logic and Computation issue: Special Issue: Logic and Computation in the Real World: CiE 2007 [View the issue table of contents]

Original Articles

Undecidability in Some Structures Related to Computation Theory

Victor L. Selivanov

A.P. Ershov Institute of Informatics Systems, Siberian Division Russian Academy of Sciences

E-mail: vseliv{at}nspu.ru

Received 10 October 2007.

We show that many of the so called discrete weak semilattices considered earlier in a series of author's publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computation theory, we obtain several new undecidability results. This applies e.g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of k-partitions in the Baire space and {omega}-algebraic domains. Whenever possible, we try to determine also the exact degrees of undecidability of the theories under discussion.

Keywords: Semilattice; discrete weak semilattice; partition; reducibility; undecidability; theory



References

  1. Abramsky S, Jung A. Domain theory. In. In: Handbook of Logic in Computer Science.—Abramsky S, et al, eds. (1994) Oxford: Clarendon Press. 1–168.
  2. Davey BA, Pristley HA. Introduction to Lattices and Order. (1994) Cambridge: Cambridge University Press.
  3. van Engelen F, Miller A, Steel J. Rigid Borel sets and better quasiorder theory. Contemporary Mathematics (1987) 65:199–222.
  4. Ershov YL. Theorie der Numerierungen I. Zeitschr. math. Logik Grundl. Math (1973) 19:289–388.
  5. Ershov YL. Theorie der Numerierungen II. Zeitschr. math. Logik Grundl. Math (1975) 21:473–584.
  6. Ershov Yu L. Theory of Numberings. (1977) Moscow: Nauka. (in Russian).
  7. Ershov Yu L. Decidability Problems and Constructive Models. (1980) Moscow: Nauka. (in Russian).
  8. Ershov Yu L, Lavrov IA, Taimanov AD, Taitslin MA. Elementary theories. Uspechi Matematicheskih Nauk (1965) 20:37–108. (Russian).
  9. Hay L. A discrete chain of degrees of index sets. Journal of Symbolic Logic (1972) 37:139–149.[CrossRef][Web of Science]
  10. Hertling P. Topologische Komplexitätsgrade von Funktionen mit endlichem Bild. Informatik-Berichte 152. (1993) Fernuniversität Hagen. 34. December.
  11. Kechris AS. Classical Descriptive Set Theory. (1994) New York: Springer.
  12. Kosub S. Complexity and Partitions. (2000) Würzburg: University of Würzburg. PhD Thesis.
  13. Kosub S, Wagner K. The Boolean hierarchy of NP-partitions. In. In: Lecture Notes of Computer Science. (2000) Berlin: Springer. 157–168.
  14. Kudinov OV, Selivanov VL. Undecidability in the homomorphic quasiorder of finite labeled forests. (2006) Berlin: Springer. 289–296. Journal of Logic and Computation, 17, 1135–1151, 2007 (full version).Vol. 3988 of Lecture Notes in Computer Science.
  15. Kuske D. Theories of orders on the set of words. Theoretical Informatics and Applications (2006) 40:53–74.[CrossRef]
  16. Kuz’mina TM. Structure of m-degrees of index sets of families of partial recursive functions. Algebra and Logic (1981) 20:55–68. (Russian, there is an English translation).
  17. Lavrov IA. Effective inseparability of the set of true and the set of finitely refutable sentences of some elementary theories. Algebra and Logic (1963) 2(N 1):5–18. (Russian).
  18. Lehtonen E. Labeled posets are universal. European Journal of Combinatorics (2007) (in press) (doi:10.1016/j.ejc.2007.02.005).
  19. Mal’cev AI. Algorithms and Recursive Functions. (1970) Groningen: Wolters–Noordhoff.
  20. Mal’cev An A. Upper semilattices of numberings. Preprint of the Institute of Math. (1980) Novosibirsk. (in Russian).
  21. Mohrherr J. Kleene index sets and functional m-degrees. Journal of Symbolic Logic (1983) 48:829–840.[CrossRef][Web of Science]
  22. Nerode A, Shore R. Reducibility orderings: theories, definability and automorphisms. Annals of Mathematical Logic (1980) 61–89.
  23. Nies A. Coding Methods in Computability Theory and Complexity Theory. (1998) Heidelberg: University of Heidelberg. Habilitation thesis.
  24. Nies A, Shore RA, Slaman T. Definability in the recursively enumerable degrees. Bulletin of Symbolic Logic (1996) 2:392–404.[CrossRef]
  25. Odifreddi PG. Classical Recursion Theory. (1999) Amsterdam: Elsevier.
  26. Selivanov VL. On the index sets of computable classes of finite sets. In. Algorithms and Automata, Kazan (1978) 95–99. (Russian).
  27. Selivanov VL. On the structure of degrees of index sets. In. Algebra and Logic (1979) 18:463–480. (Russian, there is an English translation).
  28. Selivanov VL. On the structure of degrees of generalized index sets. Algebra and Logic (1982) 21:472–491. (Russian, there is an English translation).
  29. Selivanov VL. Boolean hierarchy of partitions over reducible bases. Algebra and Logic (2004) 43:77–109. (Russian, there is an English translation).
  30. Selivanov VL. Variations on theWadge reducibility. Siberian Advances in Mathematics (2005) 5:44–80.
  31. Selivanov VL. Towards a descriptive set theory for domain-like structures. Theoretical Computer Science (2006) 365:258–282.[CrossRef][Web of Science]
  32. Selivanov VL. A useful undecidable theory. In. Cooper SB, Löwe B, Sorbi A, eds. (2007) Berlin: Springer. 685–694. Conference Computability in Europe-2007, Vol. 4497 in Lecture Notes in Computer Science.
  33. Selivanov VL. Classifying omega-regular partitions. In. In: Preproceedings of LATA-2007, Universitat Rovira i Virgili Report Series, 35/07. (2007) University of Tarragona. 529–540.
  34. Selivanov VL. On the Wadge reducibility of k-partitions. In Proceedings of the Fourth International Conference on Computability and Complexity in Analysis (CCA-2007). Available at http://dx.doi.org/10.1016/j.entcs.2008.03.008.
  35. Selivanov VL. The quotient algebra of labeled forests modulo h-equivalence. Algebra and Logic (2007) 46:120–133.[CrossRef][Web of Science]
  36. Selivanov VL. Hierarchies of {Delta}Formula-measurable k-partitions. Mathematical Logic Quarterly (2007) 53:446–461.[CrossRef][Web of Science]
  37. Wadge W. Reducibility and determinateness in the Baire space. (1984) Berkely: University of California. PhD thesis.
  38. Wagner K. On {omega}-regular sets. Information and Control (1979) 43:123–177.[CrossRef][Web of Science]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Selivanov, V. L.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?