Abstract
假設A是一個存有n個名字的陣列。在A中的名字有些會重複出現。陣列A中不一樣的名字假設共有k個，重新命名問題（renaming problem）就是要找出這k個不同的名字，並為每一個名字指字一個1~k中的唯一編號。這個問題在現實生活中，有許多實際的應用。 在這篇論文中，我將在CRCW-PRAM上提出四個平行演算法來解決renaming problem。第一個平行演算法在CRCW-PRAM上使用了n1+ε個processor和O(log k)的時間。其中ε是任何一個介於0到1之間的常數。這個結果在processor個數上改進了Farach和Muthukishnan在過去所發表的結果。第二個平行演算法只用了n個processor和O(log k)的時間，不過它假設輸入的n個names都是介於0~n-1之間的常數。第三個平行演算法是第二個的延伸，它將輸入整數資料的範圍擴充到由0到nc-1，其中c為任一個正整數並且為一個固定的常數。這個演算法和第二個演算法用了相同的processor個數和時間。最後一個平行演算法如同第一個演算法不做任何假設，它只用了n個processor，其平均執行時間（average running time）為O(log k)。另外，在本篇論文中我將證明在EREW-PRAM和CREW-PRAM上，renaming problem 的 time lower bound 為O(log n)。