English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 DetailsSummary
  Bernays-Schönfinkel-Ramsey with Simple Bounds is NEXPTIME-complete

Voigt, M., & Weidenbach, C. (2015). Bernays-Schönfinkel-Ramsey with Simple Bounds is NEXPTIME-complete. Retrieved from http://arxiv.org/abs/1501.07209.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AA87-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AA88-F
Genre: Paper

Files

show Files
hide Files
:
arXiv:1501.07209.pdf (Preprint), 366KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0024-AA89-D
Name:
arXiv:1501.07209.pdf
Description:
File downloaded from arXiv at 2015-01-29 18:18
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/help/license

Locators

show

Creators

show
hide
 Creators:
Voigt, Marco1, Author           
Weidenbach, Christoph1, Author           
Affiliations:
1Automation of Logic, MPI for Informatics, Max Planck Society, ou_1116545              

Content

show
hide
Free keywords: Computer Science, Logic in Computer Science, cs.LO,Computer Science, Computational Complexity, cs.CC
 Abstract: Linear arithmetic extended with free predicate symbols is undecidable, in general. We show that the restriction of linear arithmetic inequations to simple bounds extended with the Bernays-Sch\"onfinkel-Ramsey free first-order fragment is decidable and NEXPTIME-complete. The result is almost tight because the Bernays-Sch\"onfinkel-Ramsey fragment is undecidable in combination with linear difference inequations, simple additive inequations, quotient inequations and multiplicative inequations.

Details

show
hide
Language(s):
 Dates: 2015-01-282015
 Publication Status: Published online
 Pages: 25 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1501.07209
URI: http://arxiv.org/abs/1501.07209
BibTex Citekey: VoigtWeidenbacharXiv2015
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show