P. and L. Tbox-décomposante, Chaque axiome de sous-TBox produit des "branches OR" dans le processus d'exécution du raisonnement Donc le nombre d'axiomes de la plus grande sous-TBox m i influence également le temps de SAT-DIST et de SAT-PARA sur la TBox-décomposante . Ce propre m i est la largeur de l'arbre de décomposition. Par conséquent, si nous supposons que f sat (m) = ?(2 m ), le problème de recherche de la décomposition optimale pour les SAT-PARA et SAT-DIST est équivalent à la recherche de largeur arborescente (triangulations de nombre de clique minimum) Dans ce mémoire

A. Le, M devrait être choisi à 1, k devrait être choisi à n (n = |Ex(A)|), et l'algorithme arrêtera uniquement la décomposition récursive lorsqu'il atteindra un graphe qui est une clique

. Le-principe-de-cette-approche, V n de V dont l'association entre les sommets de chaque V i est maximale et l'association des sommets entre les V i , V j différents est minimale. Ce principe est bien appliqué dans la segmentation d'image

E. Semble-de-sommets and . Est-un-ensemble-d, arêtes avec les valeurs de poids, est appelé un graphe d'axiome si chaque sommet v ? V est un axiome dans la TBox T , chaque arête e = (u, v) ? E si u, v ? V et il y a au moins un symbole partagé entre u et v

L. Tbox and T. Dans-la, figure 8.2 ci-dessus est représentée par un graphe d'axiome comme dans la Figure 8

. Dans-ce-mémoire, nous avons étudié un ensemble d'éléments de la théorie de décomposition overlay qui permet de transformer une ontologie en la logique de description (LD) dans un ensemble des ontologies en la logique de description distribuée (LDD) Nous avions pour objectif de montrer la préservation sémantique et d'inférence d'une telle décomposition

S. [. Amir and . Mcilraith, Partition-based logical reasoning for first-order and propositional theories, Artificial Intelligence, vol.162, issue.1-2, pp.49-88, 2005.
DOI : 10.1016/j.artint.2004.11.004

]. F. Baa90 and . Baader, Terminological cycles in KL-ONE-based knowledge representation languages, Proceedings of the Eighth National Conference on Artificial Intelligence, AAAI-90, pp.621-626, 1990.

]. F. Baa96 and . Baader, Logic-based knowledge representation, pp.8-16, 1996.

