This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.
Publié le : 2007-10-14
Classification:
ordered Abelian group,
bounded quantifier,
elimination of unbounded quantifiers,
03C64,
06F20
@article{1193667710,
author = {Scowcroft, Philip},
title = {The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups},
journal = {Notre Dame J. Formal Logic},
volume = {48},
number = {1},
year = {2007},
pages = { 521-550},
language = {en},
url = {http://dml.mathdoc.fr/item/1193667710}
}
Scowcroft, Philip. The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups. Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, pp. 521-550. http://gdmltest.u-ga.fr/item/1193667710/