Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

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

Mikołaj Bojańczyk1 and Luc Segoufin2

(1)  Warsaw University,  
(2)  INRIA - LSV,  
Abstract
We study tree languages that can be defined in Δ 2. These are tree languages definable by a first-order formula whose quantifier prefix is $\exists^*\forall^*$ , and simultaneously by a first-order formula whose quantifier prefix is $\forall^*\exists^*$ , both formulas over the signature with the descendant relation. We provide an effective characterization of tree languages definable in Δ 2. This characterization is in terms of algebraic equations. Over words, the class of word languages definable in Δ 2 forms a robust class, which was given an effective algebraic characterization by Pin and Weil [11].
Work partially funded by the AutoMathA programme of the ESF, the PHC programme Polonium, and by the Polish government grant no. N206 008 32/0810.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)