Formal Theories for Linear Algebra

Stephen A Cook; Lila A Fontes

doi:10.2168/LMCS-8(1:25)2012

Stephen A Cook ; Lila A Fontes - Formal Theories for Linear Algebra

lmcs:716 - Logical Methods in Computer Science, March 16, 2012, Volume 8, Issue 1 - https://doi.org/10.2168/LMCS-8(1:25)2012

Formal Theories for Linear AlgebraArticle

Authors: Stephen A Cook ; Lila A Fontes

We introduce two-sorted theories in the style of [CN10] for the complexity classes \oplusL and DET, whose complete problems include determinants over Z2 and Z, respectively. We then describe interpretations of Soltys' linear algebra theory LAp over arbitrary integral domains, into each of our new theories. The result shows equivalences of standard theorems of linear algebra over Z2 and Z can be proved in the corresponding theory, but leaves open the interesting question of whether the theorems themselves can be proved.

Comment: This is a revised journal version of the paper "Formal Theories for Linear Algebra" (Computer Science Logic) for the journal Logical Methods in Computer Science

https://doi.org/10.2168/LMCS-8(1:25)2012

Source: arXiv.org:1101.1449

Volume: Volume 8, Issue 1

Secondary volumes: Selected Papers of the 24th International Workshop on Computer Science Logic and the 19th Annual Conference of the EACSL (CSL 2010)

Published on: March 16, 2012

Imported on: January 10, 2011

Keywords: Computer Science - Logic in Computer Science, F.4.0

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

29 Documents citing this article

2019, Bibliography, Cambridge University Press eBooks, pp. 481-505, 10.1017/9781108242066.025.

Jan Krajíček, 2019, Algebraic and Geometric Proof Systems, Cambridge University Press eBooks, pp. 337-352, 10.1017/9781108242066.018.

Jan Krajíček, 2019, Frege Systems, Cambridge University Press eBooks, pp. 39-63, 10.1017/9781108242066.004.

Jan Krajíček, 2019, Up to EF via the 〈. . .〉 Translation, Cambridge University Press eBooks, pp. 197-210, 10.1017/9781108242066.012.

Jan Krajíček, 2019, Quantified Propositional Calculus, Cambridge University Press eBooks, pp. 81-92, 10.1017/9781108242066.006.

Jan Krajíček, 2019, Beyond EF via the || . . . || Translation, Cambridge University Press eBooks, pp. 233-260, 10.1017/9781108242066.014.

Jan Krajíček, 2019, Index, Cambridge University Press eBooks, pp. 510-516, 10.1017/9781108242066.026.

Jan Krajíček, 2019, Further Proof Systems, Cambridge University Press eBooks, pp. 134-162, 10.1017/9781108242066.009.

Jan Krajíček, 2019, Algebraic and Geometric Proof Systems, Cambridge University Press eBooks, pp. 115-133, 10.1017/9781108242066.008.

Jan Krajíček, 2019, Proof Complexity, Cambridge University Press eBooks, 10.1017/9781108242066.

Jan Krajíček, 2019, The Two Worlds of Bounded Arithmetic, Cambridge University Press eBooks, pp. 185-196, 10.1017/9781108242066.011.

Jan Krajíček, 2019, Hard Tautologies, Cambridge University Press eBooks, pp. 413-441, 10.1017/9781108242066.021.

Jan Krajíček, 2019, Concepts and Problems, Cambridge University Press eBooks, pp. 11-38, 10.1017/9781108242066.003.

Jan Krajíček, 2019, Fd and Logical Restrictions, Cambridge University Press eBooks, pp. 306-336, 10.1017/9781108242066.017.

Jan Krajíček, 2019, Introduction, Cambridge University Press eBooks, pp. 1-8, 10.1017/9781108242066.002.

Jan Krajíček, 2019, R and R-Like Proof Systems, Cambridge University Press eBooks, pp. 263-295, 10.1017/9781108242066.015.

Jan Krajíček, 2019, Sequent Calculus, Cambridge University Press eBooks, pp. 64-80, 10.1017/9781108242066.005.

Jan Krajíček, 2019, Preface, Proof Complexity, pp. xiii-xiv, 10.1017/9781108242066.001.

Jan Krajíček, 2019, Resolution, Cambridge University Press eBooks, pp. 93-114, 10.1017/9781108242066.007.

Jan Krajíček, 2019, The Nature of Proof Complexity, Cambridge University Press eBooks, pp. 472-480, 10.1017/9781108242066.024.

Jan Krajíček, 2019, Optimality, Cambridge University Press eBooks, pp. 456-471, 10.1017/9781108242066.023.

Jan Krajíček, 2019, Model Theory and Lower Bounds, Cambridge University Press eBooks, pp. 442-455, 10.1017/9781108242066.022.

Jan Krajíček, 2019, LKd+1/2 and Combinatorial Restrictions, Cambridge University Press eBooks, pp. 296-305, 10.1017/9781108242066.016.

Jan Krajíček, 2019, Basic Example of the Correspondence between Theories and Proof Systems, Cambridge University Press eBooks, pp. 165-184, 10.1017/9781108242066.010.

Jan Krajíček, 2019, Feasible Interpolation: Applications, Cambridge University Press eBooks, pp. 384-410, 10.1017/9781108242066.020.

Jan Krajíček, 2019, Examples of Upper Bounds and p-Simulations, Cambridge University Press eBooks, pp. 211-232, 10.1017/9781108242066.013.

Jan Krajíček, 2019, Feasible Interpolation: A Framework, Cambridge University Press eBooks, pp. 353-383, 10.1017/9781108242066.019.

Moses Ganardi;Danny Hucke;Daniel König;Markus Lohrey, 2018, Circuits and Expressions over Finite Semirings, ACM Transactions on Computation Theory, 10, 4, pp. 1-30, 10.1145/3241375.

Daniel König;Markus Lohrey, 2017, Evaluation of Circuits Over Nilpotent and Polycyclic Groups, Algorithmica, 80, 5, pp. 1459-1492, 10.1007/s00453-017-0343-z.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3509 times.

This article's PDF has been downloaded 1003 times.