On the Descriptive Complexity of Linear Algebra

DOI10.1007/978-3-540-69937-8_2MaRDI QIDQ3511442zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar

Publication date 10 July 2008

Published in Logic, Language, Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69937-8_2

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Recommendations

• Descriptive complexity of linear equation systems and applications to propositional proof complexity
• Definability of linear equation systems over groups and rings
• Definability of linear equation systems over groups and rings
• On fixed-point logic with counting
• The expressive power of fixed-point logic with counting

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• A restricted second order logic for finite structures
• Affine Systems of Equations and Counting Infinitary Logic
• An extension of fixpoint logic with a symmetry-based choice construct
• An optimal lower bound on the number of variables for graph identification
• Computer Science Logic
• Elements of finite model theory.
• Fast Parallel Matrix Inversion Algorithms
• Fixed-point Logics with Nondeterministic Choice
• On finite rigid structures
• On polynomial time computation over unordered structures
• Relational queries computable in polynomial time
• Structure and complexity of relational queries
• Structure and importance of logspace-MOD class
• The expressive power of fixed-point logic with counting

Cited in

(15)

• On the expressive power of linear algebra on graphs
• On the expressive power of linear algebra on graphs
• Capturing the polynomial hierarchy by second-order revised Krom logic
• A descriptive complexity approach to the linear hierarchy.
• Experimental descriptive complexity
• On the Teaching Complexity of Linear Sets
• Descriptive complexity of linear equation systems and applications to propositional proof complexity
• Database Theory, Yuri, and Me
• On the expressive power of query languages for matrices
• Definability of linear equation systems over groups and rings
• Formal theories for linear algebra
• On sets of linear forms of maximal complexity
• On the descriptive complexity of \(\overline{\varSigma ^*\overline{L}}\)
• On the teaching complexity of linear sets
• Definability of linear equation systems over groups and rings

This page was built for publication: On the Descriptive Complexity of Linear Algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511442)