{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:59Z","timestamp":1753889759067,"version":"3.41.2"},"reference-count":19,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,3,16]],"date-time":"2012-03-16T00:00:00Z","timestamp":1331856000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We introduce two-sorted theories in the style of [CN10] for the complexity\nclasses \\oplusL and DET, whose complete problems include determinants over Z2\nand Z, respectively. We then describe interpretations of Soltys' linear algebra\ntheory LAp over arbitrary integral domains, into each of our new theories. The\nresult shows equivalences of standard theorems of linear algebra over Z2 and Z\ncan be proved in the corresponding theory, but leaves open the interesting\nquestion of whether the theorems themselves can be proved.<\/jats:p>","DOI":"10.2168\/lmcs-8(1:25)2012","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T10:03:11Z","timestamp":1346925791000},"source":"Crossref","is-referenced-by-count":2,"title":["Formal Theories for Linear Algebra"],"prefix":"10.46298","volume":"Volume 8, Issue 1","author":[{"given":"Stephen A","family":"Cook","sequence":"first","affiliation":[]},{"given":"Lila A","family":"Fontes","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,3,16]]},"reference":[{"key":"10.2168\/LMCS-8(1:25)2012_AKS04","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"10.2168\/LMCS-8(1:25)2012_Allender04","unstructured":"Eric Allender. Arithmetic Circuits and Counting Complexity Classes. In Jan Krajicek, editor,Complexity of computations and proofs, pages 33-72. Quaderni di Matematica, 2004."},{"key":"10.2168\/LMCS-8(1:25)2012_AllenderOg96","first-page":"1","volume":"30","author":"Eric Allender and Mitsunori Ogihara","year":"1996","journal-title":"RAIRO - Theoretical Informatics and Applications 1996"},{"key":"10.2168\/LMCS-8(1:25)2012_BBP94","doi-asserted-by":"crossref","unstructured":"Maria Luisa Bonet, Samuel R. Buss, and Toniann Pitassi. Are there Hard Examples for Frege Systems? In P. Clote and J. B. Remmel, editors,Feasible Mathematics II, pages 30-56. Birkhauser, 1994.","DOI":"10.1007\/978-1-4612-2566-9_3"},{"key":"10.2168\/LMCS-8(1:25)2012_BuntrockDaHeMe92","doi-asserted-by":"publisher","DOI":"10.1007\/BF01374526"},{"key":"10.2168\/LMCS-8(1:25)2012_Berkowitz84","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"10.2168\/LMCS-8(1:25)2012_BravermanKuRo09","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0266-4"},{"key":"10.2168\/LMCS-8(1:25)2012_CookFo10","doi-asserted-by":"crossref","unstructured":"Stephen Cook and Lila Fontes. Formal Theories for Linear Algebra. InComputer Science Logic, volume LNCS 6247, pages 245-259. Springer, 2010.","DOI":"10.1007\/978-3-642-15205-4_21"},{"key":"10.2168\/LMCS-8(1:25)2012_CookNg10","doi-asserted-by":"crossref","unstructured":"Stephen Cook and Phuong Nguyen.Logical Foundations of Proof Complexity. Cambridge University Press, 2010. Draft available from URL http:\/\/www.cs.toronto.edu\/ sacook.","DOI":"10.1017\/CBO9780511676277"},{"key":"10.2168\/LMCS-8(1:25)2012_Cook85","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"10.2168\/LMCS-8(1:25)2012_Fontes10","unstructured":"Lila Fontes. Interpreting LApintoV\u00f8plusLandV#L. Draft available at www.cs.toronto.edu\/ fontes."},{"key":"10.2168\/LMCS-8(1:25)2012_Fontes09","unstructured":"Lila Fontes. Formal Theories for Logspace Counting. Master's thesis, University of Toronto, 2009. Available at http:\/\/arxiv.org\/abs\/1001.1960."},{"key":"10.2168\/LMCS-8(1:25)2012_Immerman99","doi-asserted-by":"crossref","unstructured":"Neil Immerman.Descriptive Complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"10.2168\/LMCS-8(1:25)2012_Jer05","unstructured":"Emil Jer\u00e1bek.Weak pigeonhole principle, and randomized computation. PhD thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2005."},{"key":"10.2168\/LMCS-8(1:25)2012_MV97","unstructured":"Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity.Chicago Journal of Theoretical Computer Science, 5, 1997."},{"key":"10.2168\/LMCS-8(1:25)2012_Nguyen08","unstructured":"Phuong Nguyen.Bounded Reverse Mathematics. PhD thesis, Department of Computer Science, University of Toronto, 2008."},{"key":"10.2168\/LMCS-8(1:25)2012_SoltysCo04","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.10.018"},{"key":"10.2168\/LMCS-8(1:25)2012_Simpson","doi-asserted-by":"crossref","unstructured":"Stephen Simpson.Subsystems of Second Order Arithmetic. Springer, 1999.","DOI":"10.1007\/978-3-642-59971-2"},{"key":"10.2168\/LMCS-8(1:25)2012_Soltys01","unstructured":"Michael Soltys-Kulinicz.The Complexity of Derivations of Matrix Identities. PhD thesis, University of Toronto, 2001."}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/716\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/716\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:54:29Z","timestamp":1681242869000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,16]]},"references-count":19,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(1:25)2012","relation":{"references":[{"id-type":"doi","id":"10.1007\/978-3-642-15205-4_21","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1101.1449","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1101.1449","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,3,16]]},"article-number":"716"}}