|
Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2011, Volume 274, Pages 291–296
(Mi tm3315)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Finite quantifier hierarchies in relational algebras
A. L. Semenov, S. F. Soprunov Dorodnicyn Computing Centre, Russian Academy of Sciences, Moscow, Russia
Abstract:
For a given structure of finite signature, one can construct a hierarchy of classes of relations definable in this structure according to the number of quantifier alternations in the formulas expressing the relations. In ordinary examples, this hierarchy is either infinite (as in the arithmetic of addition and multiplication of natural numbers) or stabilizes very rapidly (in structures with decidable theories, such as the field of real numbers). In the present paper, we construct a series of examples showing that the above-mentioned hierarchy may have an arbitrary finite length. The proof employs a modification of the Ehrenfeucht game.
Received in December 2010
Citation:
A. L. Semenov, S. F. Soprunov, “Finite quantifier hierarchies in relational algebras”, Algorithmic aspects of algebra and logic, Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday, Trudy Mat. Inst. Steklova, 274, MAIK Nauka/Interperiodica, Moscow, 2011, 291–296; Proc. Steklov Inst. Math., 274 (2011), 267–272
Linking options:
https://www.mathnet.ru/eng/tm3315 https://www.mathnet.ru/eng/tm/v274/p291
|
Statistics & downloads: |
Abstract page: | 379 | Full-text PDF : | 57 | References: | 76 |
|