English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Set Constraints are the Monadic Class

Bachmair, L., Ganzinger, H., & Waldmann, U. (1993). Set Constraints are the Monadic Class. In Eighth Annual IEEE Symposium on Logic in Computer Science (pp. 75-83). Los Alamitos, USA: IEEE.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bachmair, Leo1, Author           
Ganzinger, Harald1, Author           
Waldmann, Uwe1, 2, Author           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              
2Automation of Logic, MPI for Informatics, Max Planck Society, ou_1116545              

Content

show
hide
Free keywords: -
 Abstract: We investigate the relationship between set constraints and the monadic class of first-order formulas and show that set constraints are essentially equivalent to the monadic class. From this equivalence we can infer that the satisfiability problem for set constraints is complete for NEXPTIME\@. More precisely, we prove that this problem has a lower bound of ${\rm NTIME}(c^{n/\log n})$. The relationship between set constraints and the monadic class also gives us decidability and complexity results for certain practically useful extensions of set constraints, in particular ``negative'' projections and subterm equality tests.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-121993
 Publication Status: Issued
 Pages: -
 Publishing info: Los Alamitos, USA : IEEE
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519884
Other: Local-ID: C1256104005ECAFC-965715C8DB9EACC7C125614C004A751B-BachmairGanzingerWaldmann-93-lics
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Montreal, Canada
Start-/End Date: 2003-07-08 - 2003-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Eighth Annual IEEE Symposium on Logic in Computer Science
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Los Alamitos, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 75 - 83 Identifier: -