Regularity for a Large Class of COntext-Free processes is Decidable

摘要

Regularity fo context-free processes has been proved to be decidable for BPA systems by [MM94] and normed context-free processes by [Kru95]. iN this paper the decidable class of regular context-free processes is enlarged to that of context-free processes over so-called NRD specifications. Furthermore an upper bound is given for the number of states modulo bisimulation.