On P-transitive graphs and applications

Giacomo Lenzi
(University of Salerno)

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.

In Giovanna D'Agostino and Salvatore La Torre: Proceedings Second International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2011), Minori, Italy, 15-17th June 2011, Electronic Proceedings in Theoretical Computer Science 54, pp. 222–236.
Published: 4th June 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.54.16 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org