Винокуров Н. С.
Сложность некоторых естественных проблем в автоматных структурах

Доказано, что проблема автоматного изоморфизма автоматных структур, проблема существования нетривиального автоматного автоморфизма автоматной структуры, проблема автоматной вложимости автоматных структур Σ₁⁰-полны. Также показана Σ₁¹-полнота проблемы вложения автоматных структур.

Vinokurov N. S.
Complexity of some natural problems in automatic structures

We prove that the automatic isomorphism problem for automatic structures, the automatic automorphism problem for an automatic structure, and the automatic embedding problem for automatic structures are Σ₁⁰-complete. We also prove that the embedding problem for automatic structures is Σ₁¹-complete.

Полный текст статьи / Full texts:

• PDF file (422 KB)
• PostScript file (820 KB)