Beyond Generalized Multiplicities: Register Machines over Groups
Închide
Articolul precedent
Articolul urmator
243 0
SM ISO690:2012
ALHAZOV, Artiom, FREUND, Rudolf, IVANOV, Sergiu. Beyond Generalized Multiplicities: Register Machines over Groups. In: Brainstorming Week On Membrane Computing, 5-8 februarie 2019, Sevilla. Sevilla, Spania: Universidad de Sevilla, 2019, Ediția a 17-a, pp. 11-27.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Brainstorming Week On Membrane Computing
Ediția a 17-a, 2019
Masa rotundă "Seventeenth Brainstorming Week on Membrane Computing"
Sevilla, Spania, 5-8 februarie 2019

Beyond Generalized Multiplicities: Register Machines over Groups


Pag. 11-27

Alhazov Artiom1, Freund Rudolf2, Ivanov Sergiu34
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 Technical University of Vienna,
3 IBISC, Universite Evry,
4 Universitatea Paris-Saclay
 
Disponibil în IBN: 8 mai 2021


Rezumat

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.