Algorithmic Properties of Structures for the Language with Two Unary Functional Symbols

E. B. Fokina

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 1, pp. 90-101

Résumé

When studying algorithmic properties of structures with interesting algebraic and model-theoretic properties, one often uses known structural properties of the structures. However, it is often the case that results on particular kinds of structures can be transferred to structures from many other interesting classes. One of the ways of such generalization involves coding of the original structure into a structure from the given class in a way that is effective enough to preserve interesting algorithmic properties. There are several constructions that allow us to reduce algorithmic questions for arbitrary structures to graphs. They also show that if we have a result for a graph, we also have it for a structure for any language containing at least one $n$-ary relational symbol, where $n\geq 2$. We prove that it is possible to generalize this approach and get the same results for structures for a language with two unary functional symbols. Thus, we get the results for structures for so–called rich languages.

Bibliographie

[1] Goncharov S. S., “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19 (1980), 621–639 | MR | Zbl

[2] Goncharov S. S., “Gruppy s konechnym chislom konstruktivizatsii”, Doklady AN SSSR, 256 (1981), 269–272 | MR | Zbl

[3] Goncharov S. S., “Predelno ekvivalentnye konstruktivizatsii”, Matematicheskaya logika i teoriya algoritmov, Tr. In-ta Matematiki, 2, Nauka, Novosibirsk, 1982, 4–12 | Zbl

[4] Goncharov S. S., Schetnye bulevy algebry i razreshimost, Nauchnaya kniga, Novosibirsk, 1996 | MR

[5] Goncharov S. S., Dzgoev V. D., “Avtoustoichivost modelei”, Algebra i logika, 19 (1980), 45–58 | MR | Zbl

[6] Goncharov S. S., Nait Dzh. F., “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41 (2002), 639–681 | MR | Zbl

[7] Goncharov S. S., Molokov A. V., Romanovskii N. S., “Nilpotentnye gruppy konechnoi algoritmicheskoi razmernosti”, Sib. mat. zhurn., 30 (1989), 82–88 | MR

[8] Dobritsa V. P., “Slozhnost indeksnogo mnozhestva konstruktivnoi modeli”, Algebra i logika, 22 (1983), 372–381 | MR | Zbl

[9] Kalvert U., Kammings D., Nait Dzh. F. i dr., “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43 (2004), 666–701 | MR | Zbl

[10] Kalvert U., Kharizanov V., Nait Dzh. F. i dr., “Indeksnye mnozhestva vychislimykh modelei”, Algebra i logika, 45 (2006), 538–574 | MR | Zbl

[11] Nurtazin A. T., Vychislimye klassy i algebraicheskii kriterii avtoustoichivosti, Dis. \ldots kand. fiz.-mat. nauk, In-t matematiki i mekhaniki, Alma-Ata, 1974

[12] Fokina E. B., “Indeksnye mnozhestva razreshimykh modelei”, Sib. mat. zh., 48 (2007), 1167–1179 | MR | Zbl

[13] Khusainov B., Shor R. A., “Reshenie problemy Goncharova–Esha i problema spektra v teorii vychislimykh modelei”, Dokl. Akad. nauk, 371 (2000), 30–31 | MR | Zbl

[14] Calvert W., “The Isomorphism Problem for Classes of Computable Fields”, Archive for Mathematical Logic, 75 (2004), 327–336 | DOI | MR

[15] Calvert W., “The Isomorphism Problem for Computable Abelian $p$-groups of Bounded Length”, J. of Symbolic Logic, 70 (2005), 331–345 | DOI | MR | Zbl

[16] Calvert W., Fokina E., Goncharov S. S. et al., “Index Sets for Classes of High Rank Structures”, J. Symbolic Logic, 72 (2007), 1418–1446 | DOI | MR

[17] Chisholm J., Fokina E., Gocharov S. et al., “Intrinsic Bounds on Complexity and Definability at Limit Levels”, Journal of Mathematical Logic (to appear)

[18] Cholak P., Goncharov S. S., Khoussainov B. et al., “Computably Categorical Structures and Expansions by Constants”, J. Symbolic Logic, 64 (1999), 13–37 | DOI | MR | Zbl

[19] Csima B. F., Montalbán A. et al., “Boolean Algebras, Tarski Invariants, and Index Sets”, Notre Dame J. Formal Logic, 47 (2006), 1–23 | DOI | MR | Zbl

[20] Fokina E. B., “Index Sets of Computable Structures with Decidable Theories”, Computation and Logic in the Real World, Third Conference of Computability in Europe, CiE 2007, Proceedings (Siena, Italy, June 2007), Lecture Notes in Computer Science, 4497, 2007, 290–296 | DOI | MR | Zbl

[21] Goncharov S. S., “Computability and Computable Models”, Mathematical Problems from Applied Logic, v. II, International Mathematical Series, 5, Logics for the XXI Century, eds. Dov M. Gabbay, S. S. Goncharov, M. Zakharyaschev, Springer, N.Y., 2007, 99–216 | DOI | MR | Zbl

[22] Goncharov S. S., Harizanov V., Knight J. F. et al., “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136 (2005), 219–246 | DOI | MR | Zbl

[23] Harizanov V., “The Possible Turing Degree of the Nonzero Member in a Two Element Degree Spectrum”, Ann. Pure Appl. Logic, 60 (1993), 1–30 | DOI | MR | Zbl

[24] Hirschfeldt D. R., Khoussainov B., Shore R. A., “A Computably Categorical Structure whose Expansion by a Constant has Infinite Computable Dimension”, J. Symbolic Logic, 68 (2003), 1199–1241 | DOI | MR | Zbl

[25] Hirschfeldt D. R., Khoussainov B., Shore R. A. et al., “Degree Spectra and Computable Dimensions in Algebraic Structures”, Ann. Pure Appl. Logic, 115 (2002), 71–113 | DOI | MR | Zbl

[26] Khoussainov B., Shore R. A., “Computable Isomorphisms, Degree Spectra of Relations and Scott Families”, Ann. Pure Appl. Logic, 93 (1998), 153–193 | DOI | MR | Zbl

[27] Lempp S., McCoy C., Miller R. et al., “Computable Categoricity of Trees of Finite Height”, J. Symbolic Logic, 70 (2005), 151–215 | DOI | MR | Zbl

[28] Remmel J. B., “Recursively Categorical Linear Orderings”, Proc. Amer. Math. Soc., 83 (1981), 387–391 | DOI | MR | Zbl

[29] Slaman T. A., “Relative to any Nonrecursive Set”, Proc. Amer. Math. Soc., 126 (1998), 2117–2122 | DOI | MR | Zbl

[30] Wehner S., “Enumerations, Countable Structures, and Turing Degrees”, Proc. Amer. Math. Soc., 126 (1998), 2131–2139 | DOI | MR | Zbl