| Title: |
A New Algorithm for Normal Dominance Constraints |
| Authors: |
Bodirsky, Manuel; Duchier, Denys; Niehren, Joachim; Miele, Sebastian |
| Contributors: |
Department of Computer Science Berlin; Humboldt-Universität zu Berlin = Humboldt University of Berlin = Université Humboldt de Berlin (HU Berlin); Linear logic, proof networks and categorial grammars (CALLIGRAMME); INRIA Lorraine; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA); Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS); Modeling Tree Structures, Machine Learning, and Information Extraction (MOSTRARE); Laboratoire d'Informatique Fondamentale de Lille (LIFL); Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe; Institut National de Recherche en Informatique et en Automatique (Inria); Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS); Programming Systems Lab Saarland; Saarland University Saarbrücken; J. Ian Munro |
| Source: |
ACM-SIAM Symposium on Discrete Algorithms - SODA'2003 ; https://inria.hal.science/inria-00536536 ; ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. pp.59-67 ; http://portal.acm.org/citation.cfm?id=982801 |
| Publisher Information: |
HAL CCSD; ACM Press |
| Publication Year: |
2004 |
| Collection: |
Université de Lille 3 - Sciences Humaines et Sociales: HAL |
| Subject Terms: |
dominance constraints; algorithme de graphe; graph algorithms; contraintes de dominance; [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]; [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
| Subject Geographic: |
New Orleans; Louisiana; United States |
| Description: |
ISBN: 0-89871-558-X ; International audience ; 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. |
| Document Type: |
conference object |
| Language: |
English |
| Availability: |
https://inria.hal.science/inria-00536536; https://inria.hal.science/inria-00536536/document; https://inria.hal.science/inria-00536536/file/wndc.pdf |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.191024EB |
| Database: |
BASE |