Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Konferenzbeitrag

Set Constraints are the Monadic Class

MPG-Autoren
/persons/resource/persons44055

Bachmair,  Leo
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons44474

Ganzinger,  Harald
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45689

Waldmann,  Uwe       
Automation of Logic, MPI for Informatics, Max Planck Society;
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-ADE5-A
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.