An analogue of the Myhill-Nerode theorem and its use in computingfinite-basis characterizations

摘要

A theorem that is a graph-theoretic analog of the Myhill-Nerodecharacterization of regular languages is proved. The theorem is used toestablish that for many applications obstruction sets are computable byknown algorithms. The focus is exclusively on what is computable (by aknown algorithm) in principle, as opposed to what is computable inpractice