# Jakub Rydval

Research Associate

NameMr Jakub Rydval M.Sc.

Send encrypted mail via the SecureMail portal (for TUD external users only).

Visitor Address:

Andreas-Pfitzmann-Bau, Room 3030 Nöthnitzer Straße 46

01187 Dresden

## Multimedia

- IJCAR 2020 Conference Video: https://www.youtube.com/watch?v=yc_7czxMxKU
- LICS 2020 Conference Video: https://www.youtube.com/watch?v=pQHDK3UbbsQ

## In preparation

- Amalgamation is PSPACE-hard (with Manuel Bodirsky and Simon Knäuer) https://arxiv.org/abs/2108.00452

## Submitted

- On the Descriptive Complexity of Temporal Constraint Satisfaction Problems (with Manuel Bodirsky) https://arxiv.org/abs/2002.09451
- Tractable Combinations of Temporal CSPs (with Manuel Bodirsky and Johannes Greiner) https://arxiv.org/abs/2012.05682
- Universal Horn Sentences and the Joint Embedding Property (with Manuel Bodirsky and André Schrottenloher) https://arxiv.org/abs/2104.11123
- Using Model-Theory to Find Decidable and Tractable Description Logics with Concrete Domains (with Franz Baader)

## Publications

## 2021

**An Algebraic View on p-Admissible Concrete Domains for Lightweight Description Logics**. In Wolfgang Faber, Gerhard Friedrich, Martin Gebser, and Michael Morak, editors,

*Proceedings of the 17th European Conference on Logics in Artificial Intelligence (JELIA 2021)*, volume 12678 of

*Lecture Notes in Computer Science*, pages 194–209. Cham, Springer International Publishing, 2021.

Abstract BibTeX Entry PDF File ©Springer-Verlag

Concrete domains have been introduced in Description Logics (DLs) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. To retain decidability when integrating a concrete domain into a decidable DL, the domain must satisfy quite strong restrictions. In previous work, we have analyzed the most prominent such condition, called omega-admissibility, from an algebraic point of view. This provided us with useful algebraic tools for proving omega-admissibility, which allowed us to find new examples for concrete domains whose integration leaves the prototypical expressive DL ALC decidable. When integrating concrete domains into lightweight DLs of the EL family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. In the present paper, we investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical p-admissible concrete domain based on the rational numbers. Although omega-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields decidable DLs.

@inproceedings{ BaRy-JELIA-21, address = {Cham}, author = {Franz {Baader} and Jakub {Rydval}}, booktitle = {Proceedings of the 17th European Conference on Logics in Artificial Intelligence (JELIA 2021)}, editor = {Wolfgang {Faber} and Gerhard {Friedrich} and Martin {Gebser} and Michael {Morak}}, pages = {194--209}, publisher = {Springer International Publishing}, series = {Lecture Notes in Computer Science}, title = {An Algebraic View on p-Admissible Concrete Domains for Lightweight Description Logics}, volume = {12678}, year = {2021}, }

## 2020

**Description Logics with Concrete Domains and General Concept Inclusions Revisited**. In Viorica Sofronie-Stokkermans and Nicolas Peltier, editors,

*Proceedings of the International Joint Conference on Automated Reasoning (IJCAR 2020)*, volume 12166 of

*Lecture Notes in Computer Science*, pages 413–431. Springer, 2020.

Abstract BibTeX Entry PDF File DOI

Concrete domains have been introduced in the area of Description Logic to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability. One contribution of this paper is to strengthen the existing undecidability results further by showing that concrete domains even weaker than the ones considered in the previous proofs may cause undecidability. To regain decidability in the presence of GCIs, quite strong restrictions, in sum called omega-admissiblity, need to be imposed on the concrete domain. On the one hand, we generalize the notion of omega-admissiblity from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate omega-admissiblity to well-known notions from model theory. In particular, we show that finitely bounded, homogeneous structures yield omega-admissible concrete domains. This allows us to show omega-admissibility of concrete domains using existing results from model theory.

