Mathematics – Group Theory
Scientific paper
2011-06-06
Mathematics
Group Theory
A short version will appear in Proceedings of MFCS 2011
Scientific paper
The compressed word problem for a finitely generated monoid M asks whether two given compressed words over the generators of M represent the same element of M. For string compression, straight-line programs, i.e., context-free grammars that generate a single string, are used in this paper. It is shown that the compressed word problem for a free inverse monoid of finite rank at least two is complete for Pi^p_2 (second universal level of the polynomial time hierarchy). Moreover, it is shown that there exists a fixed finite idempotent presentation (i.e., a finite set of relations involving idempotents of a free inverse monoid), for which the corresponding quotient monoid has a PSPACE-complete compressed word problem. It was shown previously that the ordinary uncompressed word problem for such a quotient can be solved in logspace. Finally, a PSPACE-algorithm that checks whether a given element of a free inverse monoid belongs to a given rational subset is presented. This problem is also shown to be PSPACE-complete (even for a fixed finitely generated submonoid instead of a variable rational subset).
No associations
LandOfFree
Compressed word problems for inverse monoids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Compressed word problems for inverse monoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed word problems for inverse monoids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-389459