The Identity Correspondence Problem and its Applications

Details The Identity Correspondence Problem and its Applications The Identity Correspondence Problem and its Applications

2009-02-11

arxiv.org/abs/0902.1975v3

P. C. Bell, I. Potapov, On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix

Mathematics

Group Theory

We have made some proofs clearer and fixed an important typo from the published journal version of this article, see footnote

Scientific paper

10.1142/10.1142/S012905411000766

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of square integral matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several question for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words.

Affiliated with

Also associated with

No associations

Rating

The Identity Correspondence Problem and its Applications 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 The Identity Correspondence Problem and its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Identity Correspondence Problem and its Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555636