Некоторые проблемы разрешимости и выразимости для предиката делимости на два последовательных числа
Аннотация
Предикат делимости на два последовательных числа DW(x,y) ÷ x | y ∧ 1+x | y был предложен Л. ван ден Дрисом и А. Уилки в работе, посвященной изучению свойств подмножеств натуральных чисел, экзистенциально выразимых с помощью единицы, сложения и делимости. В настоящей работе доказывается неразрешимость множества истинных в натуральных числах экзистенциальных формул, записанных с помощью только DW и умножения, а также выразимость всех арифметических предикатов с помощью только сложения и DW или только DW и делимости. Кроме того, получены некоторые результаты о выразимости для DW и отношения порядка.
Литература
Бельтюков А. П. Разрешимость универсальной теории натуральных чисел со сложением и делимостью // Записки научных семинаров ЛОМИ. 1975. Т. 60. С. 15–28.
Lipshitz L. The Diophantine problem for addition and divisibility // Transactions of the American Mathematical Society. 1976. Vol. 235. P. 271–283. doi:10.2307/1998219
Lipshitz L. Some remarks on the Diophantine problem for addition and divisibility // Bull. Soc. Math. Belg. Ser. B. 1981. Vol. 33, no. 1. P. 41–52.
Lechner A., Ouaknine J., Worrell J. On the Complexity of Linear Arithmetic with Divisibility // Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science(LICS). 2015.
P. 667–676. doi:10.1109/LICS.2015.67
Haase C. On the complexity of model checking counter automata. Ph.D. Thesis. University of Oxford.
Bundala D., Ouaknine J. On parametric timed automata and one-counter machines // Information and
Computation. 2017. Vol. 253. P. 272–303. doi:10.1016/j.ic.2016.07.011
Van den Dries L., Wilkie A.J. The laws of integer divisibility, and solution sets of linear divisibility
conditions // The Journal of Symbolic Logic. 2003. Vol. 68, no. 2. P. 503–526. doi:10.2178/jsl/1052669061
Starchak M. R., Kosovskii N. K., Kosovskaya T. M. Some NP-Hard Problems for the Simultaneous
Coprimeness of Values of Linear Polynomials // Global Journal of Computer Science and Technology.
Vol. 17, no. 4. P. 21–25.
Korec I. A list of arithmetical structures complete with respect to the first-order definability //
Theoretical Computer Science. 2001. Vol. 257, no. 1–2. P. 115–151. doi:10.1016/S0304-3975(00)00113-4
Richard D. What are Weak Arithmetics? // Theoretical Computer Science. 2001. Vol. 257. P. 17–29.
Robinson J. Definability and decision problems in arithmetic // The Journal of Symbolic Logic. 1949.
Vol. 14. P. 98–114. doi:10.2307/2266510
Mostowski A. On direct products of theories // The Journal of Symbolic Logic. 1952. Vol. 17, no. 1.
P. 1–31. doi:10.2307/2267454
Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191, № 2.
С. 278–282.
Матиясевич Ю. В. Десятая проблема Гильберта. М.: Физматлит. 1993.
Carmichael L. C. On the numerical factors of the arithmetic forms αn ±βn// Ann. Math. 1913. Vol. 15,
no. 2. P. 30–69. doi:10.2307/1967798
Woods A. Some problems in logic and number theory. PhD Thesis. University of Manchester. 1981.
Richard D. All arithmetical sets of powers of primes are first-order definable in terms of the
successor function and the coprimeness predicate // Discrete Mathematics. 1985. Vol. 53. P. 221–247.
doi:10.1016/0012-365X(85)90144-X
Lipshitz L. Quadratic forms, the five square problem, and diophantine equations // The collected
works of J. Richard Buchi (S. MacLane and Dirk Siefkes, eds.). Springer. 1990. P. 677 ¨ –680.
Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки научных семинаров ЛОМИ. 1974. Т. 40. С. 24–29.
Материал публикуется под лицензией:
