Automatic and polynomial-time algebraic structures

• Main Authors: Bazhenov, Nikolay, Harrison-Trainor, Matthew, Kalimullin, Iskander, Melnikov, Alexander, Ng, Keng Meng
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2020
• Subjects: Science::Mathematics; Automatic Structures; Classification
• Online Access: https://hdl.handle.net/10356/145007
• Institution: Nanyang Technological University

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 aske...