Finitely Bounded Homogeneity Turned Inside-Out
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908510633066496 |
|---|---|
| author | Rydval, Jakub |
| author_facet | Rydval, Jakub |
| contents | Deciding the amalgamation property for a given class of finite structures is an important subroutine in classifying countable finitely homogeneous structures. We study the computational complexity of the amalgamation decision problem for finitely bounded classes, i.e., classes specified by a finite set of forbidden finite substructures, or equivalently by a finite set of universal axioms. We link the amalgamation decision problem to the problem of testing the containment between the reducts of two given finitely bounded amalgamation classes to a given common subset of their signatures. On the one hand, this link enables polynomial-time reductions from various decision problems that can be represented within the reduct containment problem for finitely bounded amalgamation classes, e.g., the 2-exponential square tiling problem, leading to a new lower bound for the complexity of the amalgamation decision problem: 2NEXPTIME-hardness. On the other hand, the link also allows us to show that the amalgamation decision problem is decidable under the assumption that every finitely bounded strong amalgamation class has a computable finitely bounded Ramsey expansion. The runtime of our conditional decision procedure depends 2-exponentially on the size of a minimal Ramsey expansion. We subsequently prove that the closely related problem of testing homogenizability is already undecidable, by a polynomial-time reduction from the regularity of context-free languages. Our results indicate that the relationship between finitely bounded amalgamation classes and arbitrary finitely bounded classes shares similarities with the relationship between regular grammars and context-free grammars. A key difference is that the regularity of context-free grammars can be tested in linear time, while the problem of testing the amalgamation property for finitely bounded classes is 2NEXPTIME-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_00452 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Finitely Bounded Homogeneity Turned Inside-Out Rydval, Jakub Logic in Computer Science Logic 03D45, 03D15, 68Q17, 03D05 Deciding the amalgamation property for a given class of finite structures is an important subroutine in classifying countable finitely homogeneous structures. We study the computational complexity of the amalgamation decision problem for finitely bounded classes, i.e., classes specified by a finite set of forbidden finite substructures, or equivalently by a finite set of universal axioms. We link the amalgamation decision problem to the problem of testing the containment between the reducts of two given finitely bounded amalgamation classes to a given common subset of their signatures. On the one hand, this link enables polynomial-time reductions from various decision problems that can be represented within the reduct containment problem for finitely bounded amalgamation classes, e.g., the 2-exponential square tiling problem, leading to a new lower bound for the complexity of the amalgamation decision problem: 2NEXPTIME-hardness. On the other hand, the link also allows us to show that the amalgamation decision problem is decidable under the assumption that every finitely bounded strong amalgamation class has a computable finitely bounded Ramsey expansion. The runtime of our conditional decision procedure depends 2-exponentially on the size of a minimal Ramsey expansion. We subsequently prove that the closely related problem of testing homogenizability is already undecidable, by a polynomial-time reduction from the regularity of context-free languages. Our results indicate that the relationship between finitely bounded amalgamation classes and arbitrary finitely bounded classes shares similarities with the relationship between regular grammars and context-free grammars. A key difference is that the regularity of context-free grammars can be tested in linear time, while the problem of testing the amalgamation property for finitely bounded classes is 2NEXPTIME-hard. |
| title | Finitely Bounded Homogeneity Turned Inside-Out |
| topic | Logic in Computer Science Logic 03D45, 03D15, 68Q17, 03D05 |
| url | https://arxiv.org/abs/2108.00452 |