Presentation
Beyond Generalized Multiplicities: Register Machines over Groups
Author/s | Alhazov, Artiom
Freund, Rudolf Ivanov, Sergiu |
Editor | Research Group on Natural Computing |
Publication Date | 2019 |
Deposit Date | 2019-11-18 |
Published in |
|
Abstract | 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 ... 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. |
Citation | Alhazov, A., Freund, R. y Ivanov, S. (2019). Beyond Generalized Multiplicities: Register Machines over Groups. En BWMC 2019: Seventeenth Brainstorming Week on Membrane Computing (1-28), Sevilla, España: Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
001_Mgroups.pdf | 325.5Kb | [PDF] | View/ | |