Automatic and Polynomial-Time Algebraic Structures

Nikolay Bazhenov, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov, Keng Meng Ng

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1630-1669
Number of pages40
JournalJournal of Symbolic Logic
Volume84
Issue number4
DOIs
Publication statusPublished - 1 Dec 2019

Keywords

  • 03D05
  • 03D45
  • 03D80
  • 2010 Mathematics Subject Classification
  • 68Q45
  • Primary 03C57
  • Secondary 03D20
  • INDEX SETS
  • FREE ABELIAN-GROUPS
  • classification
  • index sets
  • automatic structures
  • COMPLEXITY

OECD FOS+WOS

  • 1.01.QL LOGIC

Fingerprint

Dive into the research topics of 'Automatic and Polynomial-Time Algebraic Structures'. Together they form a unique fingerprint.

Cite this