The long-standing research question of whether there is a logic expressing exactly the polynomial-time decidable properties of finite structures has motivated, in recent years, the exploration of logics with linear-algebriac operators. There have been a number of significant recent results on the expressive power of such logics. This paper surveys some of these results and places them within the context of the general theory of Lindström quantifiers, identifying the key closure properties of these quantifiers and relating them to earlier work on arity hierarchies. It provides pointers to the detailed technical proofs of the results on their expressive power.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Linear Algebraic Quantifiers

  • Anuj Dawar

摘要

The long-standing research question of whether there is a logic expressing exactly the polynomial-time decidable properties of finite structures has motivated, in recent years, the exploration of logics with linear-algebriac operators. There have been a number of significant recent results on the expressive power of such logics. This paper surveys some of these results and places them within the context of the general theory of Lindström quantifiers, identifying the key closure properties of these quantifiers and relating them to earlier work on arity hierarchies. It provides pointers to the detailed technical proofs of the results on their expressive power.