On P-transitive graphs and applications

Details On P-transitive graphs and applications On P-transitive graphs and applications

2011-06-07

arxiv.org/abs/1106.1243v1

EPTCS 54, 2011, pp. 222-236

Computer Science

Logic in Computer Science

In Proceedings GandALF 2011, arXiv:1106.0814

Scientific paper

10.4204/EPTCS.54.16

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.

Affiliated with

Also associated with

No associations

Rating

On P-transitive graphs and applications 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 On P-transitive graphs and applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On P-transitive graphs and applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26178