Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-ADE5-A Versions-Permalink: https://hdl.handle.net/21.11116/0000-000E-3426-D
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bachmair, Leo1, Autor           
Ganzinger, Harald1, Autor           
Waldmann, Uwe1, 2, Autor                 
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              
2Automation of Logic, MPI for Informatics, Max Planck Society, ou_1116545              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121993
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519884
Anderer: Local-ID: C1256104005ECAFC-965715C8DB9EACC7C125614C004A751B-BachmairGanzingerWaldmann-93-lics
DOI: 10.1109/LICS.1993.287598
BibTex Citekey: Bachmair_IEEE93
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Eighth Annual IEEE Symposium on Logic in Computer Science
Veranstaltungsort: Montreal, Canada
Start-/Enddatum: 1993-06-19 - 1993-06-23

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Eighth Annual IEEE Symposium on Logic in Computer Science
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Los Alamitos, USA : IEEE
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 75 - 83 Identifikator: ISBN: 0-8186-3140-6