Please use this identifier to cite or link to this item: doi:10.22028/D291-25768
Title: Parallelism and tree regular constraints
Author(s): Niehren, Joachim
Villaret, Mateu
Language: English
Year of Publication: 2002
OPUS Source: 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 key words: Constraint-Programmierung
Free key words: Tree Regular Constraints
DDC notations: 004 Computer science, internet
Publikation type: Conference Paper
Abstract: 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 to this record: urn:nbn:de:bsz:291-scidok-2833
Date of registration: 29-Jun-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
sdom.pdf139,87 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.