{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T20:04:34Z","timestamp":1748635474771},"reference-count":14,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T00:00:00Z","timestamp":1632441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,4,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In recent years, computability theorists have extensively studied generically and coarsely computable sets. This study of approximate computability was originally motivated by asymptotic density problems in combinatorial group theory. We generalize the notions of generic and coarse computability of sets, introduced by Jockusch and Schupp, to arbitrary structures by defining generically and coarsely computable and computably enumerable structures. There are two directions in which these notions could potentially trivialize: either all structures could have a densely computable copy or only those having a computable (or computably enumerable) copy. We show that some particular classes of structures realize each of these extremal conditions, while other classes realize neither of them. To further explore these concepts, we introduce a graded family of elementarity conditions for substructures, in which we require that the dense sets under consideration be \u2018strong\u2019 substructures of the original structure. Here, again, for a given class, the notion could trivialize in the same two directions and we show that both are possible. For each class that we investigate, there is some natural number $n$ such that requiring $\\varSigma _{n}$ elementarity of substructures is enough to trivialize the class of generically or densely computable structures, witnessing the essentially structural character of these notions.<\/jats:p>","DOI":"10.1093\/logcom\/exab057","type":"journal-article","created":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T11:45:24Z","timestamp":1631101524000},"page":"581-607","source":"Crossref","is-referenced-by-count":4,"title":["Densely computable structures"],"prefix":"10.1093","volume":"32","author":[{"given":"Wesley","family":"Calvert","sequence":"first","affiliation":[{"name":"Department of Mathematics, Mail Code 4408, Southern Illinois University, 1245 Lincoln Drive, Carbondale, IL 62901, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas","family":"Cenzer","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentina","family":"Harizanov","sequence":"additional","affiliation":[{"name":"Department of Mathematics, George Washington University, Washington, DC 20052, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,9,24]]},"reference":[{"key":"2022041208373642900_ref1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.apal.2005.10.002","article-title":"Effective categoricity of equivalence structures","volume":"141","author":"Calvert","year":"2006","journal-title":"Annals of Pure and Applied Logic"},{"key":"2022041208373642900_ref2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.apal.2008.11.003","article-title":"Effective categoricity of abelian p-groups","volume":"159","author":"Calvert","year":"2009","journal-title":"Annals of Pure and Applied Logic"},{"key":"2022041208373642900_ref3","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/j.apal.2011.01.002","article-title":"${\\varSigma }_1^0$ and ${\\varPi }_1^0$ structures","volume":"162","author":"Cenzer","year":"2011","journal-title":"Annals of Pure and Applied Logic"},{"key":"2022041208373642900_ref4","first-page":"390","article-title":"Computability theoretic properties of injection structures","volume":"53","author":"Cenzer","year":"2014","journal-title":"Algebra and Logic"},{"key":"2022041208373642900_ref5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1002\/malq.201300081","article-title":"Asymptotic density and the Ershov hierarchy","volume":"61","author":"Downey","year":"2015","journal-title":"Mathematical Logic Quarterly"},{"key":"2022041208373642900_ref6","first-page":"135005","article-title":"Asymptotic density and computably enumerable sets","volume":"14","author":"Downey","year":"2013","journal-title":"Journal of Mathematical Logic"},{"key":"2022041208373642900_ref7","article-title":"Asymptotic Invariants of Infinite Groups, (proceedings of the symposium held in Sussex, 1991)","volume-title":"Geometric Group Theory","author":"Gromov","year":"1993"},{"key":"2022041208373642900_ref8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","article-title":"Hyperbolic groups","volume-title":"Essays in Group Theory","author":"Gromov","year":"1987"},{"key":"2022041208373642900_ref9","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/978-3-319-50062-1_30","article-title":"Asymptotic density and the theory of computability: a partial survey","author":"Jockusch","year":"2017","journal-title":"Computability and Complexity"},{"key":"2022041208373642900_ref10","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1112\/jlms\/jdr051","article-title":"Generic computability, Turing degrees and asymptotic","volume":"85","author":"Jockusch","year":"2012","journal-title":"Journal of London Mathematical Society"},{"key":"2022041208373642900_ref11","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","article-title":"Generic-case complexity, decision problems in group theory, and random walks","volume":"264","author":"Kapovich","year":"2003","journal-title":"Journal of Algebra"},{"key":"2022041208373642900_ref12","doi-asserted-by":"crossref","first-page":"5427","DOI":"10.1090\/proc\/12669","article-title":"A robuster Scott rank","volume":"143","author":"Montalban","year":"2015","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2022041208373642900_ref13","volume-title":"The Theory of Groups","author":"Rotman","year":"1965"},{"key":"2022041208373642900_ref14","volume-title":"Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets","author":"Soare","year":"1987"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/3\/581\/43365784\/exab057.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/3\/581\/43365784\/exab057.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T08:37:57Z","timestamp":1649752677000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/32\/3\/581\/6374338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,24]]},"references-count":14,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,9,24]]},"published-print":{"date-parts":[[2022,4,12]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab057","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,4]]},"published":{"date-parts":[[2021,9,24]]}}}