An Efficient Graph Algorithm for Dominance Constraints
Identifieur interne : 007580 ( Main/Curation ); précédent : 007579; suivant : 007581An Efficient Graph Algorithm for Dominance Constraints
Auteurs : Ernst Althaus ; Denys Duchier ; Alexander Koller ; Kurt Mehlhorn ; Joachim Niehren ; Sven ThielSource :
- Journal of Algorithms ; 2003.
English descriptors
- KwdEn :
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.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003A08
- to stream Crin, to step Curation: Pour aller vers cette notice dans l'étape Curation :003A08
- to stream Crin, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000B11
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :007958
Links to Exploration step
CRIN:althaus03aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="448">An Efficient Graph Algorithm for Dominance Constraints</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:althaus03a</idno>
<date when="2003" year="2003">2003</date>
<idno type="wicri:Area/Crin/Corpus">003A08</idno>
<idno type="wicri:Area/Crin/Curation">003A08</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003A08</idno>
<idno type="wicri:Area/Crin/Checkpoint">000B11</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000B11</idno>
<idno type="wicri:Area/Main/Merge">007958</idno>
<idno type="wicri:Area/Main/Curation">007580</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">An Efficient Graph Algorithm for Dominance Constraints</title>
<author><name sortKey="Althaus, Ernst" sort="Althaus, Ernst" uniqKey="Althaus E" first="Ernst" last="Althaus">Ernst Althaus</name>
</author>
<author><name sortKey="Duchier, Denys" sort="Duchier, Denys" uniqKey="Duchier D" first="Denys" last="Duchier">Denys Duchier</name>
</author>
<author><name sortKey="Koller, Alexander" sort="Koller, Alexander" uniqKey="Koller A" first="Alexander" last="Koller">Alexander Koller</name>
</author>
<author><name sortKey="Mehlhorn, Kurt" sort="Mehlhorn, Kurt" uniqKey="Mehlhorn K" first="Kurt" last="Mehlhorn">Kurt Mehlhorn</name>
</author>
<author><name sortKey="Niehren, Joachim" sort="Niehren, Joachim" uniqKey="Niehren J" first="Joachim" last="Niehren">Joachim Niehren</name>
</author>
<author><name sortKey="Thiel, Sven" sort="Thiel, Sven" uniqKey="Thiel S" first="Sven" last="Thiel">Sven Thiel</name>
</author>
</analytic>
<series><title level="j">Journal of Algorithms</title>
<imprint><date when="2003" type="published">2003</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>dominance constraints</term>
<term>graph algorithm</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en" wicri:score="2240">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.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007580 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 007580 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Curation |type= RBID |clé= CRIN:althaus03a |texte= An Efficient Graph Algorithm for Dominance Constraints }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |