On the Diophantine problem related to power circuits Научная публикация
| Журнал |
Groups, Complexity, Cryptology
ISSN: 1867-1144 , E-ISSN: 1869-6104 |
||
|---|---|---|---|
| Вых. Данные | Год: 2026, Том: 18, Номер: 1, Номер статьи : 2, Страниц : 4 DOI: 10.46298/jgcc.2026.18.1.17270 | ||
| Ключевые слова | Diophantine problem, power circuit | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Российский научный фонд | 25-11-20023 |
Реферат:
Abstract. Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn function. Power circuits are computational structures that support addition and the operation (x,y) → x · 2y on integers. They also posed the question of decidability of the Diophantine problem over the structure ⟨N>0;+,x · 2y,≤,1⟩, which is closely related to power circuits. In this paper, we prove that the Diophantine problem over this structure is undecidable.
Библиографическая ссылка:
Rybalov A.
On the Diophantine problem related to power circuits
Groups, Complexity, Cryptology. 2026. V.18. N1. 2 :1-4. DOI: 10.46298/jgcc.2026.18.1.17270 Scopus OpenAlex
On the Diophantine problem related to power circuits
Groups, Complexity, Cryptology. 2026. V.18. N1. 2 :1-4. DOI: 10.46298/jgcc.2026.18.1.17270 Scopus OpenAlex
Даты:
| Поступила в редакцию: | 12 янв. 2026 г. |
| Принята к публикации: | 1 апр. 2026 г. |
| Опубликована в печати: | 2 апр. 2026 г. |
| Опубликована online: | 2 апр. 2026 г. |
Идентификаторы БД:
| ≡ Scopus: | 2-s2.0-105034837429 |
| ≡ OpenAlex: | W7147172997 |