Algebraic recognizability of regular tree languages

Details Algebraic recognizability of regular tree languages Algebraic recognizability of regular tree languages

2006-09-20

arxiv.org/abs/cs/0609113v1

Theoretical Computer Science 340 (2005) 291-321

Computer Science

Discrete Mathematics

Scientific paper

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 Sigma-algebra or minimal tree automaton, but adds new expressivity to it. The main result in this paper is a variety theorem \`{a} 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\'{e}goufin, and by Bojanczyk 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.

Affiliated with

Also associated with

No associations

Rating

Algebraic recognizability of regular tree languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algebraic recognizability of regular tree languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic recognizability of regular tree languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350709