Automatic Structures — Recent Results and Open Questions

[摘要] 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?

[发布机构] 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