Solving unrestricted dominance graphs

Alexander Koller and Stefan Thater

In Proceedings of the 12th Conference on Formal Grammar, Dublin, 2007.

We present the first ever algorithm for solving unrestricted dominance graphs. The algorithm extends existing polynomial solvers for restricted classes of dominance graphs, which are not sufficient to model newer theories of scope ambiguity. Using the new solver, these theories now have access to an efficient solver for the first time. The solver runs in cubic time; for those graph classes that could be solved in the past, the runtime is reduced to the same quadratic time that the most efficient previous solvers achieved.

Download: Download

BibTeX Entry
@InProceedings{fg07-unrestricted,
	author = {Alexander Koller and Stefan Thater},
	title = {Solving unrestricted dominance graphs},
	year = 2007,
	booktitle = {Proceedings of the 12th Conference on Formal Grammar},
	address = {Dublin}
}

Back: Publications