PDFLINK |

# Calibrating Computational Complexity via Definability: The Work of Julia F. Knight

Communicated by *Notices* Associate Editor Antonio Montalbán

Julia F. Knight, until recently the Charles L. Huisking Professor of Mathematics at the University of Notre Dame, continues to make a significant impact on computability theory and model theory, two subfields of logic, through her research, mentorship, and collaborative approach.

Computability theory provides a framework for calibrating the (idealized) computational content of a mathematical object, whereas model theory is about definability—what can be expressed about a structure in terms of formal syntax. In a nutshell, Knight’s work explores how the complexity of syntactic definitions is strongly connected to the computational content of structures. Knight trained as a model theorist at the University of California, Berkeley, under the supervision of Robert Vaught, a key figure in the field’s development. After completing her doctorate in 1972 and spending a few years at Penn State, Knight arrived at the University of Notre Dame in 1977, where she has remained throughout her career.

Although she has done some purely model-theoretic work, she was drawn early on into questions about the computational content of structures satisfying the axioms of first-order Peano arithmetic. This work marked the start of her path into computability theory, and her role in shaping and promoting computable structure theory, a subfield of computability that focuses on understanding the computational content encoded by mathematical structures.

The primary goal of this article is to describe Knight’s wide-ranging research contributions to logic without assuming background in the field. Her work includes now standard conceptual frameworks that involve an appealing mix of computability-theoretic and model-theoretic ideas and their application to natural examples, some of which are described in her classic text 2 with Chris Ash. In recognition of her research contributions, she was part of the inaugural class of Fellows of the American Mathematical Society in 2012, and she delivered the Association for Symbolic Logic’s Gödel Lecture in 2014. She also holds an Honorary Professorship with the Siberian Branch of the Russian Academy of Sciences.

## 1. Background

### 1.1. Structures, formulas, & arithmetic

A *structure* consists of an underlying set of elements, known as the *domain*, and whatever functions or relations on the domain that are of interest—the set of symbols used to denote these functions and relations is called the *language* of .

One structure studied extensively in logic is the *standard model of arithmetic* whose domain is , the set of natural numbers. ,Footnote^{1} We’ll fix the language of as so comes equipped with the functions giving the successor operation addition, multiplication, the usual order relation, and a constant for , .

Once a language is fixed, one can define a variety of classes of formal statements using symbols in logical connectives, variables, and quantifiers. There are natural rules for interpreting the truth or meaning of these statements within a particular structure. In finitary (elementary) first-order logic, formulas are finite in length and variables are intended to range over only the domain of the structure. ,

For example, for all natural numbers consider the first-order formula ,

