Vectorization hierarchies of some graph quantifiers
type: Item
instance of: scholarly article
title: Vectorization hierarchies of some graph quantifiers
zbMATH Open document ID: 0956.03036
author: Lauri Hella
author: Juha Nurmonen
published in: Archive for Mathematical Logic
publication date: 2001-03-13T00:00:00Z
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.
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03C80
zbMATH DE Number: 1463219
zbMATH Keywords: Ehrenfeucht-Fraissé games
zbMATH Keywords: finite model-theory
zbMATH Keywords: generalized quantifier
zbMATH Keywords: vectorization hierarchy
reviewed by: Jörg Flum
MaRDI profile type: Publication
full work available at URL: s001530050141
OpenAlex ID: W2044253312
DOI: 10.1007/S001530050141
Recommended article: A note on vector representation of graphs
Recommended article: On vectorizations of unary generalized quantifiers
Recommended article: Vector representations of graphs
Recommended article: Q3983485
Recommended article: On some properties of vector space based graphs
Recommended article: Graph quasivarieties
Recommended article: Q5091117
Recommended article: On the expressive power of linear algebra on graphs
Recommended article: The monadic quantifier alternation hierarchy over grids and graphs
description: scientific article; zbMATH DE number 1463219