Parallel complexity of the regular code problem

The regular code problem (RCP) seeks to decide whether a right linear grammar, G, generates a code, i. e. , whether or not (L(G))∗ is free over L(G). Here L(G) is the language generated by G. The regular free monoid problem (RFMP) seeks to decide whether a right linear grammar, G, generates a free monoid. Both problems can be reduced to the linear context free grammar emptiness problem, which in turn can be reduced to matrix inversion. In the case of RCP the reductions give rise to an NC algorithm. In the RFMP case the reduction yields only an EXPTIME algorithm.

Authors

• Bruce E. Litow

Keywords

No keywords are indexed for this paper.