{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:03:19Z","timestamp":1760079799725,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,11,14]],"date-time":"2013-11-14T00:00:00Z","timestamp":1384387200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"crossref","award":["EP\/H026835\/1"],"award-info":[{"award-number":["EP\/H026835\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Motivated by the quest for a logic for PTIME and recent insights that the\ndescriptive complexity of problems from linear algebra is a crucial aspect of\nthis problem, we study the solvability of linear equation systems over finite\ngroups and rings from the viewpoint of logical (inter-)definability. All\nproblems that we consider are decidable in polynomial time, but not expressible\nin fixed-point logic with counting. They also provide natural candidates for a\nseparation of polynomial time from rank logics, which extend fixed-point logics\nby operators for determining the rank of definable matrices and which are\nsufficient for solvability problems over fields. Based on the structure theory\nof finite rings, we establish logical reductions among various solvability\nproblems. Our results indicate that all solvability problems for linear\nequation systems that separate fixed-point logic with counting from PTIME can\nbe reduced to solvability over commutative rings. Moreover, we prove closure\nproperties for classes of queries that reduce to solvability over rings, which\nprovides normal forms for logics extended with solvability operators. We\nconclude by studying the extent to which fixed-point logic with counting can\nexpress problems in linear algebra over finite commutative rings, generalising\nknown results on the logical definability of linear-algebraic problems over\nfinite fields.<\/jats:p>","DOI":"10.2168\/lmcs-9(4:12)2013","type":"journal-article","created":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T09:37:51Z","timestamp":1405417071000},"source":"Crossref","is-referenced-by-count":8,"title":["Definability of linear equation systems over groups and rings"],"prefix":"10.46298","volume":"Volume 9, Issue 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4014-8248","authenticated-orcid":false,"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5588-1181","authenticated-orcid":false,"given":"Eryk","family":"Kopczynski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bjarki","family":"Holm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erich","family":"Gr\u00e4del","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wied","family":"Pakusa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2013,11,14]]},"reference":[{"key":"844:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/725\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/725\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:54:43Z","timestamp":1681242883000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,14]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(4:12)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1204.3022","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1204.3022","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2013,11,14]]},"article-number":"725"}}