On the Monadic Second-Order Transduction Hierarchy
We compare classes of finite relational structures via monadic second-order transductions. More precisely, we study the preorder where we set C \subseteq K if, and only if, there exists a transduction {\tau} such that C\subseteq{\tau}(K). If we only consider classes of incidence structures we can co...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2010-06-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1208/pdf |
| _version_ | 1797268768547667968 |
|---|---|
| author | Achim Blumensath Bruno Courcelle |
| author_facet | Achim Blumensath Bruno Courcelle |
| author_sort | Achim Blumensath |
| collection | DOAJ |
| description | We compare classes of finite relational structures via monadic second-order
transductions. More precisely, we study the preorder where we set C \subseteq K
if, and only if, there exists a transduction {\tau} such that
C\subseteq{\tau}(K). If we only consider classes of incidence structures we can
completely describe the resulting hierarchy. It is linear of order type
{\omega}+3. Each level can be characterised in terms of a suitable variant of
tree-width. Canonical representatives of the various levels are: the class of
all trees of height n, for each n \in N, of all paths, of all trees, and of all
grids. |
| first_indexed | 2024-04-25T01:37:44Z |
| format | Article |
| id | doaj.art-7066cd290eea480d962aca0d908014fa |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:44Z |
| publishDate | 2010-06-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-7066cd290eea480d962aca0d908014fa2024-03-08T09:11:27ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742010-06-01Volume 6, Issue 210.2168/LMCS-6(2:2)20101208On the Monadic Second-Order Transduction HierarchyAchim BlumensathBruno CourcelleWe compare classes of finite relational structures via monadic second-order transductions. More precisely, we study the preorder where we set C \subseteq K if, and only if, there exists a transduction {\tau} such that C\subseteq{\tau}(K). If we only consider classes of incidence structures we can completely describe the resulting hierarchy. It is linear of order type {\omega}+3. Each level can be characterised in terms of a suitable variant of tree-width. Canonical representatives of the various levels are: the class of all trees of height n, for each n \in N, of all paths, of all trees, and of all grids.https://lmcs.episciences.org/1208/pdfmathematics - logicg.2.2f.4.1 |
| spellingShingle | Achim Blumensath Bruno Courcelle On the Monadic Second-Order Transduction Hierarchy Logical Methods in Computer Science mathematics - logic g.2.2 f.4.1 |
| title | On the Monadic Second-Order Transduction Hierarchy |
| title_full | On the Monadic Second-Order Transduction Hierarchy |
| title_fullStr | On the Monadic Second-Order Transduction Hierarchy |
| title_full_unstemmed | On the Monadic Second-Order Transduction Hierarchy |
| title_short | On the Monadic Second-Order Transduction Hierarchy |
| title_sort | on the monadic second order transduction hierarchy |
| topic | mathematics - logic g.2.2 f.4.1 |
| url | https://lmcs.episciences.org/1208/pdf |
| work_keys_str_mv | AT achimblumensath onthemonadicsecondordertransductionhierarchy AT brunocourcelle onthemonadicsecondordertransductionhierarchy |