Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Set Constraints with Intersection

Charatonik, W., & Podelski, A. (2002). Set Constraints with Intersection. Information and Computation, 179, 213-229.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Charatonik, Witold1, Autor           
Podelski, Andreas1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Set constraints are inclusions between expressions denoting sets of trees (over a given alphabet of constructor symbols). The efficiency of their satisfiability test is a central issue in set-based program analysis, their main application domain. We introduce the class of {\em set constraints with intersection}\/ (the only operators forming the expressions are constructors and intersection) and show that its satisfiability problem is DEXPTIME-complete. This is the first class of set constraints (over a general constructor alphabet) that falls into this complexity class. The solved form in our algorithm represents the least solution as a tree automaton and exhibits which variables denote the empty set. We furthermore prove that set constraints with intersection are equivalent to {\em definite set constraints}\/ (in expressive power, and the satisfiability problems are linearly inter-reducible). The class of definite set constraints was the first one for which the decidability question was solved; we hereby settle also the complexity question.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003-05-092002
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 202134
Anderer: Local-ID: C1256104005ECAFC-079D7DD74FCAD6F6412566FD0057B689-CPintersectionJ
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information and Computation
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 179 Artikelnummer: - Start- / Endseite: 213 - 229 Identifikator: ISSN: 0890-5401