On Homogeneous Model of Fluted Languages
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929608476065792 |
|---|---|
| author | Kojelis, Daumantas |
| author_facet | Kojelis, Daumantas |
| contents | We study the fluted fragment of first-order logic which is often viewed as a multi-variable non-guarded extension to various systems of description logics lacking role-inverses. In this paper we show that satisfiable fluted sentences (even under reasonable extensions) admit special kinds of ``nice'' models which we call globally/locally homogeneous. Homogeneous models allow us to simplify methods for analysing fluted logics with counting quantifiers and establish a novel result for the decidability of the (finite) satisfiability problem for the fluted fragment with periodic counting. More specifically, we will show that the (finite) satisfiability problem for the language is ${\rm T{\small OWER}}$-complete. If only two variable are used, computational complexity drops to ${\rm NE{\small XP}T{\small IME}}$-completeness. We supplement our findings by showing that generalisations of fluted logics, such as the adjacent fragment, have finite and general satisfiability problems which are, respectively, $Π^0_1$- and $Σ^0_1$-complete. Additionally, satisfiability becomes $Σ^1_1$-complete if periodic counting quantifiers are permitted. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19084 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Homogeneous Model of Fluted Languages Kojelis, Daumantas Logic in Computer Science We study the fluted fragment of first-order logic which is often viewed as a multi-variable non-guarded extension to various systems of description logics lacking role-inverses. In this paper we show that satisfiable fluted sentences (even under reasonable extensions) admit special kinds of ``nice'' models which we call globally/locally homogeneous. Homogeneous models allow us to simplify methods for analysing fluted logics with counting quantifiers and establish a novel result for the decidability of the (finite) satisfiability problem for the fluted fragment with periodic counting. More specifically, we will show that the (finite) satisfiability problem for the language is ${\rm T{\small OWER}}$-complete. If only two variable are used, computational complexity drops to ${\rm NE{\small XP}T{\small IME}}$-completeness. We supplement our findings by showing that generalisations of fluted logics, such as the adjacent fragment, have finite and general satisfiability problems which are, respectively, $Π^0_1$- and $Σ^0_1$-complete. Additionally, satisfiability becomes $Σ^1_1$-complete if periodic counting quantifiers are permitted. |
| title | On Homogeneous Model of Fluted Languages |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2411.19084 |