Search

Your search keyword '"Kazakov, Yevgeny"' showing total 72 results
Start Over Author "Kazakov, Yevgeny"

Refine your results

more »

more »

more »

more »
72 results on '"Kazakov, Yevgeny"'

1. Description Logics Go Second-Order -- Extending EL with Universally Quantified Concepts

Author

Hirschbrunn, Joshua and Kazakov, Yevgeny

Subjects
Computer Science - Logic in Computer Science, Computer Science - Artificial Intelligence
Abstract

The study of Description Logics have been historically mostly focused on features that can be translated to decidable fragments of first-order logic. In this paper, we leave this restriction behind and look for useful and decidable extensions outside first-order logic. We introduce universally quantified concepts, which take the form of variables that can be replaced with arbitrary concepts, and define two semantics of this extension. A schema semantics allows replacements of concept variables only by concepts from a particular language, giving us axiom schemata similar to modal logics. A second-order semantics allows replacement of concept variables with arbitrary subsets of the domain, which is similar to quantified predicates in second-order logic. To study the proposed semantics, we focus on the extension of the description logic $\mathcal{EL}$. We show that for a useful fragment of the extension, the conclusions entailed by the different semantics coincide, allowing us to use classical $\mathcal{EL}$ reasoning algorithms even for the second-order semantics. For a slightly smaller, but still useful, fragment, we were also able to show polynomial decidability of the extension. This fragment, in particular, can express a generalized form of role chain axioms, positive self restrictions, and some forms of (local) role-value-maps from KL-ONE, without requiring any additional constructors.

Published
2023

2. On the Complexity of Semantic Integration of OWL Ontologies

Author

Kazakov, Yevgeny and Ponomaryov, Denis

Subjects
Computer Science - Artificial Intelligence
Abstract

We propose a new mechanism for integration of OWL ontologies using semantic import relations. In contrast to the standard OWL importing, we do not require all axioms of the imported ontologies to be taken into account for reasoning tasks, but only their logical implications over a chosen signature. This property comes natural in many ontology integration scenarios, especially when the number of ontologies is large. In this paper, we study the complexity of reasoning over ontologies with semantic import relations and establish a range of tight complexity bounds for various fragments of OWL.

Published
2017

3. Classical Algorithms for Reasoning and Explanation in Description Logics

Author

Glimm, Birte, Kazakov, Yevgeny, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Krötzsch, Markus, editor, and Stepanova, Daria, editor

Published
2019
Full Text
View/download PDF

4. A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Author

Kazakov, Yevgeny and Pratt-Hartmann, Ian

Subjects
Computer Science - Logic in Computer Science, Computer Science - Artificial Intelligence, Computer Science - Computational Complexity, F.4.1, F.2.2
Abstract

Graded modal logic is the formal language obtained from ordinary (propositional) modal logic by endowing its modal operators with cardinality constraints. Under the familiar possible-worlds semantics, these augmented modal operators receive interpretations such as "It is true at no fewer than 15 accessible worlds that...", or "It is true at no more than 2 accessible worlds that...". We investigate the complexity of satisfiability for this language over some familiar classes of frames. This problem is more challenging than its ordinary modal logic counterpart--especially in the case of transitive frames, where graded modal logic lacks the tree-model property. We obtain tight complexity bounds for the problem of determining the satisfiability of a given graded modal logic formula over the classes of frames characterized by any combination of reflexivity, seriality, symmetry, transitivity and the Euclidean property., Comment: Full proofs for paper presented at the IEEE Conference on Logic in Computer Science, 2009

Published
2009
Full Text
View/download PDF

5. Enumerating Justifications Using Resolution

Author

Kazakov, Yevgeny, Skočovský, Peter, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Galmiche, Didier, editor, Schulz, Stephan, editor, and Sebastiani, Roberto, editor

Published
2018
Full Text
View/download PDF

6. Scalable Reasoning by Abstraction Beyond DL-Lite

Author

Glimm, Birte, Kazakov, Yevgeny, Tran, Trung-Kien, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Ortiz, Magdalena, editor, and Schlobach, Stefan, editor

Published
2016
Full Text
View/download PDF

8. Goal-Directed Tracing of Inferences in EL Ontologies

Author

Kazakov, Yevgeny, Klinov, Pavel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Mika, Peter, editor, Tudorache, Tania, editor, Bernstein, Abraham, editor, Welty, Chris, editor, Knoblock, Craig, editor, Vrandečić, Denny, editor, Groth, Paul, editor, Noy, Natasha, editor, Janowicz, Krzysztof, editor, and Goble, Carole, editor

