Advanced search

Browse by subject

Browse by provider

Browse by language

Content Details
Normal View
CIP View

Bernays-Schoenfinkel-Ramsey with Simple ...

Voigt, Marco...

Free

Share this content

Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete by Voigt, Marco ( Author )

Content Provider	Lemonjar Open Access
Publisher	N.A
Publication Date	01-01-2015
Summary	First-order predicate logic extended with linear arithmetic is undecidable, in general. We show that the Bernays-Sch\"onfinkel-Ramsey (BSR) fragment extended with linear arithmetic restricted to simple bounds (SB) is decidable through finite ground instantiation. The identified ground instances can be employed to restrict the search space of existing automated reasoning procedures for BSR(SB). Satisfiability of BSR(SB) compared to BSR remains NEXPTIME-complete. The decidability result is almost tight because BSR is undecidable if extended with linear difference inequations, simple additive inequations, quotient inequations and multiplicative inequations.
ISBN	-
Item Type	Article
File Type	pdf
File Size	36.88 KB
Language	English
Subjects	-
Unlimited	MYR 0.01
Total read	-
URL	http://arxiv.org/abs/1501.07209

Citation

Review the full bibliography data and make any necessary corrections before using. Always consult your library resources for the exact formatting and punctuation guidelines.

AMA 11th EditionReferences

Voigt, Marco. Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. N.A. January 01, 2015. Accessed November 21, 2024. https://online.provdatabase.com/cite/18308

APA 7th EditionReferences

Voigt, Marco. (2015). Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. N.A. https://online.provdatabase.com/cite/18308

Chicago 17th EditionReferences

Voigt, Marco. Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. N.A. 2015. https://online.provdatabase.com/cite/18308

HarvardReferences

Voigt, Marco. (2015). Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. [Online]. N.A. Available from: https://online.provdatabase.com/cite/18308. (Accessed 21 November 2024).

Harvard AustraliaReferences

Voigt, Marco, 2015, Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete, N.A, viewed 21 November 2024, <https://online.provdatabase.com/cite/18308>

MLA 9th EditionWorks Cited

Voigt, Marco. Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. N.A, 2015. PROV Database, https://online.provdatabase.com/cite/18308.

Share this eBook