Standard

Automatic and Polynomial-Time Algebraic Structures. / Bazhenov, Nikolay; Harrison-Trainor, Matthew; Kalimullin, Iskander et al.

In: Journal of Symbolic Logic, Vol. 84, No. 4, 01.12.2019, p. 1630-1669.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, N, Harrison-Trainor, M, Kalimullin, I, Melnikov, A & Ng, KM 2019, 'Automatic and Polynomial-Time Algebraic Structures', Journal of Symbolic Logic, vol. 84, no. 4, pp. 1630-1669. https://doi.org/10.1017/jsl.2019.26

APA

Bazhenov, N., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., & Ng, K. M. (2019). Automatic and Polynomial-Time Algebraic Structures. Journal of Symbolic Logic, 84(4), 1630-1669. https://doi.org/10.1017/jsl.2019.26

Vancouver

Bazhenov N, Harrison-Trainor M, Kalimullin I, Melnikov A, Ng KM. Automatic and Polynomial-Time Algebraic Structures. Journal of Symbolic Logic. 2019 Dec 1;84(4):1630-1669. doi: 10.1017/jsl.2019.26

Author

Bazhenov, Nikolay ; Harrison-Trainor, Matthew ; Kalimullin, Iskander et al. / Automatic and Polynomial-Time Algebraic Structures. In: Journal of Symbolic Logic. 2019 ; Vol. 84, No. 4. pp. 1630-1669.

BibTeX

@article{821c3d18b0e945ea804363a02256b5b7,
title = "Automatic and Polynomial-Time Algebraic Structures",
abstract = "A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is Σ 1 1-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel. ",
keywords = "03D05, 03D45, 03D80, 2010 Mathematics Subject Classification, 68Q45, Primary 03C57, Secondary 03D20, INDEX SETS, FREE ABELIAN-GROUPS, classification, index sets, automatic structures, COMPLEXITY",
author = "Nikolay Bazhenov and Matthew Harrison-Trainor and Iskander Kalimullin and Alexander Melnikov and Ng, {Keng Meng}",
year = "2019",
month = dec,
day = "1",
doi = "10.1017/jsl.2019.26",
language = "English",
volume = "84",
pages = "1630--1669",
journal = "Journal of Symbolic Logic",
issn = "0022-4812",
publisher = "Cambridge University Press",
number = "4",

}

RIS

TY - JOUR

T1 - Automatic and Polynomial-Time Algebraic Structures

AU - Bazhenov, Nikolay

AU - Harrison-Trainor, Matthew

AU - Kalimullin, Iskander

AU - Melnikov, Alexander

AU - Ng, Keng Meng

PY - 2019/12/1

Y1 - 2019/12/1

N2 - A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is Σ 1 1-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

AB - A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is Σ 1 1-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

KW - 03D05

KW - 03D45

KW - 03D80

KW - 2010 Mathematics Subject Classification

KW - 68Q45

KW - Primary 03C57

KW - Secondary 03D20

KW - INDEX SETS

KW - FREE ABELIAN-GROUPS

KW - classification

KW - index sets

KW - automatic structures

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85077331669&partnerID=8YFLogxK

U2 - 10.1017/jsl.2019.26

DO - 10.1017/jsl.2019.26

M3 - Article

AN - SCOPUS:85077331669

VL - 84

SP - 1630

EP - 1669

JO - Journal of Symbolic Logic

JF - Journal of Symbolic Logic

SN - 0022-4812

IS - 4

ER -

ID: 22998175