Journal of Symbolic Logic 84 (4):1630-1669 (2019)

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 ${\rm{\Sigma }}_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 No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2019.26
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,130
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Punctual Definability on Structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.
Categorical Linearly Ordered Structures.Rod Downey, Alexander Melnikov & Keng Meng Ng - 2019 - Annals of Pure and Applied Logic 170 (10):1243-1255.

Add more citations

Similar books and articles

Polynomial-Time Versus Recursive Models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Polynomial-Time Abelian Groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Automatic Structures of Bounded Degree Revisited.Dietrich Kuske & Markus Lohrey - 2011 - Journal of Symbolic Logic 76 (4):1352-1380.
Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Choiceless Polynomial Time.Andreas Blass, Yuri Gurevich & Saharon Shelah - 1999 - Annals of Pure and Applied Logic 100 (1-3):141-187.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.


Added to PP index

Total views
14 ( #732,010 of 2,506,503 )

Recent downloads (6 months)
1 ( #416,791 of 2,506,503 )

How can I increase my downloads?


My notes