R. [. Borgida and . Brachman, Conceptual Modelling with Description Logics, pp.349-372, 2002.
DOI : 10.1017/cbo9780511711787.012

A. Berry, J. P. Bordat, and O. Cogis, Generating All the Minimal Separators of a Graph, Workshop on Graph-theoretic Concepts in Computer Science (WG'99), pp.167-172, 1999.
DOI : 10.1007/3-540-46784-X_17

D. Beneventano, S. Bergamaschi, S. Lodi, and C. Sartori, Terminological logics for schema design and query processing in OODBs, Knowledge Representation Meets Databases, 1994.

J. Bao, D. Caragea, and V. Honavar, A distributed tableau algorithm for packagebased description logics, Proc. of the IEEEACM International Conference on Web Intelligence, pp.404-410, 2006.

J. Bao, D. Caragea, and V. Honavar, On the Semantics of Linking and Importing in Modular Ontologies, ISWC 2006, pp.72-86, 2006.
DOI : 10.1007/11926078_6

M. Buchheit, F. M. Donini, and A. Schaerf, Decidable reasoning in terminological knowledge representation systems, Journal of Artificial Intelligence Research, vol.1, pp.109-138, 1993.

P. Bresciani, E. Franconi, and S. Tessaris, Implementing and testing expressive description logics : a preliminary report, Proceedings of DL-95, 4th International Workshop on Description Logics, pp.131-139, 1995.

]. F. Bhn-+-93, B. Baader, B. Hollunder, H. J. Nebel, E. Profitlich et al., An empirical analysis of optimization techniques for terminological representation systems, or : Making KRIS get a move on, DFKI Research Report RR-93-03, Deutsches Forschungszentrum für Künstliche Intelligenz, 1993.

I. [. Baader, U. Horrocks, and . Sattler, Description Logics as Ontology Languages for the Semantic Web, In KI Künstliche Intelligenz, vol.4, 2002.
DOI : 10.1007/978-3-540-32254-2_14

]. J. Bkd-+-02, M. Broekstra, S. Klein, D. Decker, F. Fensel et al., Enabling knowledge representation on the web by extending RDF schema, Computer Networks, vol.39, issue.5, pp.609-634, 2002.

J. Ronal, H. J. Brachman, and . Levesque, The tractability of subsumption in frame-based description languages, Proc. of the 4th National Conference on Artificial Intelligence (AAAI-84), pp.34-37, 1984.

F. Baader, C. Lutz, H. Sturm, and F. Wolter, Fusions of description logics, Proceedings of the International Workshop in Description Logics 2000 (DL2000), number 33 in CEUR-WS RWTH Aachen. Proceedings online available from http ://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS, pp.21-30, 2000.

M. Buchheit, F. M. Donini, W. Nutt, and A. Schaerf, Terminological system revisited : Terminology = schema + views, Proc. of the 12th Nat. Conf. on Artificial Intelligence (AAAI-94), pp.199-204, 1994.

W. [. Baader and . Nutt, Basic Description Logics. Spinger, 2003.

]. R. Bra78 and . Brachman, Structured inheritance networks, Research in Natural language understanding, 1978.

J. [. Brachman and . Schmolze, An Overview of the KL-ONE Knowledge Representation System*, Cognitive Science, vol.16, issue.10, pp.9171-216, 1985.
DOI : 10.1207/s15516709cog0902_1

U. [. Baader and . Sattler, An overview of tableau algorithms for description logics, Studia Logica, vol.69, issue.1, pp.5-40, 2001.
DOI : 10.1023/A:1013882326814

L. [. Borgida and . Serafini, Distributed Description Logics: Assimilating Information from Peer Sources, Journal of Data Semantics, vol.1, pp.153-184, 2003.
DOI : 10.1007/978-3-540-39733-5_7

[. Calvanese, Reasoning with inclusion axioms in description logics : Algorithms and complexity, European Conference on Artificial Intelligence, pp.303-307, 1996.

M. [. Cournier and . Habib, A new linear algorithm for Modular Decomposition, Proceedings of Trees in Algebra and Programming -CAAP'94, pp.64-84, 1994.
DOI : 10.1007/BFb0017474

R. K. Chu97-]-fan and . Chung, Spectral Graph Theory, 1997.

D. Calvanese, M. Lenzerini, and D. Nardi, Description logics for conceptual data modeling. Logics for Databases and Information Systems, pp.229-264, 1998.
DOI : 10.1007/978-1-4615-5643-5_8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.3016

K. [. Cuppens and . Yazdanian, A 'natural' decomposition of multi-level relations, Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy, p.273, 1992.
DOI : 10.1109/RISP.1992.213254

X. Ding, H. He, M. Zha, H. D. Gu, and . Simon, A min-max cut algorithm for graph partitioning and data clustering, Proceedings 2001 IEEE International Conference on Data Mining, pp.107-114, 2001.
DOI : 10.1109/ICDM.2001.989507

F. M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf, Reasoning in description logics, Foundation of Knowledge Representation, pp.191-236, 1996.

]. S. Eve79 and . Even, Graph Algorithms, 1979.

. Jr, D. R. Ford, . Fulkersonfra02-]-e, and . Franconi, Flows in networks Description logics for conceptual design, information access, and ontology integration, 1962.

]. M. Fra03, . Donini, and . Francesco, Complexity of Reasoning. Description Logic Handbook, 2003.

]. J. Fre95 and . Freeman, Improvements to Propositional Satisfiability Search Algorithms, 1995.

]. J. Fre96 and . Freeman, Hard random 3-sat problems and davis-putnam procedure, Artificial Intelligence, vol.81, pp.183-198, 1996.

]. F. Gav74 and . Gavil, The intersection graphs of a path in a tree are exactly the chordal graphs, Journal of Combinatorial Theory, vol.16, pp.47-56, 1974.

B. C. Grau, B. Parsia, and E. Sirin, Working with Multiple Ontologies on the Semantic Web, International Semantic Web Conference, pp.620-634, 2004.
DOI : 10.1007/978-3-540-30475-3_43

B. C. Grau, B. Parsia, and E. Sirin, Tableau algorithms for e-connections of description logics, 2004.

K. [. Grahne and . Räihä, Database decomposition into fourth normal form, Proceedings of the 9th International Conference on Very Large Data Bases, 1993.

M. [. Goasdou-'e and . Rousset, Rewriting conjunctive queries using views in description logics with existential restrictions, 2000.

]. T. Gru93 and . Gruber, A translation approach to portable ontology specifications, Knowledge Acquisition, pp.199-220, 1993.

L. [. Ghidini and . Serafini, Distributed first order logics, Frontiers Of Combining Systems 2, Studies in Logic and Computation, pp.121-140, 1998.

G. H. Golub, C. F. Van-loanhay79, and ]. P. Hayes, Matrix computations The logic of frames. Frames Conception and Text Understanding, 1979.

B. Hollunder, W. Nutt, and M. Schmidt-schauß, Subsumption algorithms for concept description languages, ECAI, pp.348-353, 1990.

]. I. Hor97 and . Horrocks, Optimising Tableaux Decision Procedures for Description Logics, 1997.

I. Horrocks, Using an expressive description logic : FaCT or fiction ?, Proc. of the 6th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR'98), pp.636-647, 1998.

I. Horrocks, DAML+OIL : a description logic for the semantic web, Bull. of the IEEE Computer Society Technical Committee on Data Engineering, vol.25, issue.1, pp.4-9, 2002.

I. Horrocks and P. F. Patel-schneider, FaCT and DLP, Proc. of the Automated Reasoning with Analytic Tableaux and Related Methods, pp.27-30, 1998.
DOI : 10.1007/3-540-69778-0_5

