Automatic Structures — Recent Results and Open Questions

3rd International Conference on Science & Engineering in Mathematics, Chemistry and Physics 2015

数学;化学;物理学

Stephan, Frank^1

Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore

119076, Singapore^1

关键词: Automatic structures;    First order;    Generalisation;    Isomorphism problems;    Linear time;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/622/1/012013/pdf
DOI  :  10.1088/1742-6596/622/1/012013

来源: IOP

【 摘 要 】

Regular languages are languages recognised by finite automata; automatic structures are a generalisation of regular languages where one also uses automatic relations (which are relations recognised by synchronous finite automata) and automatic functions (which are functions whose graph is an automatic relation). Functions and relations first-order definable from other automatic functions and relations are again automatic. Automatic functions coincide with the functions computed by position-faithful one-tape Turing machines in linear time. This survey addresses recent results and open questions on topics related to automatic structures: How difficult is the isomorphism problem for various types of automatic structures? Which groups are automatic? When are automatic groups Abelian or orderable? How can one overcome some of the limitations to represent rings and fields by weakening the automaticity requirements of a structure?