The Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs is Infinite

Ly Olivier

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


Here we deal with the question of definability of infinite graphs up to isomorphism by weak monadic second-order formulae. In this respect, we prove that the quantifier alternation hierarchy of equational graphs is infinite. Two proofs are given: the first one is based on the Ehrenfeucht-Fraissť games; the second one uses the arithmetical hierarchy. Finally we give a new proof of the Thomas's result according to which the hierarchy of the weak monadic second-order logic of the complete binary tree is infinite.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems