Vectorization hierarchies of some graph quantifiers

DOI10.1007/S001530050141MaRDI QIDQ1568709zbMATH OpenOpenAlexFDO

Authors Lauri Hella, Juha Nurmonen

Publication date 13 March 2001

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530050141

zbMATH Keywords

Ehrenfeucht-Fraissé gamesfinite model-theorygeneralized quantifiervectorization hierarchy

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80)

Review text

If \(Q\) is a generalized quantifier and \(k\geq 1\), denote by \(Q^k\) the \(k\)th vectorization of \(Q\). The vectorization hierarchy of \(Q\) is unbounded if there are arbitrarily large natural numbers \(k\) such that \(Q^k\) is not expressible in the extension \(\text{FO} (\{Q^l|l<k\})\) of first-order logic FO. Conditions on \(Q\) are presented that guarantee that the vectorization hierarchy is unbounded. Applications to concrete quantifiers are given.

Recommendations

• A note on vector representation of graphs
• On vectorizations of unary generalized quantifiers
• Vector representations of graphs
• scientific article; zbMATH DE number 26845
• On some properties of vector space based graphs
• Graph quasivarieties
• On the expressive power of linear algebra on graphs
• On the expressive power of linear algebra on graphs
• The monadic quantifier alternation hierarchy over grids and graphs

Cited in

(1)

• On vectorizations of unary generalized quantifiers

This page was built for publication: Vectorization hierarchies of some graph quantifiers

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