Automatic and polynomial-time algebraic structures

• المؤلفون الرئيسيون: Bazhenov, Nikolay, Harrison-Trainor, Matthew, Kalimullin, Iskander, Melnikov, Alexander, Ng, Keng Meng
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2020
• الموضوعات: Science::Mathematics; Automatic Structures; Classification
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/145007
• المؤسسة: 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...