Published November 18, 2019
| Version v1
Publication
Beyond Generalized Multiplicities: Register Machines over Groups
Contributors
Description
Register machines are a classic model of computing, often seen as a canonical
example of a device manipulating natural numbers. In this paper, we de ne register
machines operating on general groups instead. This generalization follows the research
direction started in multiple previous works. We study the expressive power of register
machines as a function of the underlying groups, as well as of allowed ingredients (zero
test, partial blindness, forbidden regions). We put forward a fundamental connection
between register machines and vector addition systems. Finally, we show how registers
over free groups can be used to store and manipulate strings.
Additional details
Identifiers
- URL
- https://idus.us.es/handle//11441/90263
- URN
- urn:oai:idus.us.es:11441/90263