|
Sibirskii Matematicheskii Zhurnal, 2005, Volume 46, Number 1, Pages 71–78
(Mi smj958)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Complexity of some natural problems in automatic structures
N. S. Vinokurov Novosibirsk State University, Mechanics and Mathematics Department
Abstract:
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 $\Sigma_1^0$-complete. We also prove that the embedding problem for automatic structures is $\Sigma_1^1$-complete.
Keywords:
finite automaton, automatic structures, isomorphism problem.
Received: 26.11.2003 Revised: 01.12.2004
Citation:
N. S. Vinokurov, “Complexity of some natural problems in automatic structures”, Sibirsk. Mat. Zh., 46:1 (2005), 71–78; Siberian Math. J., 46:1 (2005), 56–61
Linking options:
https://www.mathnet.ru/eng/smj958 https://www.mathnet.ru/eng/smj/v46/i1/p71
|
Statistics & downloads: |
Abstract page: | 252 | Full-text PDF : | 84 | References: | 54 |
|