Geodesic
On equivalence of two PFP-operator semantics
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2020), pp. 41-49 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider two different semantics of partial fixed point (PFP) operator. We establish that they are equivalent for structures those contain more than one element. For this purpose we show how to translate each type of PFP-operator to other one.
Keywords: partial fixed point, infinite structure, semantic. 
@article{VTPMK_2020_3_a3,
     author = {V. S. Sekorin},
     title = {On equivalence of two {PFP-operator} semantics},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {41--49},
     year = {2020},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2020_3_a3/}
}
TY  - JOUR
AU  - V. S. Sekorin
TI  - On equivalence of two PFP-operator semantics
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2020
SP  - 41
EP  - 49
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2020_3_a3/
LA  - ru
ID  - VTPMK_2020_3_a3
ER  - 
%0 Journal Article
%A V. S. Sekorin
%T On equivalence of two PFP-operator semantics
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2020
%P 41-49
%N 3
%U http://geodesic.mathdoc.fr/item/VTPMK_2020_3_a3/
%G ru
%F VTPMK_2020_3_a3
V. S. Sekorin. On equivalence of two PFP-operator semantics. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2020), pp. 41-49. http://geodesic.mathdoc.fr/item/VTPMK_2020_3_a3/

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

[3] Gurevich Y., “Toward logic tailored for computational complexity”, Computation and Proof Theory, v. 1104, Lecture Notes in Mathematics, Springer, 1984, 175–216 | DOI | MR

[4] 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

[5] Kreutzer S., “Partial Fixed-Point Logic on Infinite Structure”, Computer Science Logic, 2002, 337–351 | DOI | MR | Zbl

[6] Libkin L., Elements of Finite Model Theory, Springer, Berlin, 2004, 314 pp. | MR | Zbl

[7] Sekorin V. S., “Partial Fixed Point for Finite Models in Second Order Logic”, Lobachevskii Journal of Mathematics, 41:9 (2020), 1672–1679 | DOI | MR | Zbl

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

[9] Dudakov S. M., “About the security of single-and multi-seat IFP operators”, Modeling and analysis of information systems, 25:5 (2018), 525–533 (in Russian) | MR