English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Membership Problems in Finite Groups

Lohrey, M., Rosowski, A., & Zetzsche, G. (2022). Membership Problems in Finite Groups. In S. Szeider, R. Ganian, & A. Silva (Eds.), 47th International Symposium on Mathematical Foundations of Computer Science (pp. 1-16). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.MFCS.2022.71.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-000A-BC99-6 Version Permalink: https://hdl.handle.net/21.11116/0000-000B-33FA-2
Genre: Conference Paper

Files

show Files
hide Files
:
arXiv:2206.11756.pdf (Preprint), 327KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-000A-BC9B-4
Name:
arXiv:2206.11756.pdf
Description:
File downloaded from arXiv at 2022-07-19 11:25 A short version will appear in the proceedings of MFCS 2022
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://creativecommons.org/licenses/by/4.0/
:
LIPIcs-MFCS-2022-71.pdf (Publisher version), 765KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-000B-32E4-B
Name:
LIPIcs-MFCS-2022-71.pdf
Description:
-
OA-Status:
Gold
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
https://creativecommons.org/licenses/by/4.0/legalcode

Locators

show
hide
Locator:
https://drops.dagstuhl.de/opus/volltexte/2022/16869/ (Publisher version)
Description:
-
OA-Status:
Green

Creators

show
hide
 Creators:
Lohrey, Markus1, Author
Rosowski, Andreas1, Author
Zetzsche, Georg2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Group G. Zetzsche, Max Planck Institute for Software Systems, Max Planck Society, ou_3031905              

Content

show
hide
Free keywords: Mathematics, Group Theory, math.GR,Computer Science, Formal Languages and Automata Theory, cs.FL,
 Abstract: We show that the subset sum problem, the knapsack problem and the rational
subset membership problem for permutation groups are NP-complete. Concerning
the knapsack problem we obtain NP-completeness for every fixed $n \geq 3$,
where $n$ is the number of permutations in the knapsack equation. In other
words: membership in products of three cyclic permutation groups is
NP-complete. This sharpens a result of Luks, which states NP-completeness of
the membership problem for products of three abelian permutation groups. We
also consider the context-free membership problem in permutation groups and
prove that it is PSPACE-complete but NP-complete for a restricted class of
context-free grammars where acyclic derivation trees must have constant
Horton-Strahler number. Our upper bounds hold for black box groups. The results
for context-free membership problems in permutation groups yield new complexity
bounds for various intersection non-emptiness problems for DFAs and a single
context-free grammar.

Details

show
hide
Language(s): eng - English
 Dates: 2022-06-232022-06-282022
 Publication Status: Published online
 Pages: 22 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: URN: urn:nbn:de:0030-drops-168694
BibTex Citekey: LohreyMFCS22
DOI: 10.4230/LIPIcs.MFCS.2022.71
 Degree: -

Event

show
hide
Title: 47th International Symposium on Mathematical Foundations of Computer Science
Place of Event: Vienna, Austria
Start-/End Date: 2022-08-22 - 2022-08-26

Legal Case

show

Project information

show

Source 1

show
hide
Title: 47th International Symposium on Mathematical Foundations of Computer Science
  Abbreviation : MFCS 2022
  Subtitle : MFCS 2022, August 22–26, 2022, Vienna, Austria
Source Genre: Proceedings
 Creator(s):
Szeider, Stefan1, Editor
Ganian, Robert1, Editor
Silva, Alexandra1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Wadern : Schloss Dagstuhl
Pages: - Volume / Issue: - Sequence Number: 71 Start / End Page: 1 - 16 Identifier: ISBN: 978-3-95977-256-3

Source 2

show
hide
Title: Leibniz International Proceedings in Informatics
  Abbreviation : LIPIcs
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 241 Sequence Number: - Start / End Page: - Identifier: -