Article3052: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Bartosz Bednarczyk (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Bartosz |ErsterAutorNachname=Bednarczyk }} {{Article |Referiert=0 |Title=One-Variable Logic Meets Presburger Ari…“) |
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 13: | Zeile 13: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We consider the one-variable fragment of first-order logic extended with Presburger constraints. The logic is designed in such a way that it subsumes the previously-known fragments extended with counting, modulo counting or cardinality comparison and combines their expressive powers. We prove | |Abstract=We consider the one-variable fragment of first-order logic extended with Presburger constraints. The logic is designed in such a way that it subsumes the previously-known fragments extended with counting, modulo counting or cardinality comparison and combines their expressive powers. We prove NP-completeness of the logic by presenting an optimal algorithm for solving its finite satisfiability problem. | ||
|DOI Name=10.1016/j.tcs.2019.09.028 | |DOI Name=10.1016/j.tcs.2019.09.028 | ||
|Forschungsgruppe=Computational Logic | |Forschungsgruppe=Computational Logic | ||
}} | }} | ||
Version vom 16. Oktober 2019, 20:48 Uhr
One-Variable Logic Meets Presburger Arithmetic
Bartosz BednarczykBartosz Bednarczyk
Bartosz Bednarczyk
One-Variable Logic Meets Presburger Arithmetic
Theoretical Computer Science, to appear
One-Variable Logic Meets Presburger Arithmetic
Theoretical Computer Science, to appear
- KurzfassungAbstract
We consider the one-variable fragment of first-order logic extended with Presburger constraints. The logic is designed in such a way that it subsumes the previously-known fragments extended with counting, modulo counting or cardinality comparison and combines their expressive powers. We prove NP-completeness of the logic by presenting an optimal algorithm for solving its finite satisfiability problem. - Forschungsgruppe:Research Group: Computational LogicComputational Logic
@article{B2019,
author = {Bartosz Bednarczyk},
title = {One-Variable Logic Meets Presburger Arithmetic},
journal = {Theoretical Computer Science},
publisher = {Elsevier},
year = {2019},
month = {September},
doi = {10.1016/j.tcs.2019.09.028}
}