@inproceedings{ BaRy-IJCAR20, author = {Franz {Baader} and Jakub {Rydval}}, booktitle = {Proceedings of the International Joint Conference on Automated Reasoning ({IJCAR} 2020)}, doi = {https://dx.doi.org/10.1007/978-3-030-51074-9_24}, editor = {Viorica {Sofronie-Stokkermans} and Nicolas {Peltier}}, pages = {413--431}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Description Logics with Concrete Domains and General Concept Inclusions Revisited}, volume = {12166}, year = {2020}, }

**Description Logics with Concrete Domains and General Concept Inclusions Revisited (Extended Abstract)**. In Stefan Borgwardt and Thomas Meyer, editors,

*Proceedings of the 33rd International Workshop on Description Logics (DL'20)*, volume 2663 of

*CEUR Workshop Proceedings*. Online, CEUR-WS, 2020.

Abstract BibTeX Entry PDF File

Concrete domains have been introduced in the area of Description Logic to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability. One contribution of this paper is to strengthen the existing undecidability results further by showing that concrete domains even weaker than the ones considered in the previous proofs may cause undecidability. To regain decidability in the presence of GCIs, quite strong restrictions, in sum called omega-admissiblity, need to be imposed on the concrete domain. On the one hand, we generalize the notion of omega-admissiblity from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate omega-admissiblity to well-known notions from model theory. In particular, we show that finitely bounded, homogeneous structures yield omega-admissible concrete domains. This allows us to show omega-admissibility of concrete domains using existing results from model theory.

@inproceedings{ BaRy-DL-20, address = {Online}, author = {Franz {Baader} and Jakub {Rydval}}, booktitle = {Proceedings of the 33rd International Workshop on Description Logics (DL'20)}, editor = {Stefan {Borgwardt} and Thomas {Meyer}}, publisher = {CEUR-WS}, series = {CEUR Workshop Proceedings}, title = {Description Logics with Concrete Domains and General Concept Inclusions Revisited (Extended Abstract)}, volume = {2663}, year = {2020}, }

**Temporal Constraint Satisfaction Problems in Fixed-Point Logic**. In

*Proceedings of the Symposium on Logic in Computer Science (LICS 2020)*, pages 237–251. New York, NY, USA, Association for Computing Machinery, 2020.

Abstract BibTeX Entry PDF File PDF File (Extended Technical Report) DOI

Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q;<); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.

@inproceedings{ BoRy-LICS20, address = {New York, NY, USA}, author = {Manuel {Bodirsky} and Wied {Pakusa} and Jakub {Rydval}}, booktitle = {Proceedings of the Symposium on Logic in Computer Science ({LICS} 2020)}, doi = {https://dx.doi.org/10.1145/3373718.3394750}, pages = {237--251}, publisher = {Association for Computing Machinery}, title = {Temporal Constraint Satisfaction Problems in Fixed-Point Logic}, year = {2020}, }

Generated 21 October 2021, 19:15:41.

## Technical Reports

## 2020

**Using Model-Theory to Find**\(\omega\)

**-Admissible Concrete Domains**. LTCS-Report 20-01, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany, 2020.

Abstract BibTeX Entry PDF File

Concrete domains have been introduced in the area of Description Logic to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability. One contribution of this paper is to strengthen the existing undecidability results further by showing that concrete domains even weaker than the ones considered in the previous proofs may cause undecidability. To regain decidability in the presence of GCIs, quite strong restrictions, in sum called omega-admissiblity, need to be imposed on the concrete domain. On the one hand, we generalize the notion of omega-admissiblity from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate omega-admissiblity to well-known notions from model theory. In particular, we show that finitely bounded, homogeneous structures yield omega-admissible concrete domains. This allows us to show omega-admissibility of concrete domains using existing results from model theory.

@techreport{ BaRy-LTCS-20-01, address = {Dresden, Germany}, author = {Franz {Baader} and Jakub {Rydval}}, institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden}, number = {20-01}, title = {Using Model-Theory to Find $\omega$-Admissible Concrete Domains}, type = {LTCS-Report}, year = {2020}, }

**Temporal Constraint Satisfaction Problems in Fixed-Point Logic**. LTCS-Report 20-04, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany, 2020.

BibTeX Entry

@techreport{ BoPaRy-LTCS-20-04, address = {Dresden, Germany}, author = {Manuel {Bodirsky} and Wied {Pakusa} and Jakub {Rydval}}, institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden}, number = {20-04}, title = {Temporal Constraint Satisfaction Problems in Fixed-Point Logic}, type = {LTCS-Report}, year = {2020}, }

**An Algebraic View on p-Admissible Concrete Domains for Lightweight Description Logics (Extended Version)**. LTCS-Report 20-10, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany, 2020.

Abstract BibTeX Entry PDF File

Concrete domains have been introduced in Description Logics (DLs) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. To retain decidability when integrating a concrete domain into a decidable DL, the domain must satisfy quite strong restrictions. In previous work, we have analyzed the most prominent such condition, called omega-admissibility, from an algebraic point of view. This provided us with useful algebraic tools for proving omega-admissibility, which allowed us to find new examples for concrete domains whose integration leaves the prototypical expressive DL ALC decidable. When integrating concrete domains into lightweight DLs of the EL family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. In the present paper, we investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical p-admissible concrete domain based on the rational numbers. Although omega-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields decidable DLs.

@techreport{ BaRy-LTCS-20-10, address = {Dresden, Germany}, author = {Franz {Baader} and Jakub {Rydval}}, institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden}, number = {20-10}, title = {An Algebraic View on p-Admissible Concrete Domains for Lightweight Description Logics (Extended Version)}, type = {LTCS-Report}, year = {2020}, }

Generated 21 October 2021, 19:16:12.