Academic Journal
The Identity Problem in ℤ ≀ ℤ Is Decidable
| العنوان: | The Identity Problem in ℤ ≀ ℤ Is Decidable |
|---|---|
| المؤلفون: | Dong, Ruiwen |
| المساهمون: | Ruiwen Dong |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2023 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | wreath product, algorithmic group theory, identity problem, polynomial semiring, positive coefficients |
| الوصف: | We consider semigroup algorithmic problems in the wreath product ℤ ≀ ℤ. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain the neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of ℤ ≀ ℤ. We show that both problems are decidable. Our result complements the undecidability of the Semigroup Membership Problem (does a semigroup contain a given element?) in ℤ ≀ ℤ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.124 |
| DOI: | 10.4230/LIPIcs.ICALP.2023.124 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.ICALP.2023.124 https://nbn-resolving.org/urn:nbn:de:0030-drops-181768 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.124 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.3C56BD86 |
| قاعدة البيانات: | BASE |
كن أول من يترك تعليقا!