Abstract.
We consider graph decision problems on partial 3-trees that can be solved by a finite-state, leaf-to-root tree automaton processing a width-3 tree decomposition of the given graph. The class of yes-instances of such a problem is said to be recognizable by the tree automaton. In this paper we show that any such class of recognizable partial 3-trees is definable by a sentence in CMS logic. Here, CMS logic is the extension of Monadic Second-order logic with predicates to count the cardinality of sets modulo fixed integers. We also generalize this result to show that recognizability (by a tree automaton that processes width-k tree decompositions) implies CMS-definability for k -connected partial k -trees. The converse—definability implies recognizability—is known to hold for any class of partial k -trees, and even for any graph class with an appropriate definition of recognizability. It has been conjectured that recognizability implies definability over partial k -trees; but a proof was previously known only for k ≤ 2 . This paper proves the conjecture, and hence the equivalence of definability and recognizability, over partial 3-trees and k -connected partial k -trees. We use techniques that may lead to a proof of this equivalence over all partial k -trees.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received February 3, 1997; revised July 24, 1997.
Rights and permissions
About this article
Cite this article
Kaller, D. Definability Equals Recognizability of Partial 3-Trees and \sl k -Connected Partial \sl k -Trees . Algorithmica 27, 348–381 (2000). https://doi.org/10.1007/s004530010024
Issue Date:
DOI: https://doi.org/10.1007/s004530010024