Bibliographic Details
| Title: |
Algebraic recognizability of regular tree languages |
| Authors: |
Ésik, Zoltán1,2 ze@inf.u-szeged.hu, Weil, Pascal3 pascal.weil@labri.fr |
| Source: |
Theoretical Computer Science. Jun2005, Vol. 340 Issue 2, p291-321. 31p. |
| Subjects: |
Computer programming, Algebra, Mathematical analysis, Robots |
| Abstract: |
Abstract: We propose a new algebraic framework to discuss and classify recognizable tree languages, and to characterize interesting classes of such languages. Our algebraic tool, called preclones, encompasses the classical notion of syntactic -algebra or minimal tree automaton, but adds new expressivity to it. The main result in this paper is a variety theorem à la Eilenberg, but we also discuss important examples of logically defined classes of recognizable tree languages, whose characterization and decidability was established in recent papers (by Benedikt and Ségoufin, and by Bojańczyk and Walukiewicz) and can be naturally formulated in terms of pseudovarieties of preclones. Finally, this paper constitutes the foundation for another paper by the same authors, where first-order definable tree languages receive an algebraic characterization. [Copyright &y& Elsevier] |
|
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
