{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:18Z","timestamp":1761611238047},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2202,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The logic<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004643_inline1\" \/>extends first-order logic by a generalized form of counting quantifiers (\u201cthe number of elements satisfying \u2026 belongs to the set<jats:italic>C<\/jats:italic>\u201d). This logic is investigated for structures with an injectively<jats:italic>\u03c9<\/jats:italic>-automatic presentation. If first-order logic is extended by an infinity-quantifier, the resulting theory of any such structure is known to be decidable [6]. It is shown that, as in the case of automatic structures [21], also modulo-counting quantifiers as well as infinite cardinality quantifiers (\u201cthere are<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004643_inline2\" \/>many elements satisfying \u2026\u201d) lead to decidable theories. For a structure of bounded degree with injective<jats:italic>\u03c9<\/jats:italic>-automatic presentation, the fragment of<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004643_inline1\" \/>that contains only effective quantifiers is shown to be decidable and an elementary algorithm for this decision is presented. Both assumptions (<jats:italic>\u03c9<\/jats:italic>-automaticity and bounded degree) are necessary for this result to hold.<\/jats:p>","DOI":"10.2178\/jsl\/1208358745","type":"journal-article","created":{"date-parts":[[2008,10,14]],"date-time":"2008-10-14T15:19:02Z","timestamp":1223997542000},"page":"129-150","source":"Crossref","is-referenced-by-count":15,"title":["First-order and counting theories of<i>\u03c9<\/i>-automatic structures"],"prefix":"10.1017","volume":"73","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200004643_ref020","first-page":"168","volume-title":"Proceedings of the IEEE Symposium on Logic in Computer Science (LICS)","author":"Khoussainov","year":"2003"},{"key":"S0022481200004643_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39813-4_24"},{"key":"S0022481200004643_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60178-3_93"},{"key":"S0022481200004643_ref016","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200410013"},{"key":"S0022481200004643_ref017","unstructured":"Khoussainov B. , Hjorth G. , Montalban A. , and Nies A. , From automatic structures to Borel structures, 2007, manuscript."},{"key":"S0022481200004643_ref027","volume-title":"Infinite Words","volume":"141","author":"Perrin","year":"2004"},{"key":"S0022481200004643_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/11690634_22"},{"key":"S0022481200004643_ref024","doi-asserted-by":"crossref","DOI":"10.1515\/9783112546369","volume-title":"Algebraische Codierungstheorie","author":"Lindner","year":"1977"},{"key":"S0022481200004643_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80051-6"},{"key":"S0022481200004643_ref015","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029832"},{"key":"S0022481200004643_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"S0022481200004643_ref026","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200004643_ref013","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S0022481200004643_ref001","unstructured":"B\u00e1r\u00e1ny V. , Automatic presentations of infinite structures, Ph.D. thesis, RWTH Aachen, Fakult\u00e4t f\u00fcr Mathematik, Informatik und Naturwissenschaften, 2007."},{"key":"S0022481200004643_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876642"},{"key":"S0022481200004643_ref003","first-page":"1280","volume":"62","author":"B\u00e8s","year":"1997","journal-title":"Undecidable extensions of Biichi arithmetic and Cobham-Semenov theorem"},{"key":"S0022481200004643_ref004","volume-title":"Automatic structures","author":"Blumensath","year":"1999"},{"key":"S0022481200004643_ref005","first-page":"51","volume-title":"Proceedings of the IEEE Symposium on Logic in Computer Science (LICS)","author":"Blumensath","year":"2000"},{"key":"S0022481200004643_ref028","first-page":"1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC)","author":"Stockmeyer","year":"1973"},{"key":"S0022481200004643_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90042-1"},{"key":"S0022481200004643_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"S0022481200004643_ref007","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0022481200004643_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.06.011"},{"key":"S0022481200004643_ref010","doi-asserted-by":"crossref","DOI":"10.1201\/9781439865699","volume-title":"Word Processing in Groups","author":"Epstein","year":"1992"},{"key":"S0022481200004643_ref011","first-page":"105","volume-title":"Logic Colloquium '81","author":"Gaifman","year":"1982"},{"key":"S0022481200004643_ref012","first-page":"31","volume-title":"Colloquium on the Foundations of Mathematics, Mathematical Machines and their Applications (Tihany, 1962)","author":"H\u00e4rtig","year":"1965"},{"key":"S0022481200004643_ref019","first-page":"467","article-title":"Graphs with automatic presentations over a unary alphabet","volume":"6","author":"Khoussainov","year":"2001","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0022481200004643_ref021","first-page":"440","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS)","volume":"2996","author":"Khoussainov","year":"2004"},{"key":"S0022481200004643_ref025","first-page":"344","volume-title":"Proceedings of the 10th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR)","volume":"2850","author":"Lohrey","year":"2003"},{"key":"S0022481200004643_ref030","first-page":"133","volume-title":"Handbook of Theoretical Computer Science","author":"Thomas","year":"1990"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200004643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T11:57:27Z","timestamp":1684583847000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200004643\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["S0022481200004643"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1208358745","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]}}}