On the Myhill-Nerode Theorem for Trees
Abstract
This result generalizes in a straightforward way to automata on finite trees. I rediscovered this generalization in connection with work on finitely presented algebras, and stated it without proof or attribution in [7, 8], being at that time under the impression that it was folklore and completely elementary. It was again rediscovered independently by Z. Fulop and S. Vagvolgyi and reported in a recent contribution to this Bulletin. In that paper they attribute the result to me.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1992
- Accession Number
- AD1007848
Entities
People
- Dexter Kozen
Organizations
- Cornell University