Published
2014
Full Text
View/download PDF

9. Abstraction Refinement for Ontology Materialization

Author

Glimm, Birte, Kazakov, Yevgeny, Liebig, Thorsten, Tran, Trung-Kien, Vialard, Vincent, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Mika, Peter, editor, Tudorache, Tania, editor, Bernstein, Abraham, editor, Welty, Chris, editor, Knoblock, Craig, editor, Vrandečić, Denny, editor, Groth, Paul, editor, Noy, Natasha, editor, Janowicz, Krzysztof, editor, and Goble, Carole, editor

Published
2014
Full Text
View/download PDF

10. Incremental Reasoning in OWL EL without Bookkeeping

Author

Kazakov, Yevgeny, Klinov, Pavel, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Alani, Harith, editor, Kagal, Lalana, editor, Fokoue, Achille, editor, Groth, Paul, editor, Biemann, Chris, editor, Parreira, Josiane Xavier, editor, Aroyo, Lora, editor, Noy, Natasha, editor, Welty, Chris, editor, and Janowicz, Krzysztof, editor

Published
2013
Full Text
View/download PDF

11. Concurrent Classification of Ontologies

Author

Kazakov, Yevgeny, Krötzsch, Markus, Simančík, František, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aroyo, Lora, editor, Welty, Chris, editor, Alani, Harith, editor, Taylor, Jamie, editor, Bernstein, Abraham, editor, Kagal, Lalana, editor, Noy, Natasha, editor, and Blomqvist, Eva, editor

Published
2011
Full Text
View/download PDF

14. Extracting Modules from Ontologies: A Logic-Based Approach

Author

Cuenca Grau, Bernardo, Horrocks, Ian, Kazakov, Yevgeny, Sattler, Ulrike, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Stuckenschmidt, Heiner, editor, Parent, Christine, editor, and Spaccapietra, Stefano, editor

Published
2009
Full Text
View/download PDF

17. History Matters: Incremental Ontology Reasoning Using Modules

Author

Cuenca Grau, Bernardo, Halaschek-Wiener, Christian, Kazakov, Yevgeny, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Aberer, Karl, editor, Choi, Key-Sun, editor, Noy, Natasha, editor, Allemang, Dean, editor, Lee, Kyung-Il, editor, Nixon, Lyndon, editor, Golbeck, Jennifer, editor, Mika, Peter, editor, Maynard, Diana, editor, Mizoguchi, Riichiro, editor, Schreiber, Guus, editor, and Cudré-Mauroux, Philippe, editor

Published
2007
Full Text
View/download PDF

19. A Resolution-Based Decision Procedure for

Author

Kazakov, Yevgeny, Motik, Boris, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Furbach, Ulrich, editor, and Shankar, Natarajan, editor

Published
2006
Full Text
View/download PDF

20. A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment

Author

Kazakov, Yevgeny, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Alferes, Jóse Júlio, editor, and Leite, João, editor

Published
2004
Full Text
View/download PDF

21. A Resolution Decision Procedure for the Guarded Fragment with Transitive Guards

Author

Kazakov, Yevgeny, de Nivelle, Hans, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Basin, David, editor, and Rusinowitch, Michaël, editor

Published
2004
Full Text
View/download PDF

44. Just the right amount

Author

Grau, Bernardo Cuenca, primary, Horrocks, Ian, additional, Kazakov, Yevgeny, additional, and Sattler, Ulrike, additional

Published
2007
Full Text
View/download PDF

45. Tractable Extensions of the Description Logic $\CAL EL$ with Numerical Datatypes.

Author

Magka, Despoina, Kazakov, Yevgeny, and Horrocks, Ian

Abstract

We consider extensions of the lightweight description logic (DL) ]> with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decidable in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left-hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractability, extend the ]> reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, rationals and reals. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

46. How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited.

Author

Carbonell, Jaime G., Siekmann, Jörg, Dershowitz, Nachum, Voronkov, Andrei, Kazakov, Yevgeny, Sattler, Ulrike, and Zolin, Evgeny

Abstract

