Constant Time Simulation of an R-Mesh on an LR-Mesh

Recently, many parallel computing models using dynamically reconfigurable electrical buses have been proposed in the literature. The underlying characteristics are similar among these models, but they do have certain differences that can take form of restrictions on configurations allowed. This paper presents a constant time simulation of an R-mesh on an LR-mesh (a restricted model of the R-mesh), proving that in spite of the differences, the two models possess the same complexity. In other words, the LR-mesh can simulate a step of the R-mesh in constant time with a polynomial increase in size. This simulation is based on Rein-gold´s algorithm to solve USTCON in log-space. The simulation is also the first to be executed in constant time.