The Experts below are selected from a list of 74013 Experts worldwide ranked by ideXlab platform
Michael Zakharyaschev - One of the best experts on this subject based on the ideXlab platform.
-
Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey.
Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering, 2017Co-Authors: Elena Botoeva, Frank Wolter, Boris Konev, Vladislav Ryzhikov, Carsten Lutz, Michael ZakharyaschevAbstract:The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What safe replacement means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology Inseparability such as query Inseparability and concept Inseparability, which generalize corresponding notions of conservative extensions. We survey results on various notions of Inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.
-
Inseparability and conservative extensions of description logic ontologies a survey
Reasoning Web International Summer School, 2016Co-Authors: Elena Botoeva, Frank Wolter, Boris Konev, Vladislav Ryzhikov, Carsten Lutz, Michael ZakharyaschevAbstract:The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What ‘safe replacement’ means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology Inseparability such as query Inseparability and concept Inseparability, which generalize corresponding notions of conservative extensions. In this chapter, we survey results on various notions of Inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.
-
Games for query Inseparability of description logic knowledge bases
Artificial Intelligence, 2016Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We consider conjunctive query Inseparability of description logic knowledge bases with respect to a given signature-a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query Inseparability and develop worst-case optimal decision algorithms for fragments of Horn- ALCHI , including the description logics underpinning OWL?2?QL and OWL?2?EL. We also determine the data and combined complexity of deciding query Inseparability. While query Inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL?2?QL by showing that TBox query Inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of Inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query Inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.
-
KR - Query Inseparability for description logic knowledge bases
2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query Inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL2QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL2QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.
-
Description Logics - Query Inseparability by games
Description Logics, 2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query Inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to ExpTime and 2ExpTime. We also employ our results to resolve two major open problems for OWL 2 QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both ExpTime-complete for combined complexity.
Frank Wolter - One of the best experts on this subject based on the ideXlab platform.
-
Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey.
Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering, 2017Co-Authors: Elena Botoeva, Frank Wolter, Boris Konev, Vladislav Ryzhikov, Carsten Lutz, Michael ZakharyaschevAbstract:The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What safe replacement means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology Inseparability such as query Inseparability and concept Inseparability, which generalize corresponding notions of conservative extensions. We survey results on various notions of Inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.
-
Inseparability and conservative extensions of description logic ontologies a survey
Reasoning Web International Summer School, 2016Co-Authors: Elena Botoeva, Frank Wolter, Boris Konev, Vladislav Ryzhikov, Carsten Lutz, Michael ZakharyaschevAbstract:The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What ‘safe replacement’ means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology Inseparability such as query Inseparability and concept Inseparability, which generalize corresponding notions of conservative extensions. In this chapter, we survey results on various notions of Inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.
-
Games for query Inseparability of description logic knowledge bases
Artificial Intelligence, 2016Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We consider conjunctive query Inseparability of description logic knowledge bases with respect to a given signature-a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query Inseparability and develop worst-case optimal decision algorithms for fragments of Horn- ALCHI , including the description logics underpinning OWL?2?QL and OWL?2?EL. We also determine the data and combined complexity of deciding query Inseparability. While query Inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL?2?QL by showing that TBox query Inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of Inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query Inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.
-
KR - Query Inseparability for description logic knowledge bases
2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query Inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL2QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL2QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.
-
Description Logics - Query Inseparability by games
Description Logics, 2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query Inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to ExpTime and 2ExpTime. We also employ our results to resolve two major open problems for OWL 2 QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both ExpTime-complete for combined complexity.
Ryszard Horodecki - One of the best experts on this subject based on the ideXlab platform.
-
Inseparability criteria based on matrices of moments
Physical Review A, 2009Co-Authors: Adam Miranowicz, Pawel Horodecki, Marco Piani, Ryszard HorodeckiAbstract:Inseparability criteria for continuous and discrete bipartite quantum states based on moments of annihilation and creation operators are studied by developing the idea of Shchukin-Vogel criterion [Phys. Rev. Lett. 95, 230502 (2005)]. If a state is separable, then the corresponding matrix of moments is separable too. Thus, we derive generalized criteria based on the separability properties of the matrix of moments. In particular, a criterion based on realignment of moments in the matrix is proposed as an analog of the standard realignment criterion for density matrices. Other Inseparability inequalities are obtained by applying positive maps to the matrix of moments. Usefulness of the Shchukin-Vogel criterion to describe bipartite-entanglement of more than two modes is demonstrated: we obtain various three-mode Inseparability criteria, including some previously known ones, which were originally derived from the Cauchy-Schwarz inequality.
-
Information-theoretic aspects of Inseparability of mixed states
Physical review. A Atomic molecular and optical physics, 1996Co-Authors: Ryszard Horodecki, Michal HorodeckiAbstract:Information-theoretic aspects of quantum Inseparability of mixed states are investigated in terms of the \ensuremath{\alpha} entropy inequalities and teleportation fidelity. Inseparability of mixed states is defined and a complete characterization of the inseparable 2\ifmmode\times\else\texttimes\fi{}2 systems with maximally disordered subsystems is presented within the Hilbert-Schmidt space formalism. A connection between teleportation and negative conditional \ensuremath{\alpha} entropy is also emphasized. \textcopyright{} 1996 The American Physical Society.
-
Distillability of Inseparable Quantum Systems
arXiv: Quantum Physics, 1996Co-Authors: Michal Horodecki, Pawel Horodecki, Ryszard HorodeckiAbstract:We apply the Inseparability criterion for $2 \times 2$ systems, local filtering and Bennett et al. purification protocol [Phys. Rev. Lett. {\bf 76}, 722 (1996)] to show how to distill {\it any} inseparable $2\times 2$ system. The extended protocol is illustrated geometrically by means of the state parameters in the Hilbert-Schmidt space.
-
Teleportation, Bell's inequalities and Inseparability
Physics Letters Section A: General Atomic and Solid State Physics, 1996Co-Authors: Ryszard Horodecki, Michal Horodecki, Pawel HorodeckiAbstract:Relations between teleportation, Bell's inequalities and Inseparability are investigated. It is shown that any mixed two spin-1/2 state which violates the Bell-CHSH inequality is useful for teleportation. The result is extended to any Bell's inequalities constructed from the expectation values of products of spin operators. It is also shown that there exist inseparable states which are not useful for teleportation within the standard scheme.
-
Teleportation, Bell's Inequalities and Inseparability
Physics Letters A, 1996Co-Authors: Ryszard Horodecki, Michal Horodecki, Pawel HorodeckiAbstract:Relations between teleportation, Bell's inequalities and Inseparability are investigated. It is shown that any mixed two spin-$1\over2$ state which violates the Bell-CHSH inequality is useful for teleportation. The result is extended to any Bell's inequalities constructed of the expectation values of products of spin operators. It is also shown that there exist inseparable states which are not useful for teleportation within the standard scheme.
Pawel Horodecki - One of the best experts on this subject based on the ideXlab platform.
-
Inseparability criteria based on matrices of moments
Physical Review A, 2009Co-Authors: Adam Miranowicz, Pawel Horodecki, Marco Piani, Ryszard HorodeckiAbstract:Inseparability criteria for continuous and discrete bipartite quantum states based on moments of annihilation and creation operators are studied by developing the idea of Shchukin-Vogel criterion [Phys. Rev. Lett. 95, 230502 (2005)]. If a state is separable, then the corresponding matrix of moments is separable too. Thus, we derive generalized criteria based on the separability properties of the matrix of moments. In particular, a criterion based on realignment of moments in the matrix is proposed as an analog of the standard realignment criterion for density matrices. Other Inseparability inequalities are obtained by applying positive maps to the matrix of moments. Usefulness of the Shchukin-Vogel criterion to describe bipartite-entanglement of more than two modes is demonstrated: we obtain various three-mode Inseparability criteria, including some previously known ones, which were originally derived from the Cauchy-Schwarz inequality.
-
Distillability of Inseparable Quantum Systems
arXiv: Quantum Physics, 1996Co-Authors: Michal Horodecki, Pawel Horodecki, Ryszard HorodeckiAbstract:We apply the Inseparability criterion for $2 \times 2$ systems, local filtering and Bennett et al. purification protocol [Phys. Rev. Lett. {\bf 76}, 722 (1996)] to show how to distill {\it any} inseparable $2\times 2$ system. The extended protocol is illustrated geometrically by means of the state parameters in the Hilbert-Schmidt space.
-
Teleportation, Bell's inequalities and Inseparability
Physics Letters Section A: General Atomic and Solid State Physics, 1996Co-Authors: Ryszard Horodecki, Michal Horodecki, Pawel HorodeckiAbstract:Relations between teleportation, Bell's inequalities and Inseparability are investigated. It is shown that any mixed two spin-1/2 state which violates the Bell-CHSH inequality is useful for teleportation. The result is extended to any Bell's inequalities constructed from the expectation values of products of spin operators. It is also shown that there exist inseparable states which are not useful for teleportation within the standard scheme.
-
Teleportation, Bell's Inequalities and Inseparability
Physics Letters A, 1996Co-Authors: Ryszard Horodecki, Michal Horodecki, Pawel HorodeckiAbstract:Relations between teleportation, Bell's inequalities and Inseparability are investigated. It is shown that any mixed two spin-$1\over2$ state which violates the Bell-CHSH inequality is useful for teleportation. The result is extended to any Bell's inequalities constructed of the expectation values of products of spin operators. It is also shown that there exist inseparable states which are not useful for teleportation within the standard scheme.
Roman Kontchakov - One of the best experts on this subject based on the ideXlab platform.
-
Games for query Inseparability of description logic knowledge bases
Artificial Intelligence, 2016Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We consider conjunctive query Inseparability of description logic knowledge bases with respect to a given signature-a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query Inseparability and develop worst-case optimal decision algorithms for fragments of Horn- ALCHI , including the description logics underpinning OWL?2?QL and OWL?2?EL. We also determine the data and combined complexity of deciding query Inseparability. While query Inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL?2?QL by showing that TBox query Inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of Inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query Inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.
-
KR - Query Inseparability for description logic knowledge bases
2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query Inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL2QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL2QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.
-
Description Logics - Query Inseparability by games
Description Logics, 2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query Inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to ExpTime and 2ExpTime. We also employ our results to resolve two major open problems for OWL 2 QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both ExpTime-complete for combined complexity.
-
query Inseparability by games
Description Logics, 2014Co-Authors: Elena Botoeva, Frank Wolter, Roman Kontchakov, Vladislav Ryzhikov, Michael ZakharyaschevAbstract:We investigate conjunctive query Inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query Inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to ExpTime and 2ExpTime. We also employ our results to resolve two major open problems for OWL 2 QL by showing that TBox query Inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both ExpTime-complete for combined complexity.
-
conjunctive query Inseparability of owl 2 ql tboxes
National Conference on Artificial Intelligence, 2011Co-Authors: Boris Konev, Frank Wolter, Roman Kontchakov, Michel Ludwig, Thomas Schneider, Michael ZakharyaschevAbstract:The OWL 2 profile OWL 2 QL, based on the DL-Lite family of description logics, is emerging as a major language for developing new ontologies and approximating the existing ones. Its main application is ontology-based data access, where ontologies are used to provide background knowledge for answering queries over data. We investigate the corresponding notion of query Inseparability (or equivalence) for OWL 2 QL ontologies and show that deciding query Inseparability is PSPACE-hard and in EXPTIME. We give polynomial time (incomplete) algorithms and demonstrate by experiments that they can be used for practical module extraction.
