An Efficient Graph Algorithm for Dominance Constraints

Ernst Althaus; Denys Duchier; Alexander Koller; Kurt Mehlhorn; Joachim Niehren; Sven Thiel

inria-00536539, version 1

An Efficient Graph Algorithm for Dominance Constraints

Ernst Althaus ¹, Denys Duchier ()^a^, 2, Alexander Koller ³, Kurt Mehlhorn ¹, Joachim Niehren () ^4, 5, Sven Thiel ¹

Journal of Algorithms 48, 1 (2003) 194-219

Résumé : Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.

a – INRIA
1 : Max Planck Institut für Informatik (MPII)
Max-Planck-Institut
2 : CALLIGRAMME (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : Allgemeine Linguistik Computational Linguistics and phonetics (Allgemeine Linguistik)
Saarland University
4 : MOSTRARE (INRIA Futurs)
INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales
5 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA

inria-00536539, version 1
http://hal.inria.fr/inria-00536539
oai:hal.inria.fr:inria-00536539
Contributeur : Joachim Niehren <>
Déposé pour le compte de : Joachim NIEHREN <>
Soumis le : Mardi 16 Novembre 2010, 13:50:27
Dernière modification le : Mercredi 24 Novembre 2010, 14:52:00

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1016/S0196-6774(03)00050-6

Texte intégral chez l'éditeur

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00536539"><analytic>
<author><persName><forename>Ernst</forename><surname>Althaus</surname></persName>
<affiliation>
<orgName type="laboratory">MPII</orgName>
<orgName type="team">Max Planck Institut für Informatik</orgName>
<country>DE</country>
<orgName type="institution">Max-Planck-Institut</orgName>
</affiliation>
</author>
<author><persName><forename>Denys</forename><surname>Duchier</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CALLIGRAMME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Alexander</forename><surname>Koller</surname></persName>
<affiliation>
<orgName type="laboratory">Allgemeine Linguistik</orgName>
<orgName type="team">Allgemeine Linguistik Computational Linguistics and phonetics</orgName>
<country>FR</country>
<orgName type="institution">Saarland University</orgName>
</affiliation>
</author>
<author><persName><forename>Kurt</forename><surname>Mehlhorn</surname></persName>
<affiliation>
<orgName type="laboratory">MPII</orgName>
<orgName type="team">Max Planck Institut für Informatik</orgName>
<country>DE</country>
<orgName type="institution">Max-Planck-Institut</orgName>
</affiliation>
</author>
<author><persName><forename>Joachim</forename><surname>Niehren</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">MOSTRARE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Sven</forename><surname>Thiel</surname></persName>
<affiliation>
<orgName type="laboratory">MPII</orgName>
<orgName type="team">Max Planck Institut für Informatik</orgName>
<country>DE</country>
<orgName type="institution">Max-Planck-Institut</orgName>
</affiliation>
</author>
<title type="main" level="a">An Efficient Graph Algorithm for Dominance Constraints</title></analytic><monogr><title level="j" type="main">Journal of Algorithms</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">2003-08-00</biblScope><biblScope type="vol">48</biblScope><biblScope type="issue">1</biblScope><biblScope type="pp">194-219</biblScope></imprint></monogr><idno type="doi">10.1016/S0196-6774(03)00050-6</idno><idno type="HALid">http://hal.inria.fr/inria-00536539</idno><idno type="HALFile">http://hal.inria.fr/inria-00536539/PDF/eff-dom.pdf</idno></biblStruct>
</listBibl>
</listBibl>