文章基本信息

标题：Tree-width for first order formulae
本地全文：下载
作者：Adler Isolde ; Mark Weyer
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2012
卷号：8
期号：1
页码：1
DOI：10.2168/LMCS-8(1:32)2012
出版社：Technical University of Braunschweig
摘要：We introduce tree-width for first order formulae \phi, fotw(\phi). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of formulae of bounded fotw, model checking is fixed parameter tractable, with parameter the length of the formula. This is done by translating a formula \phi\ with fotw(\phi)
其他关键词：treewidth, model checking, conjunctive queries, quantified constraint formulae, first-order logic, elimination-width, cops and robbers game.