期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width~k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula and for
every k there is a linear-time algorithm that decides whether a given logical structure of tree width at most k satisfies . We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
关键词：Bodlaender, Courcelle, Logspace, monadic second-order logic, partial k-trees, tree width
