Logo image
Tessellation automata with group transformations
Technical documentation   Open access

Tessellation automata with group transformations

Thomas J. Ostrand and Elaine J. Weyuker
Rutgers University
1973
DOI:
https://doi.org/10.7282/t3-epwb-hr43

Abstract

A group tessellation automaton (TA) is one whose state alphabet consists of the elements of a group, and whose local transformation is defined in terms of the group's composition rule. If the domain and range of a group TA mapping are restricted to finite configurations, the mapping is one-to-one. On the set of all configurations (including infinite ones), group mappings are onto, but not one-to-one. Questions about the existence of predecessors and successors of configurations, are undecidable for general TA, are constructively solvable for group TA. It is shown that every finite configuration of an arbitrary group TA is self-reproducing. A method of calculating successive generations of abelian group TA configurations is presented, and then used to demonstrate a self-reproduction theorem for abelian group TA. The arithmetical numbers, a generalization of binomial coefficients, are used to derive this result.
pdf
DCS-TR-26498.37 kBDownloadView
Technical Documentation Open Access
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

41 File downloads
50 Record Views

Details

Logo image