The Description Logics underpinning OWL impose a well-known syntactic restriction in order to preserve decidability: they do not allow to use non-simple roles—that is, transitive roles or their super-roles—in number restrictions. When modeling composite objects, for example in bio-medical ontologies, this restriction can pose problems.X Therefore, we take a closer look at the problem of counting over non-simple roles. On the one hand, we sharpen the known undecidability results and demonstrate that: (i) for DLs with inverse roles, counting over non-simple roles leads to undecidability even when there is only one role in the language; (ii) for DLs without inverses, two transitive and an arbitrary role are sufficient for undecidability. On the other hand, we demonstrate that counting over non-simple roles does not compromise decidability in the absence of inverse roles provided that certain restrictions on role inclusion axioms are satisfied. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

47. A Resolution-Based Decision Procedure for $\mathcal{SHOIQ}$.

Author

Furbach, Ulrich, Shankar, Natarajan, Kazakov, Yevgeny, and Motik, Boris

Abstract

We present a resolution-based decision procedure for the description logic $\mathcal{SHOIQ}$ — the logic underlying the Semantic Web ontology language $\mathcal{OWLDL}$. Our procedure is goal-oriented, and it naturally extends a similar procedure for $\mathcal{SHIQ}$, which has proven itself in practice. Applying existing techniques for deriving saturation-based decision procedures to $\mathcal{SHOIQ}$ is not straightforward due to nominals, number restrictions, and inverse roles—a combination known to cause termination problems. We overcome this difficulty by using the basic superposition calculus, extended with custom simplification rules. [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

48. The Incredible ELK.

Author

Kazakov, Yevgeny, Krötzsch, Markus, and Simančík, František

Subjects
DESCRIPTION logics, ONTOLOGY, SELF-expression, LANGUAGE & languages, COMPLEXITY (Philosophy), ASSIMILATION theory (Cognitive learning theory)
Abstract

$\mathcal {E} \mathcal {L}$ is a simple tractable Description Logic that features conjunctions and existential restrictions. Due to its favorable computational properties and relevance to existing ontologies, $\mathcal {E} \mathcal {L}$ has become the language of choice for terminological reasoning in biomedical applications, and has formed the basis of the OWL EL profile of the Web ontology language OWL. This paper describes ELK-a high performance reasoner for OWL EL ontologies-and details various aspects from theory to implementation that make ELK one of the most competitive reasoning systems for $\mathcal {E} \mathcal {L}$ ontologies available today. [ABSTRACT FROM AUTHOR]

Published
2014
Full Text
View/download PDF

49. Incremental Classification of Description Logics Ontologies.

Author

Grau, Bernardo Cuenca, Halaschek-Wiener, Christian, Kazakov, Yevgeny, and Suntisrivaraporn, Boontawee

Subjects
CLASSIFICATION, DESCRIPTION logics, KNOWLEDGE representation (Information theory), PREDICATE (Logic), ONTOLOGIES (Information retrieval)
Abstract

The article presents the development of algorithms and optimization techniques for use in incremental reasoning and classifying ontologies. The authors define incremental reasoning that reuses information gathered from previous versions of an ontology. They mention that the techniques do not rely on a specific reasoner or reasoning approach and can be executed by utilizing any existing reasoner. The authors present the results of applying the techniques to incremental classification of Web Ontology Language (OWL) ontologies.

Published
2010
Full Text
View/download PDF

50. Modular Reuse of Ontologies: Theory and Practice.

Author

Grau, Bernardo Cuenca, Horrocks, Ian, Kazakov, Yevgeny, and Sattler, Ulrike

Subjects
ONTOLOGY, REASONING, LANGUAGE & languages, DESCRIPTION logics, MODULARITY (Psychology), ALGORITHMS
Abstract

In this paper, we propose a set of tasks that are relevant for the modular reuse of ontologies. In order to formalize these tasks as reasoning problems, we introduce the notions of conservative extension, safety and module for a very general class of logic-based ontology languages. We investigate the general properties of and relationships between these notions and study the relationships between the relevant reasoning problems we have previously identified. To study the computability of these problems, we consider, in particular, Description Logics (DLs), which provide the formal underpinning of the W3C Web Ontology Language (OWL), and show that all the problems we consider are undecidable or algorithmically unsolvable for the description logic underlying OWL DL. In order to achieve a practical solution, we identify conditions sufficient for an ontology to reuse a set of symbols "safely"--that is, without changing their meaning. We provide the notion of a safety class, which characterizes any sufficient condition for safety, and identify a family of safety classes-called locality--which enjoys a collection of desirable properties. We use the notion of a safety class to extract modules from ontologies, and we provide various modularization algorithms that are appropriate to the properties of the particular safety class in use. Finally, we show practical benefits of our safety checking and module extraction algorithms. [ABSTRACT FROM AUTHOR]

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results