Loading...
Please wait, while we are loading the content...
Similar Documents
Recognizability equals definability for partial k-paths (1996).
| Content Provider | CiteSeerX |
|---|---|
| Author | Kabanets, Valentine |
| Abstract | It is well-known that a language is recognizable iff it is definable in a monadic second-order logic. The same holds for sets of finite ranked trees (or finite unranked trees, in which case one must use a counting monadic second-order logic). Courcelle initiated research into the problem of definability vs. recognizability for finite graphs. Unlike the case of words and trees, recognizability does not equal definability for arbitrary families of graphs. Courcelle and others have shown that definability implies recognizability for partial k-trees (graphs of bounded tree-width), and conjectured that the converse also holds. The converse implication was proved for the cases of k = 0; 1; 2; 3. It was also established for families of k-connected partial k-trees. In this thesis, we show that a recognizable family of partial k-paths (graphs of bounded path-width) is definable in a counting monadic second-order logic (CMS), thereby proving the equality of definability and recognizability for ... |
| File Format | |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Partial K-paths Recognizability Equal Definability Counting Monadic Second-order Logic Definability V Definability Implies Recognizability Bounded Tree-width Recognizable Family Finite Graph Unranked Tree Equal Definability K-connected Partial K-trees Converse Implication Partial K-trees Monadic Second-order Logic Recognizable Iff Arbitrary Family Bounded Path-width |
| Content Type | Text |
