Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

Parallelism Constraints

Katrin E. Erk, Joachim Niehren

International Conference on Rewriting Techniques and Applications, Vol. 1833 of Lecture Notes in Computer Science, pp. 110--126, Springer-Verlag, Berlin, 2000

Parallelism constraints are logical desciptions of trees. They are as expressive as context unification, i.e. second-order linear unification. We present a semi-decision procedure enumerating all most general unifiers of a parallelism constraint and prove it sound and complete. In contrast to all known procedures for context unification, the presented procedure terminates for the important fragment of dominance constraints and performs reasonably well in a recent application to underspecified natural language semantics.

Download PDF        Show BibTeX               

@INPROCEEDINGS{ParCons00,
  title = {Parallelism Constraints},
  author = {Katrin E. Erk and Joachim Niehren},
  year = {2000},
  publisher = {{Springer-Verlag, Berlin}},
  booktitle = {International Conference on Rewriting Techniques and                   Applications},
  series = {{Lecture Notes in Computer Science}},
  volume = {{1833}},
  pages = {{110--126}},
  address = {{Norwich, U.K.}},
}

Login to edit