Geodesic
Generic undecidability of universal theories
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1289-1294

Voir la notice de l'article provenant de la source Math-Net.Ru

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper we study generic complexity of undecidable universal theories. We prove that any undecidable universal theory remains generically undecidable (i.e. for almost all inputs).
Keywords: universal theory, generic complexity. 
@article{SEMR_2019_16_a21,
     author = {A. N. Rybalov},
     title = {Generic undecidability of universal theories},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1289--1294},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic undecidability of universal theories
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1289
EP  - 1294
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/
LA  - ru
ID  - SEMR_2019_16_a21
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic undecidability of universal theories
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1289-1294
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/
%G ru
%F SEMR_2019_16_a21
A. N. Rybalov. Generic undecidability of universal theories. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1289-1294. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/