That's correct only if the implementation was made without using the original implementation - for example, made off of a common specification, or using only the inputs and outputs of the application. (AKA, a "clean room" implementation)

If the reimplementation was made by perusing the original, it can be considered a derivative work subject to copyright.