Accession Number:

AD1007848

Title:

On the Myhill-Nerode Theorem for Trees

Descriptive Note:

Technical Report

Corporate Author:

CORNELL UNIV ITHACA NY ITHACA United States

Personal Author(s):

Report Date:

1992-06-01

Pagination or Media Count:

6.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE