We study the classes of B?chi and Rabin automatic structures. For??B?chi (Rabin) automatic structures their domains consist of??infinite strings (trees), and the basic relations, including the equality relation, and graphs??of operations are recognized by??B?chi (Rabin) automata. A?????B?chi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata-theoretic content of the well-known L?wenheim-Skolem theorem in model theory. We provide??automata-theoretic versions of L?wenheim-Skolem theorem for Rabin and B?chi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every B?chi automatic structure have an injective B?chi presentation? Does every Rabin automatic structure have an injective Rabin presentation???We provide examples of B?chi structures without injective B?chi and Rabin presentations. To answer these questions we introduce Borel structures and usesome of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for B?chi automatic structures.