Title :
An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations
Author :
Fellows, Michael R. ; Langston, Michael A.
Author_Institution :
Dept. of Comput. Sci., Idaho Univ., Moscow, ID, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
A theorem that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages is proved. The theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice
Keywords :
computability; graph theory; Myhill-Nerode characterization; computability; computing finite-basis characterizations; graph-theoretic analog; obstruction sets; regular languages; Analog computers; Argon; Computer science; Contracts; Doped fiber amplifiers; Polynomials; Resists;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63528