I. Horrocks and P. F. Patel-schneider, Optimizing description logic subsumption, Journal of Logic and Computation, vol.9, issue.3, pp.267-293, 1999.
DOI : 10.1093/logcom/9.3.267

I. Horrocks and P. F. Patel-schneider, Optimizing description logic subsumption, Journal of Logic and Computation, vol.9, issue.3, pp.267-293, 1999.
DOI : 10.1093/logcom/9.3.267

D. [. Kloks and . Kratsch, Listing all Minimal Separators of a Graph, SIAM Journal on Computing, vol.27, issue.3, pp.27605-613, 1998.
DOI : 10.1137/S009753979427087X

O. Kutz, C. Lutz, F. Wolter, and M. Zakharyaschev, E-connections of description logics, Proceedings of the International Workshop on Description Logics (DL- 2003), pp.178-187, 2003.

O. Kutz, F. Wolter, and M. Zakharyaschev, Connecting abstract description systems, Proceedings of the 8th Conference on Principles of Knowledge Representation and Reasoning, pp.215-226, 2002.

R. [. Levesque and . Brachman, Expressiveness and tractability in knowledge representation and reasoning, Computational Intelligence, vol.2, issue.2, pp.78-93, 1987.
DOI : 10.1016/0004-3702(84)90054-7

. [. Le-duc, Transformation d'Ontologies basées sur la Logique de Description -Application dans le Commerce Electronique, 2004.

R. Macgregor, The evolving technology of classification-based knowledge representation systems, Principles of Semantic Networks, pp.385-400, 1991.

F. Mazoit, Décompositions algorithmiques des graphes, 2004.

E. Mays, R. Dionne, and R. Weida, K-Rep system overview, ACM SIGART Bulletin, vol.2, issue.3, 1991.
DOI : 10.1145/122296.122310

]. M. Min75 and . Minsky, A framework for representing knowledge. The Psychology of Computer Vision, 1975.

]. B. Neb88 and . Nebel, Computational complexity of terminological reasoning in back, Journal of Artificial Intelligence, issue.3, pp.34371-383, 1988.

]. B. Neb90 and . Nebel, Teminological reasoning is inherently intractable, Artificial Intelligence, pp.235-249, 1990.

]. B. Neb91 and . Nebel, Terminological cycles : Semantics and computational properties, Principles of Semantic Networks, pp.331-362, 1991.

]. C. Pel91 and . Peltason, The back system -an overview, SIGART Bulletin, pp.114-119, 1991.

N. [. Pham and . Le-thanh, Decomposition-based reasoning for large knowledge bases in description logics, Proceedings of the 13th ISPE International Conference on Concurrent Engineering : Research and Applications, pp.288-295, 2006.

N. [. Pham and . Le-thanh, Some approaches of ontology decomposition in description logics, Proceedings of the 14th ISPE International Conference on Concurrent Engineering : Research and Applications, pp.534-542, 2007.

N. [. Pham, P. Thanh, and . Sander, Decomposition-based reasoning for large knowledge bases in description logics, Integrated Computer-Aided Engineering, vol.15, issue.1, pp.53-70, 2008.

T. Park and A. Van-gelder, Partitioning methods for satisfiability testing on large formulas, Proceedings 13th International Conference on Automated Deduction, pp.748-762, 1996.

]. M. Qui68 and . Quillian, Semantic memory, Semantic Information Processing, 1968.

L. Serafini, A. Borgida, and A. Tamilin, Aspects of distributed and modular ontology reasoning, IJCAI, pp.570-575, 2005.

D. [. Shoikhet and . Geiger, Finding optimal triangulations via minimal vertex separators, Proceedings of the 3rd International Conference, pp.270-281, 1992.

J. [. Shi and . Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, pp.888-905, 2000.

]. R. Smu68 and . Smullyan, First-order logic, 1968.

J. F. Sowa, Conceptural structures : Information processing in mind and machine, 1984.

A. Daniel and . Spielman, Spectral graph theory and its applications. Lecture, 2004.

G. [. Schmidt-schauß and . Smolka, Attributive concept descriptions with complements, Artificial Intelligence, vol.48, issue.1, pp.1-26, 1991.
DOI : 10.1016/0004-3702(91)90078-X

]. L. St04a, A. Serafini, and . Tamilin, Drago : Distributed reasoning architecture for the semantic web, 2004.

]. L. St04b, A. Serafini, and . Tamilin, Local tableaux for reasoning in distributed description logics, Description Logics Workshop, 2004.

D. Tsarkov, I. Horrocks, and P. F. Patel-schneider, Optimising terminological reasoning for expressive description logics, J. of Automated Reasoning, 2007.

]. I. Tod06 and . Todinca, Décompositions arborescentes de graphes : calcul, approximations, heuristiques. Habilitation à diriger des recherches, 2006.

M. [. Volot, M. Joubert, and . Fieschi, Review of biomedical knowledge and data representation with conceptual graphs, Methods of Information in Medicine, vol.37, issue.1, pp.86-96, 1998.

W. A. Woods, WHAT'S IN A LINK, pp.35-82, 1975.
DOI : 10.1016/B978-0-12-108550-6.50007-0