RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1974 Volume 40, Pages 24–29 (Mi znsl2678)

This article is cited in 1 paper

On solutions of systems consisting both of word equationa and of word length inequalities

N. K. Kossovski


Abstract: It is proved that systems named in the title are undecidable. Moreover some undecidable set $M$ can be represented in the form $a\in M\Leftrightarrow\exists x_1\dots x_n P$ where $P$ is a system of the above mentioned form. However some recursive set cannot be represented in this form.

UDC: 51.01+518.5



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024