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

Equivalent automatic structures and their boundaries. / Neumann, Walter D.; Shapiro, Michael.

In: International Journal of Algebra and Computation, Vol. 2, No. 4, 1992, p. 443-469.

Research output: Contribution to journalArticle

Neumann, Walter D. ; Shapiro, Michael. / Equivalent automatic structures and their boundaries. In: International Journal of Algebra and Computation. 1992 ; Vol. 2, No. 4. pp. 443-469.
@article{66bd0c7bd31b42fc9eb13083205843b8,
title = "Equivalent automatic structures and their boundaries",
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.",
author = "Neumann, {Walter D.} and Michael Shapiro",
year = "1992",
doi = "10.1142/S021819679200027X",
language = "English",
volume = "2",
pages = "443--469",
journal = "International Journal of Algebra and Computation",
issn = "0218-1967",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "4",

}

TY - JOUR

T1 - Equivalent automatic structures and their boundaries

AU - Neumann, Walter D.

AU - Shapiro, Michael

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

U2 - 10.1142/S021819679200027X

DO - 10.1142/S021819679200027X

M3 - Article

VL - 2

SP - 443

EP - 469

JO - International Journal of Algebra and Computation

JF - International Journal of Algebra and Computation

SN - 0218-1967

IS - 4

ER -