Geodesic
On bound of transfinite construction of inflationary fixed point
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2018), pp. 72-80 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider inflationary fixed point operators which are not computable in finitely many steps. In this case we prove that for any ordinal $\alpha\leq\omega^\omega$ there exists an IFP-operator converging exactly in $\alpha$ steps. For discrete order there exists an IFP-operator which can converge exactly in $\alpha$ steps for any ordinal $\alpha$.
Keywords: inflationary fixed point, discrete order, transfinite construction. 
@article{VTPMK_2018_3_a4,
     author = {S. M. Dudakov},
     title = {On bound of transfinite construction of inflationary fixed point},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {72--80},
     year = {2018},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2018_3_a4/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On bound of transfinite construction of inflationary fixed point
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2018
SP  - 72
EP  - 80
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2018_3_a4/
LA  - ru
ID  - VTPMK_2018_3_a4
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On bound of transfinite construction of inflationary fixed point
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2018
%P 72-80
%N 3
%U http://geodesic.mathdoc.fr/item/VTPMK_2018_3_a4/
%G ru
%F VTPMK_2018_3_a4
S. M. Dudakov. On bound of transfinite construction of inflationary fixed point. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2018), pp. 72-80. http://geodesic.mathdoc.fr/item/VTPMK_2018_3_a4/

[1] Aho A. V., Ullman J. D., “Universality of data retrieval languages”, Proc. of 6th Symp. on Principles of Programming Languages, 1979, 110–120 | MR

[2] Benedikt M., Dong G., Libkin L., Wong L., “Relational expressive power of constraint query languages”, Proc. 15th ACM Symp. on Principles of Database Systems, 1996, 5–16 | MR

[3] Chandra A., Harel D., “Computable queries for relational databases”, Journal of Computer and System Sciences, 21:2 (1980), 156–178 | DOI | MR | Zbl

[4] Codd E. F., “A relational model for large shared data banks”, Communications of the ACM, 13 (1970), 377–387 | DOI | Zbl

[5] Codd E. F., “Relational completeness of data base sublanguages”, Database Systems, ed. R. Rustin, Prentice-Hall, 1972, 33–64

[6] Dudakov S. M., “On safety of recursive queries”, Herald of Tver State University. Series: Applied Mathematics, 2012, no. 4 (27), 71–80 (in Russian)

[7] Dudakov S. M., “On safety of IFP-operators and recursive queries”, Herald of Tver State University. Series: Applied Mathematics, 2013, no. 2 (29), 5–13 (in Russian)

[8] Dudakov S. M., “Strong minimality and IFP-safety”, Herald of Tver State University. Series: Applied Mathematics, 2015, no. 3, 25–32 (in Russian)

[9] Dudakov S. M., “On inflationary fix-point operators safety”, Lobachevskii Journal of Mathematics, 36:4 (2015), 328–331 | DOI | MR | Zbl

[10] Dudakov S. M., “Iterative operators in classic theories”, Proceedings of Conference Algebra and Algorithm Theory (Ivanovo, 2018), IvSU Publ., Ivanono, 145–147 (in Russian)

[11] Dudakov S. M., Taitslin M. A., “Collapse results for query languages in database theory”, Russian Mathematical Surveys, 61:2 (2006), 195–253 | DOI | DOI | MR | Zbl

[12] Gurevich Y., Shelah S., “Fixed-point extensions of first-order logic”, Annals of Pure and Applied Logic, 1986, no. 32, 265–280 | DOI | MR | Zbl

[13] Kanellakis P., Kuper G., Revesz P., “Constraint query languages”, Journal of Computer and System Sciences, 51 (1995), 26–52 | DOI | MR

[14] Marker D., Model theory: an introduction, Springer-Verlag, New York, 2002, 342 pp. | MR | Zbl