Geodesic
On expressive power of monadic transitive close logic over discrete order
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 25-33 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We establish that the monadic transitive close operator over linear discrete order allows to express addition, multiplication and exponential function up to $H_2(n)$. Here $n$ is formulas length and $H_2(n)$ is the hyperexponential function.
Keywords: transitive close logic, linerar discrete order, expressive power. 
@article{VTPMK_2017_4_a1,
     author = {S. M. Dudakov},
     title = {On expressive power of monadic transitive close logic over discrete order},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {25--33},
     year = {2017},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a1/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On expressive power of monadic transitive close logic over discrete order
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2017
SP  - 25
EP  - 33
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a1/
LA  - ru
ID  - VTPMK_2017_4_a1
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On expressive power of monadic transitive close logic over discrete order
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2017
%P 25-33
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a1/
%G ru
%F VTPMK_2017_4_a1
S. M. Dudakov. On expressive power of monadic transitive close logic over discrete order. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 25-33. http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a1/

[1] Bulos D., Dzheffri R., Computability and Logic, ed. S. N. Artemov, Mir Publ., Moscow, 1994, 396 pp. (in Russian)

[2] Zolotov A. S., “The use of the transitive closure operator on formulas with a single successor function and divisibility predicates”, Vestnik TvGU. Seriya: Prikladnaya matematika [Herald of Tver State University. Series: Applied Mathematics], 2013, no. 1(28), 101-117 (in Russian)

[3] Zolotov A. S., “On undecidability of additive and multiplicative theories of natural numbers with the transitive closure operator”, Vestnik TvGU. Seriya: Prikladnaya matematika [Herald of Tver State University. Series: Applied Mathematics], 2014, no. 3, 117-125 (in Russian)

[4] Karatsuba A. A., Fundamentals of Analytic Number Theory, URSS, Moscow, 2004, 184 pp. (in Russian) | MR

[5] Fagin R., “Monadic generalized spectra”, Zeitschrift fuer Mathematische Logik und Grundlagen der Mathematik, 1975, no. 21, 89-96 | DOI | MR | Zbl

[6] Fischer M. J., Rabin M. O., “Super-exponential complexity of Presburger arithmetic”, Proceedings of the SIAM-AMS Symposium in Applied Mathematics, 7 (1974), 27-41 | MR