Knapsack problem for automaton groups

Abstract : 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.
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01373796
Contributeur : Thibault Godin <>
Soumis le : jeudi 29 septembre 2016 - 11:35:01
Dernière modification le : jeudi 11 janvier 2018 - 06:27:39
Document(s) archivé(s) le : vendredi 30 décembre 2016 - 12:45:44

Fichiers

knapsack_arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Thibault Godin. Knapsack problem for automaton groups. 2016. 〈hal-01373796〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

57