Equivalent automatic structures and their boundaries

Walter D. Neumann, Michael Shapiro

Research output: Contribution to journalArticlepeer-review


Two (synchronous, asynchronous, or non-deterministic asynchronous) automatic structures on a group G are “equivalent” if their union is a non-deterministic asynchronous automatic structure. We discuss this relation, giving a classification of structures up to equivalence for abelian groups and partial results in some other cases. We also discuss a “boundary” of an asynchronous automatic structure. We show that it is an invariant of the equivalence class of the structure, and describe other properties. We describe a “rehabilitated boundary” which yields Sn−1 for any automatic structure on ℤn.
Original languageEnglish
Pages (from-to)443-469
Number of pages27
JournalInternational Journal of Algebra and Computation
Issue number4
Publication statusPublished - 1992


Dive into the research topics of 'Equivalent automatic structures and their boundaries'. Together they form a unique fingerprint.

Cite this