Rank-decreasing transductions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910306616213504 |
|---|---|
| author | Bojańczyk, Mikołaj Ohlmann, Pierre |
| author_facet | Bojańczyk, Mikołaj Ohlmann, Pierre |
| contents | We propose to study transformations on graphs, and more generally structures, by looking at how the cut-rank (as introduced by Oum) of subsets is affected when going from the input structure to the output structure. We consider transformations in which the underlying sets are the same for both the input and output, and so the cut-ranks of subsets can be easily compared. The purpose of this paper is to give a characterisation of logically defined transductions that is expressed in purely structural terms, without referring to logic: transformations which decrease the cut-rank, in the asymptotic sense, are exactly those that can be defined in monadic second-order logic. This characterisation assumes that the transduction has inputs of bounded treewidth; we also show that the characterisation fails in the absence of any assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13328 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rank-decreasing transductions Bojańczyk, Mikołaj Ohlmann, Pierre Logic in Computer Science We propose to study transformations on graphs, and more generally structures, by looking at how the cut-rank (as introduced by Oum) of subsets is affected when going from the input structure to the output structure. We consider transformations in which the underlying sets are the same for both the input and output, and so the cut-ranks of subsets can be easily compared. The purpose of this paper is to give a characterisation of logically defined transductions that is expressed in purely structural terms, without referring to logic: transformations which decrease the cut-rank, in the asymptotic sense, are exactly those that can be defined in monadic second-order logic. This characterisation assumes that the transduction has inputs of bounded treewidth; we also show that the characterisation fails in the absence of any assumptions. |
| title | Rank-decreasing transductions |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2401.13328 |