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

Abstract: 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
From: Joachim Niehren <>
Submitted for: Joachim NIEHREN <>
Submitted on: Tuesday, 16 November 2010 13:50:27
Updated on: Wednesday, 24 November 2010 14:52:00

See detailed view

Associated documents

PDF :

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

Full text from publisher

Export

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 in peer-reviewed journal</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>