Algebraic characterization of logically defined tree languages

Details Algebraic characterization of logically defined tree languages Algebraic characterization of logically defined tree languages

2007-09-19

arxiv.org/abs/0709.2962v3

International Journal of Algebra and Computation 20 (2010) 195-239

Computer Science

Logic in Computer Science

46 pages. Version 3: various local improvements (more typos corrected, and "intuitive" explanations added)

Scientific paper

We give an algebraic characterization of the tree languages that are defined by logical formulas using certain Lindstr\"om quantifiers. An important instance of our result concerns first-order definable tree languages. Our characterization relies on the usage of preclones, an algebraic structure introduced by the authors in a previous paper, and of the block product operation on preclones. Our results generalize analogous results on finite word languages, but it must be noted that, as they stand, they do not yield an algorithm to decide whether a given regular tree language is first-order definable.

Affiliated with

Also associated with

No associations

Rating

Algebraic characterization of logically defined 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 characterization of logically defined tree languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic characterization of logically defined tree languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-336378