On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a nite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is...

Full description

Saved in:
Bibliographic Details
Main Authors: Paul Bell, Igor Potapov
Format: Default Article
Published: 2010
Subjects:
Other information and computing sciences not elsewhere classified
Combinatorics on Words
Group problem
Post's correspondence problem
Matrix semigroups
Undecidability
Information and Computing Sciences not elsewhere classified
Online Access:https://hdl.handle.net/2134/12042
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items