A polynomial algorithm testing partial confluence of basic semi-Thue systems
We give a polynomial algorithm solving the problem "is S partially confluent on the rational set R?" for finite, basic, noetherian semi-Thue systems. The algorithm is obtained by a polynomial reduction of this problem to the equivalence problem for deterministic 2-tape finite automata, which has been shown to be polynomially decidable in Friedman and Greibach (1982).
confluence semi-thue systems two-tape finite automata