A new algorithm for normal dominance constraints

ABSTRACT

Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.

REFERENCES

• 1: Ernst Althaus , Denys Duchier , Alexander Koller , Kurt Mehlhorn , Joachim Niehren , Sven Thiel, An efficient graph algorithm for dominance constraints, Journal of Algorithms, v.48 n.1, p.194-219, August 2003 [doi>10.1016/S0196-6774(03)00050-6]
• 2: R. Backofen, J. Rogers, and K. Vijay-Shanker. A first-order axiomatization of the theory of finite trees. Journal of Logic, Language, and Information, 4:5--39, 1995.
• 3: Manuel Bodirsky , Martin Kutz, Pure Dominance Constraints, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.287-298, March 14-16, 2002
• 4: J. Bos. Predicate logic unplugged. In Proceedings of the 10th Amsterdam Colloquium, pages 133--143, 1996.
• 5: A. Copestake, D. Flickinger, I. Sag, and C. Pollard. Minimal recursion semantics: An introduction. CSLI Draft, Sept. 1999.
• 6: Markus Egg , Alexander Koller , Joachim Niehren, The Constraint Language for Lambda Structures, Journal of Logic, Language and Information, v.10 n.4, p.457-485, 2001 [doi>10.1023/A:1017964622902]
• 7: C. Gardent and B. Webber. Describing discourse semantics. In Proceedings of the 4th TAG+ Workshop, Philadelphia, 1998. University of Pennsylvania.
• 8: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276715]
• 9: Alexander Koller , Joachim Niehren , Ralf Treinen, Dominance Constraints: Algorithms and Complexity, Selected papers from the Third International Conference, on Logical Aspects of Computational Linguistics, p.106-125, December 14-16, 1998
• 10: Mitchell P. Marcus , Donald Hindle , Margaret M. Fleck, D-theory: talking about talking about trees, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts [doi>10.3115/981311.981337]
• 11: Joachim Niehren , Stefan Thater, Bridging the gap between underspecification formalisms: minimal recursion semantics as dominance constraints, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.367-374, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075096.1075143]
• 12: J. Rogers and K. Vijay-Shanker. Obtaining trees from their descriptions: An application to tree-adjoining grammars. Computational Intelligence, 10:401--421, 1994.
• 13: S. Thiel. A linear time algorithm for the configuration problem of dominance graphs. Submitted, 2004. Max-Planck Institut, Saarbrücken.