Equivalent automatic structures and their boundaries

Walter D. Neumann, Michael Shapiro

Research output: Contribution to journalArticle

Abstract

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
Volume2
Issue number4
DOIs
Publication statusPublished - 1992

Cite this