Automatic and polynomial-time algebraic structures
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145007 |
| _version_ | 1826128972780404736 |
|---|---|
| author | Bazhenov, Nikolay Harrison-Trainor, Matthew Kalimullin, Iskander Melnikov, Alexander Ng, Keng Meng |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Bazhenov, Nikolay Harrison-Trainor, Matthew Kalimullin, Iskander Melnikov, Alexander Ng, Keng Meng |
| author_sort | Bazhenov, Nikolay |
| collection | NTU |
| description | 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 -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. |
| first_indexed | 2024-10-01T07:33:15Z |
| format | Journal Article |
| id | ntu-10356/145007 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:33:15Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1450072023-02-28T19:54:27Z Automatic and polynomial-time algebraic structures Bazhenov, Nikolay Harrison-Trainor, Matthew Kalimullin, Iskander Melnikov, Alexander Ng, Keng Meng School of Physical and Mathematical Sciences Science::Mathematics Automatic Structures Classification 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 -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. Ministry of Education (MOE) Published version N. Bazhenov is supported by Russian Science Foundation, project No. 18-11-00028. M. Harrison-Trainor is supported by an NSERC Banting fellowship. The research of I. Kalimullin was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project No. 1.1515.2017/4.6. Also I. Kalimullin is funded by the Russian Ministry of Education and Science (project No. 1.451.2016/1.4) as the federal professor in mathematics. A. Melnikov was supported by Massey University Research Fund and Marsden Fund of New Zealand. K. M. Ng is partially supported by grant MOE2015-T2-2-055. 2020-12-08T07:03:57Z 2020-12-08T07:03:57Z 2019 Journal Article Bazhenov, N., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., & Ng, K. M. (2019). Automatic and polynomial-time algebraic structures. The Journal of Symbolic Logic, 84(4), 1630-1669. doi:10.1017/jsl.2019.26 0022-4812 https://hdl.handle.net/10356/145007 10.1017/jsl.2019.26 4 84 1630 1669 en MOE2015-T2-2-055 The Journal of Symbolic Logic © 2019 Association for Symbolic Logic. All rights reserved. This paper was published in The Journal of Symbolic Logic and is made available with permission of Association for Symbolic Logic. application/pdf |
| spellingShingle | Science::Mathematics Automatic Structures Classification Bazhenov, Nikolay Harrison-Trainor, Matthew Kalimullin, Iskander Melnikov, Alexander Ng, Keng Meng Automatic and polynomial-time algebraic structures |
| title | Automatic and polynomial-time algebraic structures |
| title_full | Automatic and polynomial-time algebraic structures |
| title_fullStr | Automatic and polynomial-time algebraic structures |
| title_full_unstemmed | Automatic and polynomial-time algebraic structures |
| title_short | Automatic and polynomial-time algebraic structures |
| title_sort | automatic and polynomial time algebraic structures |
| topic | Science::Mathematics Automatic Structures Classification |
| url | https://hdl.handle.net/10356/145007 |
| work_keys_str_mv | AT bazhenovnikolay automaticandpolynomialtimealgebraicstructures AT harrisontrainormatthew automaticandpolynomialtimealgebraicstructures AT kalimulliniskander automaticandpolynomialtimealgebraicstructures AT melnikovalexander automaticandpolynomialtimealgebraicstructures AT ngkengmeng automaticandpolynomialtimealgebraicstructures |