2011/06/07 by Giacomo Lenzi
Computer Science · #cs.LO
paper · pdf · doi:10.4204/eptcs.54.16
published as EPTCS 54, 2011, pp. 222-236 · In Proceedings GandALF 2011, arXiv:1106.0814
arxiv created 2011/06/07 · arxiv updated 2011/06/08
We introduce a new class of graphs which we call P-transitive graphs, lying between transitive and 3-transitive graphs. First we show that the analogue of de Jongh-Sambin Theorem is false for wellfounded P-transitive graphs; then we show that the mu-calculus fixpoint hierarchy is infinite for P-transitive graphs. Both results contrast with the case of transitive graphs. We give also an undecidability result for an enriched mu-calculus on P-transitive graphs. Finally, we consider a polynomial time reduction from the model checking problem on arbitrary graphs to the model checking problem on P-transitive graphs. All these results carry over to 3-transitive graphs.