Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25768
Titel: Parallelism and tree regular constraints
Verfasser: Niehren, Joachim
Villaret, Mateu
Sprache: Englisch
Erscheinungsjahr: 2002
Quelle: 9th International Conference on Logic for Programming Artificial Intelligence and Reasoning, Tbilisi, Georgia, 14-18 October 2002, pp. 311-326 (Lecture Notes on Artificial Intelligence; 2514)
SWD-Schlagwörter: Constraint-Programmierung
Freie Schlagwörter: Tree Regular Constraints
DDC-Sachgruppe: 004 Informatik
Dokumentart : InProceedings (Aufsatz / Paper einer Konferenz etc.)
Kurzfassung: Parallelism constraints are logical descriptions of trees. Parallelism constraints subsume dominance constraints and are equal in expressive power to context unification. Parallelism constraints belong to the constraint language for lambda structures (CLLS) which serves for modeling natural language semantics. In this paper, we investigate the extension of parallelism constraints by tree regular constraints. This canonical extension is subsumed by the monadic second-order logic over parallelism constraints. We analyze the precise expressiveness of this extension on basis of a new relationship between tree automata and logic. Our result is relevant for classifying different extensions of parallelism constraints, as in CLLS. Finally, we prove that parallelism constraints and context unification remain equivalent when extended with tree regular constraints.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-2833
hdl:20.500.11880/25824
http://dx.doi.org/10.22028/D291-25768
SciDok-Publikation: 29-Jun-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
sdom.pdf139,87 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.