Parallel Play Saves Quantifiers
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916194379890688 |
|---|---|
| author | Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik Williams, Ryan |
| author_facet | Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik Williams, Ryan |
| contents | The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear orders and strings, and introduce a technique we call "parallel play", that dramatically reduces the number of quantifiers needed in many cases. Linear orders and strings are the most basic representatives of ordered structures -- a class of structures that has historically been notoriously difficult to analyze. Yet, in this paper, we provide upper bounds on the number of quantifiers needed to characterize different-sized subsets of these structures, and prove that they are tight up to constant factors, including, in some cases, up to a factor of $1+\varepsilon$, for arbitrarily small $\varepsilon$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10293 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Play Saves Quantifiers Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik Williams, Ryan Logic in Computer Science Computational Complexity The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear orders and strings, and introduce a technique we call "parallel play", that dramatically reduces the number of quantifiers needed in many cases. Linear orders and strings are the most basic representatives of ordered structures -- a class of structures that has historically been notoriously difficult to analyze. Yet, in this paper, we provide upper bounds on the number of quantifiers needed to characterize different-sized subsets of these structures, and prove that they are tight up to constant factors, including, in some cases, up to a factor of $1+\varepsilon$, for arbitrarily small $\varepsilon$. |
| title | Parallel Play Saves Quantifiers |
| topic | Logic in Computer Science Computational Complexity |
| url | https://arxiv.org/abs/2402.10293 |