DocumentCode
2242300
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
fYear
1989
fDate
30 Oct-1 Nov 1989
Firstpage
520
Lastpage
525
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location
Research Triangle Park, NC
Print_ISBN
0-8186-1982-1
Type
conf
DOI
10.1109/SFCS.1989.63528
Filename
63528
Link To Document