Knapsack problem for automaton groups - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2016

Knapsack problem for automaton groups

Résumé

The knapsack problem is a classic optimisation problem that has been recently extended in the setting of groups. Its study reveals to be interesting since it provides many different behaviours, depending on the considered class of groups. In this paper we deal with groups generated by Mealy automata—a class that is often used to study group-theoretical conjectures—and prove that the knapsack problem is undecidable for this class. In a second time, we construct a graph that, if finite, provides a solution to the knapsack problem. We deduce that the knapsack problem is decidable for the so-called bounded automaton groups, a class where the order and conjugacy problems are already known to be decidable.
Fichier principal
Vignette du fichier
knapsack_arxiv.pdf (215.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01373796 , version 1 (29-09-2016)

Identifiants

Citer

Thibault Godin. Knapsack problem for automaton groups. 2016. ⟨hal-01373796⟩
129 Consultations
180 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More