Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2004
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909174662692864 |
|---|---|
| author | Pratt-Hartmann, Ian |
| author_facet | Pratt-Hartmann, Ian |
| contents | We show that the satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0411031 |
| institution | arXiv |
| publishDate | 2004 |
| record_format | arxiv |
| spellingShingle | Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers Pratt-Hartmann, Ian Logic in Computer Science F.4.1 We show that the satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly. |
| title | Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers |
| topic | Logic in Computer Science F.4.1 |
| url | https://arxiv.org/abs/cs/0411031 |