Parameterized Complexity Of Representing Models Of MSO Formulas

Diese Arbeit erweitert Courcelles Theorem, indem sie zeigt, dass Modelle von MSO2-Formeln mit freien Variablen durch Entscheidungsdiagramme linear parametrisierter Größe dargestellt werden können. Sie legt parametrisierte lineare obere Schranken für aussagenlogische Entscheidungsdiagramme (SDD) basierend auf Baumweite und geordnete binäre Entscheidungsdiagramme (OBDD) basierend auf Pfadweite fest.