de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

An Undecidable Fragment of the Theory of Set Constraints

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44232

Charatonik,  Witold
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Charatonik, W. (1998). An Undecidable Fragment of the Theory of Set Constraints. Information Processing Letters, 68, 147-151.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3815-8
Zusammenfassung
Set constraints are inclusions between expressions denoting sets of trees. In atomic set constraints, the syntax of set expressions is restricted not to contain any Boolean set operators. Using a reduction from the Hilbert's Tenth Problem we prove the undecidability of the $\exists^*\forall^*$-fragment of the first-order theory of atomic set constraints. This improves recent results by Seynhaeve et.\ al.