Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2008
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911845058609152 |
|---|---|
| author | Pratt-Hartmann, Ian |
| author_facet | Pratt-Hartmann, Ian |
| contents | The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting is NP-complete; the data-complexity of both query-answering and finite query-answering for the two-variable guarded fragment with counting is co-NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0806_1636 |
| institution | arXiv |
| publishDate | 2008 |
| record_format | arxiv |
| spellingShingle | Data-Complexity of the Two-Variable Fragment with Counting Quantifiers Pratt-Hartmann, Ian Logic in Computer Science Artificial Intelligence Computational Complexity F.4.1 The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting is NP-complete; the data-complexity of both query-answering and finite query-answering for the two-variable guarded fragment with counting is co-NP-complete. |
| title | Data-Complexity of the Two-Variable Fragment with Counting Quantifiers |
| topic | Logic in Computer Science Artificial Intelligence Computational Complexity F.4.1 |
| url | https://arxiv.org/abs/0806.1636 |