Parallelism and Tree Regular Constraints

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.
Type de document :
Communication dans un congrès
International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2002, Tblisi, Georgia. Springer, 2514, pp.311--326, 2002, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536827
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:12:50
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:18:21

Fichiers

sdom.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536827, version 1

Citation

Joachim Niehren, Mateu Villaret. Parallelism and Tree Regular Constraints. International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2002, Tblisi, Georgia. Springer, 2514, pp.311--326, 2002, Lecture Notes in Computer Science. 〈inria-00536827〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

59