### Deciding first-order properties of locally tree-decomposable structuresDeciding first-order properties of locally tree-decomposable structures

Access Restriction
Subscribed

 Author Frick, Markus ♦ Grohe, Martin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2001 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword First-order logic ♦ Locality ♦ Model-checking ♦ Parameterized complexity ♦ Planar graphs ♦ Query evaluation ♦ Tree-width Abstract We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes of bounded valence or of bounded tree-width. We also consider a slightly more general concept of a class of structures having bounded local tree-width.We show that for each property φ of structures that is definable in first-order logic and for each locally tree-decomposable class C of structures, there is a linear time algorithm deciding whether a given structure $\textit{A}$ ∈ C has property φ. For classes C of bounded local tree-width, we show that for every $\textit{k}$ ≥ 1 there is an algorithm solving the same problem in time $O(n^{1+(1/k)})$ (where $\textit{n}$ is the cardinality of the input structure). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2001-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 48 Issue Number 6 Page Count 23 Starting Page 1184 Ending Page 1206

#### Open content in new tab

Source: ACM Digital Library