|
СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
АННОТАЦИИ
Винокуров Н. С. Сложность некоторых естественных проблем в автоматных структурах //
Том 46 (2005), Номер 1,
стр. 7178
Доказано, что проблема автоматного изоморфизма автоматных структур, проблема существования нетривиального автоматного автоморфизма автоматной структуры, проблема автоматной вложимости автоматных структур $\Sigma^0_1$-полны. Также показана $\Sigma_1^1$-полнота проблемы вложения автоматных структур.
|
|
© Сибирский Математический Журнал, 2003-2006
|
|