Back to Search
Start Over
One-variable logic meets Presburger arithmetic.
- Source :
-
Theoretical Computer Science . Jan2020, Vol. 802, p141-146. 6p. - Publication Year :
- 2020
-
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 Image 1 -completeness of the logic by presenting an optimal algorithm for solving its finite satisfiability problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 802
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 139771113
- Full Text :
- https://doi.org/10.1016/j.tcs.2019.09.028