Geodesic
On undecidability of unary non-nested PFP-operators for one successor function theory
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2024), pp. 89-93 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate the decidability of first-order logic extensions. For example, it is established in A. S. Zolotov's works that a logic with a unary transitive closure operator for the one successor theory is decidable. We show that in a similar case, a logic with a unary partial fixed point operator is undecidable. For this purpose, we reduce the halting problem for the counter machine to the problem of truth of the underlying formula. This reduction uses only one unary non-nested partial fixed operator that is applied to a universal or existential formula.
Keywords: first-order logic, partial fixed point, undecidability. 
@article{IVM_2024_4_a8,
     author = {V. S. Sekorin},
     title = {On undecidability of unary non-nested {PFP-operators} for one successor function theory},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {89--93},
     year = {2024},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2024_4_a8/}
}
TY  - JOUR
AU  - V. S. Sekorin
TI  - On undecidability of unary non-nested PFP-operators for one successor function theory
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2024
SP  - 89
EP  - 93
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IVM_2024_4_a8/
LA  - ru
ID  - IVM_2024_4_a8
ER  - 
%0 Journal Article
%A V. S. Sekorin
%T On undecidability of unary non-nested PFP-operators for one successor function theory
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2024
%P 89-93
%N 4
%U http://geodesic.mathdoc.fr/item/IVM_2024_4_a8/
%G ru
%F IVM_2024_4_a8
V. S. Sekorin. On undecidability of unary non-nested PFP-operators for one successor function theory. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2024), pp. 89-93. http://geodesic.mathdoc.fr/item/IVM_2024_4_a8/

[1] Aho A., Ulman J.D., “Universality of data retrieval languages”, Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages POPL '79, 1979, 110–119 | DOI | MR

[2] Gurevich Y., Shelah S., “Fixed-point extensions of first-order logic”, Ann. Pure and Appl. Logic, 32 (1986), 265–280 | DOI | MR

[3] Dudakov S.M., Taitslin M. A., “Collapse results for query languages in database theory”, UMN, 61:2 (2006 \month 01), 3–66 | DOI | MR

[4] Zolotov A.S., “On decidability of the theory with the transitive closure operator”, Lobachevskii J. Math., 36:4 (2015), 434–440 | DOI | MR

[5] Sekorin V.S., “Ob ekvivalentnosti dvukh semantik PFP-operatora”, Vestn. Tversk. gos. un-ta. Ser. Prikl. matem., 2020, no. 3, 41–49

[6] Dudakov S.M., “On Safety of Unary and Nonunary IFP Operators”, Automatic Control and Computer Sci., 53 (2019), 683–688 | DOI

[7] Minsky M.L., Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1967 | MR