Automatic structures and the theory of lists

Goncharov constructed the axiomatic theory of linear lists over the elements of a given data type. We study algorithmic complexity for models of this theory. We prove that the enriched list structure over a finite set of atoms is automatically presentable, and the enriched list structure over an infinite set of atoms has no automatic presentations.