Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity. A classical theorem of Courcelle states that any graph property defina...

Description complète

Détails bibliographiques

Auteurs principaux:	Dušan Knop, Martin Koutecký, Tomáš Masařík, Tomáš Toufar
Format:	Artigo
Langue:	Inglês
Publié:	Logical Methods in Computer Science e.V. 2019-12-01
Collection:	Logical Methods in Computer Science
Sujets:	computer science - computational complexity computer science - logic in computer science f.2.2, g.2.2 f.2.2 g.2.2
Accès en ligne:	https://lmcs.episciences.org/5017/pdf
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!