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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Situated Simplification

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

Podelski,  Andreas
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

Podelski, A., & Smolka, G. (1997). Situated Simplification. Theoretical Computer Science, 173(1), 235-252.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3A11-F
Zusammenfassung
Testing satisfaction of guards is the essential operation of concurrent constraint programming ({\footnotesize CCP}) systems. We present and prove correct, for the first time, an incremental algorithm for the simultaneous tests of entailment and disentailment of rational tree constraints to be used in {\footnotesize CCP} systems with deep guards (\eg, in {\footnotesize AKL} or in Oz). The algorithm is presented as the {\em simplification\/} of the constraints which form the (possibly deep) guards and which are {\em situated\/} at different nodes in a tree (of arbitrary depth). The nodes correspond to local computation spaces. In this algorithm, a variable may have multiple bindings (which each represent a constraint on that same variable in a different node). These may be realized in various ways. We give a simple fixed-point algorithm and use it for proving that the tests implemented by another, practical algorithm are correct and complete for entailment and disentailment. We formulate the results in this paper for rational tree constraints; they can be adapted to finite and feature trees.