When interpreted in *sentences*. A sentence is either true or false in a structure, according to natural interpretation rules; certainly *models* *model* of *theory* of *true arithmetic* (

Nonsentences, such as the subformula of

are valuable for describing subsets of (and relations on) a fixed structure *defines* the following subset of

Since *nonstandard* models of true arithmetic, ones in which there are elements larger than any natural number. In fact, the standard model

The existence of nonstandard models of

In fact, for each countable structure, there is a single sentence in

The sentence guaranteed by Theorem 1 for a structure *Scott sentence* of

*Peano arithmetic* represents mathematicians’ best attempt at giving a useful set of axioms describing the standard model of arithmetic. The axioms of Peano arithmetic are the usual rules for the arithmetic operations and order, along with axioms of the form

which state that induction holds for any finitary first-order formula

and can carry out the inductive proof.

Gödel’s Incompleteness Theorems imply that

### 1.2. Computability

Alan Turing provided the conceptual framework for determining the computational complexity of sets of natural numbers. At the most basic level, a set *computable* if there is an algorithmFootnote^{2} that computes the characteristic function *computably enumerable (c.e.)* if there is an algorithm for listing out the elements of

^{2}

By algorithm we really mean a Turing machine, but an informal understanding suffices here by Church’s thesis.

✖We can discuss the computability of anything that can be encoded by sets of natural numbers. For example, even though neither

Using the same ideas, we can compare the relative complexity of two subsets of natural numbers (or

*computable relative to*

*Turing degree*, the equivalence class of sets that are Turing equivalent to

Just as *halts*, on input

Observe that we can *jump* of

These sets end up serving as an important measuring stick for computational power in the *arithmetical hierarchy*.

#### 1.2.1. The arithmetical hierarchy

Even with its expressive limitations, finitary first-order logic can define many subsets of *Diophantine equation*, one of the form

Theorem 3 together with the existence of non-computable c.e. sets like

This relationship between computational complexity and definability extends to all *arithmetical sets*, those that are definable in *arithmetical hierarchy* classifies these definable subsets by the syntactic complexity of the formulas defining them. A formula (in prenex normal form) is ^{3} The

The arithmetical hierarchy is tightly aligned with the computational complexity of subsets of ^{4} and shows that the hierarchy does not collapse.

## 2. Complexity of Structures

While Knight was at Penn State, Mark Nadel recruited her to join him at the University of Notre Dame in 1977. Like Knight, Nadel was a model theorist studying models of arithmetic from that field’s perspective, but their joint efforts began to require some methods from computability. At the same time, others had become interested in the computational content of models of

Here we’ve begun blurring the idea of a structure with a specific encoding of one. To encode a (countable) structure *atomic diagram* of *presentation* or *copy* of

### 2.1. Degrees of models of arithmetic

Though Tennenbaum had earlier shown that there are no computable nonstandard models of *low* set

The situation for

As for models of

### 2.2. Degrees of presentations

The above work motivated Knight and others to study different presentations of a given countable structure. The degrees of these presentations can vary widely, making the following definition natural.

In 1982, Marker proved that the degree spectrum of a model

Her proof shows how automorphically nontrivial structures are rich enough to allow (and are necessary) for the coding of additional computational information. Knight continued to study questions involving the degree spectra of structures, e.g., what sets are computable in all copies of a given structure, while visiting Jockusch at Urbana-Champaign for her sabbatical in 1984–85 and throughout her career.

## 3. Complexity Between Copies

Knight met Chris Ash, a computability theorist at Monash University who would become a close collaborator, during her 1984–85 sabbatical. Their highly regarded book 2 describes their shared interests (see this text for all references in this section). The book was not intended to be jointly authored, but Knight completed the project after Ash’s untimely death in 1995. The book addresses three kinds of problems regarding the complexity between and within particular copies of a fixed structure. So as to give some concrete motivation,Footnote^{5} we’ll first state their most basic incarnations.

A relation on a structure *intrinsically c.e.* if it has the property in Problem 1. Let *not* to be intrinsically c.e., even though it’s computable in the standard model

Structures *computably categorical*. For example, the usual linear order on the rationals

Though *are*

In earlier work, others explored Problems 1, 2, and 3 as stated, in general and in specific kinds of structures, e.g., Goncharov and independently Remmel proved that the computably categorical linear orders are those with only finitely many successor pairs. However, the answers to the original problems are typically quite complicated. As we’ll see, the problems have more elegant solutions when the copies range over *all* copies of a fixed structure, rather than only those of a given complexity. For example, a computable structure *relatively computably categorical* if for every copy *hyperarithmetical hierarchy*, an extension of the arithmetical hierarchy.

### 3.1. Hyperarithmetical hierarchy

The measuring stick of the arithmetical hierarchy is the sequence

Such ordinals are those that are order-isomorphic to a computable well-ordering. These *computable ordinals* form a countable initial segment of all ordinals; the notation

A subset of *hyperarithmetical* if it is computable from

#### 3.1.1. Computable infinitary formulas

Just like the arithmetical sets, the hyperarithmetical sets can be described in terms of definability. Here we use *computable infinitary formulas*, formulas from

The next theorem, which follows from results related to Theorem 8, provides evidence that the computable infinitary formulas are the “right” logic for the hyperarithmetical setting.

We remark that the

#### 3.1.2. Connection to analytic hierarchy

The hyperarithmetical sets can also be defined in terms of the first level of the *analytical hierarchy*, a classification of subsets of *sets* of natural numbers. Here quantifiers ranging over sets (and their alternations) are what drive complexity. A formula of this kind is ^{6} The hyperarithmetical sets coincide with the

Computable infinitary formulas are also the “right” logic for understanding computable structures (and hyperarithmetical ones too). Most crucially, for any computable ordinal

One can apply Barwise-Kreisel Compactness to show that computable infinitary formulas are capable of distinguishing between nonisomorphic computable structures.

### 3.2. Results on the relativizations

By their nature, Problems 1, 2, and 3 in the introduction to §3 require understanding how computational power is connected to definability. In fact, the resolution of the full relativization of Problem 1 is purely about definability.

A relation *relatively intrinsically *. Recall that the adverb “relatively” here indicates that

*all*copies of

The syntactic conditions in Theorem 8 were first identified in the computable setting by Ash and Anil Nerode and then Ash’s student Ewan Barker. Though those results came first, Theorem 8 can be stated and proven more elegantly, suggesting that combining “relative” approaches leads to stronger results. Progress on Problems 2 and 3 evolved similarly.

The solutions to Problems 2 and 3 (whether relativized or not) involve the ability to effectively enumerate formulas that define certain parts of the structure. Goncharov showed the solution to Problem 2 involves a special kind of *Scott family*, an important tool in the proof of the Scott Isomorphism Theorem.

Showing that the given computational feature implies the desired definability is the difficult direction in both Theorems 8 and 9. The proofs of these portions use forcing, a powerful technique of mathematical logic. Forcing here involves building a “generic” copy

### 3.3. Priority arguments

While Theorems 8 and 9 rely on forcing, the solutions of the original three problems use *finite injury priority constructions*, a fundamental proof technique in computability theory. Friedberg and independently Muchnick first used this method to build a c.e. set

The strategies for satisfying distinct requirements may conflict. In fact, satisfying one requirement may “injure” or undo the satisfaction of another. Hence, an ordering is put on the requirements to make clear at any stage which requirement has priority to act. In a finite injury construction, like that of the Friedberg-Muchnick Theorem and those for the original three problems above, each requirement is injured only finitely often. Though these constructions are computable, knowing when requirements are permanently satisfied is

Shoenfield and Sacks independently invented *infinite injury constructions*, to obtain theorems like Sacks’ result that the degrees of c.e. sets are dense. Determining how requirements are satisfied in these constructions requires increasing amounts of power. For example, Harrington used his “workers” method to obtain a nonstandard model of arithmetic that was arithmetical but whose theory was not. Determining how requirements are met in this construction requires

To ameliorate this situation, Ash developed a black box approach. His “metatheorem” guarantees that if certain effectiveness conditions are satisfied, then an associated infinite injury priority construction will succeed. Knight joined forces with Ash and others to refine this method, develop new variations, e.g., 15, and explore applications, including ones related to the three problems.

## 4. Complexity of Classes of Structures

Though well aware of his work before, Knight met Sergei Goncharov (Novosibirsk State University) at an Association for Symbolic Logic conference in Leeds in the summer of 1997 before joining him at a conference in Kazan. There Goncharov gave a talk describing a variety of effective classification results for specific classes of computable structures (e.g., computable linear orders) and calling for similar results for other natural classes. At the talk, Richard Shore asked Goncharov what would make him give up on finding an effective classification of a particular class. Shore’s question led Knight and Goncharov to explore three known approaches to effective classification and to identify a satisfying answer in 9. This work generated a new wave of interest in both the theory of effective classification and its application to natural classes, from graphs, to fields, to groups.

Let *characterizations* and *classifications* of

### 4.1. Three approaches

#### 4.1.1. Enumerations

Classification in mathematics often takes the form of a list of all distinct possibilities, up to a fixed notion of equivalence, e.g., the classification of finite simple groups. This idea motivates the first approach.

Thus, an enumeration characterizes the computable structures in

#### 4.1.2. Computable infinitary descriptions & Scott rank

The second approach is syntactic, relating to Scott sentences and Scott families. In this approach, an effective characterization of

In a standard proof of the Scott Isomorphism Theorem, one first shows that there is a Scott family for the given structure *Scott rank* of

Turning to a class

#### 4.1.3. Index sets & the isomorphism problem

The third approach measures the computational content of sets involving the “names” of presentations in

Here Goncharov and Knight viewed

#### 4.1.4. Relationships between approaches

At the level of determining whether a class

Theorem 11 provides a robust test for determining whether a class is effectively classifiable. Applying Theorem 11, one can show natural classes like vector spaces over a fixed infinite computable field, algebraically closed fields of fixed characteristic, and archimedean real closed fields are effectively classifiable whereas classes like undirected graphs, fields of fixed characteristic, real closed fields, and linear orders are not.

### 4.2. Finer-grained complexity

A hallmark of Knight’s work is the marriage of theory-building and application, and Knight and her collaborators have used all three approaches to obtain finer-grained information about specific effectively classifiable classes. Exact complexity calculations make use of the structural properties of the class and often employ results of classical (noneffective) mathematics. In this section, we highlight some of this work, beginning with Knight and her collaborators work on free groups in 5. All references in §4.2.1 can be found there.

#### 4.2.1. Free groups

In 1945, Tarski asked whether all free groups with at least two, but not infinitely many, generators are *elementarily equivalent*, i.e., satisfy the same finitary first-order statements in the language of groups. In 2006, Sela and independently Kharlampovich and Myasnikov proved the answer is positive—finitary first-order logic is unable to distinguish between finitely generated free groups of rank at least two. Since all countable free groups have computable presentations, they are distinguished from one another by computable infinitary formulas by Corollary 1. Hence, it’s natural to search for computable infinitary descriptions of these groups. Any such description of these groups puts an upper bound on the computational content of their index sets. A description of a group

Let

Knight and her collaborators, including some of her then current and former students, found optimal descriptions for

When applied to the class of all groups, however, the *locally free* but not free. A group is *locally free* if every finitely generated subgroup is a free group. An example of a locally free but not free group that satisfies the *Nielsen transformations* on collections of words, which are analogous in flavor to row reductions on matrices. Just as there is reduced echelon form for matrices, there is an on words. Given a tuple of words,

Interestingly, the optimal descriptions of the groups and classes are not always the “natural” ones. Knight and her collaborators note that an obvious description of

#### 4.2.2. Friedberg enumerations

Though the three approaches agree on whether a class has an effective classification or not, the exact complexities may differ between approaches. For example, computable Friedberg enumerations exist for vector spaces over a fixed infinite computable field and algebraically closed fields of fixed characteristic, but Calvert showed that the isomorphism problem

Equivalence structures, ones whose domain

Determining whether the class of equivalence structures has a computable Friedberg enumeration proved challenging. Goncharov and Knight were able to show that the class of all equivalence structures with infinitely many infinite classes has a computable Friedberg enumeration, but conjectured that the full class did not. Others proved related but not definitive existence and nonexistence results. However, Goncharov and Knight’s conjecture was false—Downey, Melnikov, and Ng provided a Friedberg enumeration of all equivalence structures in 2017. (See 7 for the attributions in §4.2.2.)

#### 4.2.3. Results when is nonclassifiable

If a class

With Calvert, Goncharov, and Millar, Knight showed that there are computable structures of Scott rank in that they have exactly one countable model up to isomorphism. Millar and Sacks produced a nonhyperarithmetical example of Scott rank

*, but asked whether the example could be made computable. In 2018, Harrison-Trainor, Igusa, and Knight produced such an example (see 10 for the references in this section).* -categorical

Knight, together with a large team, also studied the class of high rank structures using the tools described earlier. They showed that the index set of the class of high rank structures is as complicated as possible, specifically

### 4.3. Another approach to classification

In the early 2000s, Alexander Kechris suggested to Knight that an approach to classification from descriptive set theory might have a natural effective analogue. In descriptive set theory, as above, structures are identified with their atomic diagrams, which in turn are identified with their encodings as elements of Cantor space *Polish space*, a separable and complete metric space. For a class

A coarse measure of classification complexity in this setting is whether the isomorphism relation on

Examples of Borel complete classes include linear orders, trees, and undirected graphs. But Borel reducibility does not allow for distinctions between classes having countably many isomorphism types.

Following Kechris’ suggestion, Knight and her then students Calvert, Cummings, and Miller introduced *computable* and *Turing computable embeddings*, as two ways to distinguish between classes with countably many isomorphism types. Here these embeddings directly translate statements about a structure in

Knight and others 8 also explored an analogous kind of computable embedding introduced by Friedman and Fokina that maps elements of

## 5. Further Contributions

Though we’ve described many important threads of Knight’s work, there are others. We briefly mention a few more.

### 5.1. Computable model theory

Knight would continue to explore ideas connected to those in §2.1. If a theory *Solovay theories* (see their paper 1 for all references in this section). Earlier, Knight and Solovay proved that a set computes a copy of some model of every Solovay theory if and only if it computes a nonstandard model of

More recently, Knight and Andrews studied Solovay theories that are *strongly minimal*, an important class of theories in model-theoretic stability. A *minimal structure* is one in which each subset defined by a finitary first-order formula is finite or cofinite. In other words, the only definable subsets of the domain are those that are definable using equality and inequality alone. A theory is *strongly minimal* if all its models are minimal. Many natural theories are strongly minimal, e.g., those of vector spaces over

Knight and Andrews proved that all countable models of a strongly minimal Solovay theory have a *high* sets over

### 5.2. Recursive saturation, integer parts, & Hahn fields

Recursive saturation is a property of abundance, in that structures with this property have elements that satisfy any reasonable, describable property. Knight extensively studied this important model-theoretic notion and its relationship to models of arithmetic.

As one example of her work in this area, Knight, D’Aquino, and Starchenko studied integer parts of real closed fields 6. (See this citation for references in §5.2.) A real closed field is an ordered field that has the same theory as *integer part*

Shepherdson showed that a discrete ordered ring

To prove a given real closed field *Hahn field*, a field of generalized power series in which the series have ordinal lengths. Understanding this process led Knight and her collaborators to study the complexity of root-taking in Hahn fields and the simpler setting of fields of Puiseux series, when these fields are algebraically closed and of characteristic zero. They proved that Newton’s method for finding roots over a field of Puiseux series is fully computable, and uniformly so for nonconstant polynomials (see 11 for all citations in this paragraph). In the Hahn field setting, Knight and Lange found sharp bounds on the ordinal lengths of roots in terms of the lengths of the polynomial’s coefficients. These length bounds seem to play an important role in understanding the exact complexity of the root-taking process in Hahn fields, an area of ongoing work.

### 5.3.
-minimality

Knight also played a role in the development of *o-minimality*, an important generalization of strong minimality formalized by Anand Pillay and Charles Steinhorn. An *o-minimal structure* is one with an order in which each subset of the domain defined by a finitary first-order formula is a finite union of points and intervals, i.e., those that are definable using only equality and the order alone. In analogy with the strongly minimal setting, a theory is *o-minimal* if all its models are

## 6. Epilogue

Mathematicians can shape their discipline not only through their intellectual contributions but also their approach to the mathematics community. Knight collaborates extensively with others at all career stages, and she generously acknowledges others’ ideas (even when rescuing a germ of a good idea from an ill-conceived proposal).

She supports collaboration and communication in other ways as well. Early in her career, she cofounded the Midwest Model Theory seminar with John Baldwin at Illinois-Chicago. This seminar continues to run today and inspired analogous seminar series in computability in the midwest and northeast. A lack of communication between the East and West led to substantial research duplication in computability during and after the Cold War. Knight has been a major proponent of East/West collaboration, facilitating funding and travel in both directions for logicians. Her efforts along with those of others, particularly Steffen Lempp who started an NSF East/West collaboration grant in the late 1990s that Knight now administers, have helped to integrate these research communities and propel the field forward. She continues to steward the logic community as the immediate past president of the Association for Symbolic Logic.

Knight is an exemplary mentor and advocate for early-career mathematicians (including but not limited to her eighteen doctoral students), greeting new faces at conferences, securing funding, and making valuable introductions. These efforts are not limited to logicians either. She served as Director of Graduate Studies at Notre Dame for many years and was awarded the university’s 2007 James A. Burns, C.S.C., Graduate School Award for distinction in graduate education.

## Acknowledgments

The author is very grateful for Knight’s ongoing mentorship, collaboration, and friendship, and her assistance in putting together this article. She also thanks the anonymous referees for their thoughtful suggestions.

## References

- [1]
- Uri Andrews, Steffen Lempp, and Noah Schweber,
*Building models of strongly minimal theories*, Adv. Math.**386**(2021), Paper No. 107802, 25, DOI 10.1016/j.aim.2021.107802. MR4266747Show rawAMSref`\bib{MR4266747}{article}{ author={Andrews, Uri}, author={Lempp, Steffen}, author={Schweber, Noah}, title={Building models of strongly minimal theories}, journal={Adv. Math.}, volume={386}, date={2021}, pages={Paper No. 107802, 25}, issn={0001-8708}, review={\MR {4266747}}, doi={10.1016/j.aim.2021.107802}, }`

Close amsref.^{✖} - [2]
- C. J. Ash and J. Knight,
*Computable structures and the hyperarithmetical hierarchy*, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR1767842Show rawAMSref`\bib{MR1767842}{book}{ author={Ash, C. J.}, author={Knight, J.}, title={Computable structures and the hyperarithmetical hierarchy}, series={Studies in Logic and the Foundations of Mathematics}, volume={144}, publisher={North-Holland Publishing Co., Amsterdam}, date={2000}, pages={xvi+346}, isbn={0-444-50072-3}, review={\MR {1767842}}, }`

Close amsref.^{✖} - [3]
- W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov, and V. Puzarenko,
*Index sets for classes of high rank structures*, J. Symbolic Logic**72**(2007), no. 4, 1418–1432, DOI 10.2178/jsl/1203350796. MR2371215Show rawAMSref`\bib{MR2371215}{article}{ author={Calvert, W.}, author={Fokina, E.}, author={Goncharov, S. S.}, author={Knight, J. F.}, author={Kudinov, O.}, author={Morozov, A. S.}, author={Puzarenko, V.}, title={Index sets for classes of high rank structures}, journal={J. Symbolic Logic}, volume={72}, date={2007}, number={4}, pages={1418--1432}, issn={0022-4812}, review={\MR {2371215}}, doi={10.2178/jsl/1203350796}, }`

Close amsref.^{✖} - [4]
- Wesley Calvert and Julia F. Knight,
*Classification from a computable viewpoint*, Bull. Symbolic Logic**12**(2006), no. 2, 191–218. MR2223921Show rawAMSref`\bib{MR2223921}{article}{ author={Calvert, Wesley}, author={Knight, Julia F.}, title={Classification from a computable viewpoint}, journal={Bull. Symbolic Logic}, volume={12}, date={2006}, number={2}, pages={191--218}, issn={1079-8986}, review={\MR {2223921}}, }`

Close amsref.^{✖} - [5]
- J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski, and J. Wallbaum,
*Describing free groups*, Trans. Amer. Math. Soc.**364**(2012), no. 11, 5715–5728, DOI 10.1090/S0002-9947-2012-05456-0. MR2946928Show rawAMSref`\bib{MR2946928}{article}{ author={Carson, J.}, author={Harizanov, V.}, author={Knight, J.}, author={Lange, K.}, author={McCoy, C.}, author={Morozov, A.}, author={Quinn, S.}, author={Safranski, C.}, author={Wallbaum, J.}, title={Describing free groups}, journal={Trans. Amer. Math. Soc.}, volume={364}, date={2012}, number={11}, pages={5715--5728}, issn={0002-9947}, review={\MR {2946928}}, doi={10.1090/S0002-9947-2012-05456-0}, }`

Close amsref.^{✖} - [6]
- P. D’Aquino, J. F. Knight, and S. Starchenko,
*Real closed fields and models of Peano arithmetic*, J. Symbolic Logic**75**(2010), no. 1, 1–11, DOI 10.2178/jsl/1264433906. MR2605879Show rawAMSref`\bib{MR2605879}{article}{ author={D'Aquino, P.}, author={Knight, J. F.}, author={Starchenko, S.}, title={Real closed fields and models of Peano arithmetic}, journal={J. Symbolic Logic}, volume={75}, date={2010}, number={1}, pages={1--11}, issn={0022-4812}, review={\MR {2605879}}, doi={10.2178/jsl/1264433906}, }`

Close amsref.^{✖} - [7]
- Rodney G. Downey, Alexander G. Melnikov, and Keng Meng Ng,
*A Friedberg enumeration of equivalence structures*, J. Math. Log.**17**(2017), no. 2, 1750008, 28, DOI 10.1142/S0219061317500088. MR3730564Show rawAMSref`\bib{MR3730564}{article}{ author={Downey, Rodney G.}, author={Melnikov, Alexander G.}, author={Ng, Keng Meng}, title={A Friedberg enumeration of equivalence structures}, journal={J. Math. Log.}, volume={17}, date={2017}, number={2}, pages={1750008, 28}, issn={0219-0613}, review={\MR {3730564}}, doi={10.1142/S0219061317500088}, }`

Close amsref.^{✖} - [8]
- Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles McCoy, and Antonio Montalbán,
*Isomorphism relations on computable structures*, J. Symbolic Logic**77**(2012), no. 1, 122–132, DOI 10.2178/jsl/1327068695. MR2951633Show rawAMSref`\bib{MR2951633}{article}{ author={Fokina, Ekaterina B.}, author={Friedman, Sy-David}, author={Harizanov, Valentina}, author={Knight, Julia F.}, author={McCoy, Charles}, author={Montalb\'{a}n, Antonio}, title={Isomorphism relations on computable structures}, journal={J. Symbolic Logic}, volume={77}, date={2012}, number={1}, pages={122--132}, issn={0022-4812}, review={\MR {2951633}}, doi={10.2178/jsl/1327068695}, }`

Close amsref.^{✖} - [9]
- S. S. Goncharov and Dzh. Naĭt,
*Computable structure and antistructure theorems*(Russian, with Russian summary), Algebra Logika**41**(2002), no. 6, 639–681, 757, DOI 10.1023/A:1021758312697; English transl., Algebra Logic**41**(2002), no. 6, 351–373. MR1967769Show rawAMSref`\bib{MR1967769}{article}{ author={Goncharov, S. S.}, author={Na\u {\i }t, Dzh.}, title={Computable structure and antistructure theorems}, language={Russian, with Russian summary}, journal={Algebra Logika}, volume={41}, date={2002}, number={6}, pages={639--681, 757}, issn={0373-9252}, translation={ journal={Algebra Logic}, volume={41}, date={2002}, number={6}, pages={351--373}, issn={0002-5232}, }, review={\MR {1967769}}, doi={10.1023/A:1021758312697}, }`