Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Details Tree Languages Defined in First-Order Logic with One Quantifier Alternation Tree Languages Defined in First-Order Logic with One Quantifier Alternation

2010-09-15

arxiv.org/abs/1009.2854v2

LMCS special issue for LICS 2008

Computer Science

Formal Languages and Automata Theory

Scientific paper

We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the descendant relation alone or together with the lexicographical order relation on nodes. We provide an effective characterization of tree and forest languages definable in \Delta_2 . This characterization is in terms of algebraic equations. Over words, the class of word languages definable in \Delta_2 forms a robust class, which was given an effective algebraic characterization by Pin and Weil.

Affiliated with

Also associated with

No associations

Rating

Tree Languages Defined in First-Order Logic with One Quantifier Alternation 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 Tree Languages Defined in First-Order Logic with One Quantifier Alternation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree Languages Defined in First-Order Logic with One Quantifier Alternation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-77003