Algebraic characterization of logically defined tree languages Esik, Zoltan; Weil, Pascal

User activity

Share to:
View the summary of this work
Esik, Zoltan ; Weil, Pascal
Appears In
International Journal of Algebra and Computation
f.4.3; computer science - logic in computer science; f.4.1
To access, purchase, authenticate, or subscribe to the full-text of this article, please visit this link: Byline: ZOLTAN ESIK, PASCAL WEIL We give an algebraic characterization of the tree languages that are defined by logical formulas using certain Lindstrom 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.
Work ID

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users