BEGIN:VCALENDAR
PRODID:-//SMW Project//Semantic Result Formats
VERSION:2.0
METHOD:PUBLISH
X-WR-CALNAME:ICCL-Veranstaltungen
X-WR-CALDESC:
BEGIN:VEVENT
SUMMARY:Temporal reasoning with DatalogMTL
URL://iccl.inf.tu-dresden.de/web/Temporal_reasoning_with_DatalogMTL
UID://iccl.inf.tu-dresden.de/web/Temporal_reasoning_with_DatalogMTL
DTSTART:20230919T110000
DTEND:20230919T120000
LOCATION:APB room 2026
DESCRIPTION:Abstract: During the talk\, I will present DatalogMTL – an extension of Datalog with operators from metric temporal logic (MTL) – and our research on this formalism. DatalogMTL allows for performing complex temporal reasoning tasks over the rational timeline\, which makes it suitable for many practical applications. However\, performing the main reasoning tasks in this setting is computationally expensive\, e.g.\, fact entailment is EXPSPACE-complete in combined and PSPACE-complete in data complexity. High complexity\, together with the need of performing reasoning over infinite temporal structures\, makes developing practical algorithms for DatalogMTL challenging. I will describe our approaches to address these difficulties\, and discuss their experimental evaluation.\n\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 2026\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230918T130921
SEQUENCE:38715
END:VEVENT
BEGIN:VEVENT
SUMMARY:Representative Answer Sets: Collecting Something of Everything
URL://iccl.inf.tu-dresden.de/web/Representative_Answer_Sets:_Collecting_Something_of_Everything
UID://iccl.inf.tu-dresden.de/web/Representative_Answer_Sets:_Collecting_Something_of_Everything
DTSTART:20230914T110000
DTEND:20230914T120000
LOCATION:APB room 3027
DESCRIPTION:Title: Representative Answer Sets: Collecting Something of Everything\n\nAbstract: Answer set programming (ASP) is a popular problem\nsolving paradigm with applications in planning and configuration.\nIn practice\, the number of answer sets can be overwhelmingly high\,\nwhich naturally causes interest in a concise characterisation of the\nsolution space in terms of representative answer sets. We establish\na notion of representativeness that refers to the entropy of specified\ntarget atoms within a collection of answer sets. Accordingly\, we pro-\npose different approaches for collecting such representative answer\nsets\, based on answer set navigation. Finally\, we conduct experi-\nments using our prototypical implementation\, which reveals promis-\ning results.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230911T151551
SEQUENCE:38697
END:VEVENT
BEGIN:VEVENT
SUMMARY:Formalizing "Formale Systeme"
URL://iccl.inf.tu-dresden.de/web/Formalizing_%22Formale_Systeme%22
UID://iccl.inf.tu-dresden.de/web/Formalizing_%22Formale_Systeme%22
DTSTART:20230831T110000
DTEND:20230831T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: In undergraduate theoretical computer science courses\, students\nencounter many new concepts along with techniques to prove theorems\nabout those with mathematical rigour. Most of those definitions and\nproofs are both constructive in nature and fairly self contained\, since\nthey depend on only very few mathematical facts. This makes formalising\nthem in an automated theorem prover feasible and educational. The\nobjective of this project was to formalize a subset of the two lectures\n"Formale Systeme" and "Theoretische Informatik und Logik"\, serving both\nas a reference for students and as a starting point for future\nformalisations.\n\nThe LEAN theorem prover and programming language is a project under\nactive development with a large\, community maintained library of\nmathematical definitions and theorems called "mathlib". This makes it a\ngood fit for formalising the undergraduate computer science lectures.\nLEAN also incorporates interesting and convenient features\, notably a\nHaskell inspired type class resolution\, a first-class support for\nquotients and the ability to very easily extend the language with new\nnotations or tactics.\n\nWhile there has already been some effort to formalizing "Formale\nSysteme"\, most has been reimplemented to make the definitions easier to\nwork with\, taking special care to end up with small and reusable proofs.\nOverall the focus has been on regular languages\, where the equivalence\nof DFAs\, NFAs and regular grammars among each other is the major\nimplemented result.\n\nIn this talk I will give a short introduction to LEAN and outline the\ndefinitions and theorems that have been formalized as a part of this\nproject.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230825T155022
SEQUENCE:38609
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Abstract Expressive Power of Description Logics with Concrete Domains
URL://iccl.inf.tu-dresden.de/web/On_the_Abstract_Expressive_Power_of_Description_Logics_with_Concrete_Domains
UID://iccl.inf.tu-dresden.de/web/On_the_Abstract_Expressive_Power_of_Description_Logics_with_Concrete_Domains
DTSTART:20230824T110000
DTEND:20230824T120000
LOCATION:APB room 3027
DESCRIPTION:The talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus\n\nAbstract: Concrete domains have been introduced in Description Logic (DL) to\nenable reference to concrete objects (such as numbers) and predefined\npredicates on these objects (such as numerical comparisons) when\ndefining concepts. The main emphasis of research in this context was on\nfinding restrictions on the concrete domain such that its integration\ninto certain DLs preserves decidability. In particular\, it was shown\nthat ω-admissible concrete domains can be integrated into the DL ALC\nwithout causing undecidability.\n\nIn this paper\, we concentrate on investigating the expressive power of\nDLs with concrete domains. Basically\, their semantics is defined using\nfirst-order interpretations as abstract domains extended with partial\nfunctions from the abstract domain into the concrete domain.\nThe abstract expressive power of a given classical logic (first-order\nlogic or DL) extended with a concrete domain is determined by which\nclasses of first-order interpretations (i.e.\, abstract domains where we\nforget the partial functions and their values) can be expressed.\n\nTo show that such a class is not first-order definable\, one can try to\nuse a compactness argument\, i.e.\, prove that first-order definability\nwould lead to a contradiction to compactness of first-order logic (FO).\nIn the first part of the paper\, we will show that extensions of FO or\nALC with a homomorphism ω-compact concrete domain share many formal\nproperties with FO\, such as the compactness and the downward\nLöwenheim-Skolem property. Nevertheless\, their abstract expressive power\nneed not be contained in that of FO. Note that any ω-admissible concrete\ndomain is homomorphism ω-compact.\n\nIn the second part of the paper\, we investigate whether finitely-bounded\nhomogeneous structures\, which preserve decidability if employed as\nconcrete domains\, can be used to express certain universal first-order\nsentences\, which then could be added to knowledge bases without\ndestroying decidability. We will see that this requires rather strong\nconditions on the universal first-order sentences or an extended scheme\nfor integrating the concrete domain.
DTSTAMP:20230821T104147
SEQUENCE:38603
END:VEVENT
BEGIN:VEVENT
SUMMARY:Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination
URL://iccl.inf.tu-dresden.de/web/Do_Repeat_Yourself:_Understanding_Sufficient_Conditions_for_Restricted_Chase_Non-Termination
UID://iccl.inf.tu-dresden.de/web/Do_Repeat_Yourself:_Understanding_Sufficient_Conditions_for_Restricted_Chase_Non-Termination
DTSTART:20230727T110000
DTEND:20230727T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: The disjunctive restricted chase is a sound and complete procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. Alas\, this procedure does not always terminate and checking if it does is undecidable. However\, we can use acyclicity notions (sufficient conditions that imply termination) to effectively apply the chase in many real-world cases. To know if these conditions are as general as possible\, we can use cyclicity notions (sufficient conditions that imply non-termination). In this paper\, we discuss some issues with previously existing cyclicity notions\, propose some novel notions for non-termination by dismantling the original idea\, and empirically verify the generality of the new criteria.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230724T172459
SEQUENCE:38568
END:VEVENT
BEGIN:VEVENT
SUMMARY:How I made my research more VISIBLE? Undecidability Results for ALC Extended with Visibly Pushdown Path Expressions.
URL://iccl.inf.tu-dresden.de/web/How_I_made_my_research_more_VISIBLE%3F_Undecidability_Results_for_ALC_Extended_with_Visibly_Pushdown_Path_Expressions.
UID://iccl.inf.tu-dresden.de/web/How_I_made_my_research_more_VISIBLE%3F_Undecidability_Results_for_ALC_Extended_with_Visibly_Pushdown_Path_Expressions.
DTSTART:20230713T110000
DTEND:20230713T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: We investigate the impact of non-regular path expressions on the decidability of satisfiability checking and querying in description logics. Our primary object of interest is ALCvpl\, an extension of ALC with path expressions using visibly-pushdown languages\, which was shown to be decidable by Löding et al. in 2007. We prove that decidability of ALCvpl is preserved when enriching the logic with functionality\, but decidability is lost upon adding the seemingly innocent Self operator. We also consider the simplest non-regular (visibly-pushdown) language r#s# := {r^n s^n : n ∈ N}. We establish undecidability of the satisfiability problem for ALC extended with nominals and r#s#\, as well as the query entailment problem\, where such non-regular atoms are present in queries.\nThis work is based on the paper accepted to JELIA 2023\, which is going to be submitted to Logical Methods in Computer Science next week.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230710T192135
SEQUENCE:38488
END:VEVENT
BEGIN:VEVENT
SUMMARY:Investigating the finite-cliquewidth-model property of C².
URL://iccl.inf.tu-dresden.de/web/Navigating_ASP_Solution_Spaces
UID://iccl.inf.tu-dresden.de/web/Navigating_ASP_Solution_Spaces
DTSTART:20230706T110000
DTEND:20230706T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: I will try to explain to you the results of my internship on 2-variable logics (with counters) and how it interfaces with the cliquewidth notion. \n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230706T073233
SEQUENCE:38479
END:VEVENT
BEGIN:VEVENT
SUMMARY:To Lead or to be Led: A Generalized Condorcet Jury Theorem under Dependence
URL://iccl.inf.tu-dresden.de/web/To_Lead_or_to_be_Led:_A_Generalized_Condorcet_Jury_Theorem_under_Dependence
UID://iccl.inf.tu-dresden.de/web/To_Lead_or_to_be_Led:_A_Generalized_Condorcet_Jury_Theorem_under_Dependence
DTSTART:20230629T110000
DTEND:20230609T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: Aggregating pieces of information or beliefs held by (abstract) agents is central to a variety of belief merging applications. When the merging process aims at retrieving an underlying ground truth\, the Condorcet Jury Theorem (CJT) allows identifying voting rules that almost surely track the true piece of information for large groups of agents\, given that specific conditions are met. As essential assumptions\, the CJT relies on all agents being equally competent as well as independent from one another. In the search for a generalization of the CJT applicable to real-world scenarios\, both aforementioned assumptions were weakened separately. In this work\, we provide a generalization of the CJT that allows\, at the same time\, for heterogeneous competence levels across agents as well as a degree of dependence modeled through an opinion leader exerting influence on the electorate. Additionally\, we derive a concrete bound on the number of agents necessary to successfully track the underlying ground truth\, and examine the bound's tightness by means of statistical simulations.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230623T151719
SEQUENCE:38412
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deontic Explanations via Logical Argumentation.
URL://iccl.inf.tu-dresden.de/web/Deontic_Explanations_via_Logical_Argumentation.
UID://iccl.inf.tu-dresden.de/web/Deontic_Explanations_via_Logical_Argumentation.
DTSTART:20230615T110000
DTEND:20230615T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: In many normative reasoning contexts\, one is not merely interested in knowing whether an obligation holds\, but also in why it holds despite other norms to the contrary. Answers to such why questions are deontic explanations. They not only lead to a better understanding of normative reasoning\, they also motivate compliance and collaboration. The importance of such explanations increases with the development of AI systems that need to comply with normative codes. The study of explanation is growing rapidly but\, so far\, little to no formal work has been done in the intersection of explanation and normative reasoning. What is more\, existing approaches in deontic logic do not make explicit the reasons why certain obligations do and do not hold given a normative system\, and are\, therefore\, not yet suitable for deontic explanations. In collaboration with Christian Strasser\, we developed Deontic Argumentation Calculi (DAC): Sequent-style proof systems tailored to the construction of deontic explanations. DAC generate transparent arguments that provide explicit reasons why certain obligations hold and why certain norms are inapplicable. We prove that Formal Argumentation (FA) frameworks instantiated with DAC arguments are sound and complete with respect to the nonmonotonic inference relation of the class of constrained Input/Output (I/O) logics\, a renowned formalism for defeasible reasoning with norms and their conflicts. We demonstrate how to employ DAC to generate deontic explanations using general tools from the FA literature. In particular\, we use these tools to generate deontic explanations as answers to contrastive questions of the form “Why am I obliged to ϕ\, despite ψ?”\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230613T100051
SEQUENCE:38351
END:VEVENT
BEGIN:VEVENT
SUMMARY:Querying Wikidata with GraphQL
URL://iccl.inf.tu-dresden.de/web/Querying_Wikidata_with_GraphQL
UID://iccl.inf.tu-dresden.de/web/Querying_Wikidata_with_GraphQL
DTSTART:20230608T110000
DTEND:20230608T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: Knowledge graphs like Wikidata are widely used in commercial and\nresearch domains. They represent knowledge that conveys information\nabout the real world in the form of graphs. Often they are modelled\nusing directed-edge labelled graphs using the Resource Description\nFramework (RDF). RDF is a framework that represents information in the\nform of Linked Data. SPARQL is a protocol and query language for RDF. It\nis based on matching graph patterns and is used to query RDF graphs.\nSPARQL is a powerful query language as it is expressive\, and provides\nmany features to retrieve and manipulate data. However\, SPARQL queries\nare complex in nature and have a steep learning curve. There are few\ntools and libraries available to developers for working with SPARQL.\nGraphQL is a popular query language for working with APIs. It is a\nflexible query language and is designed to have a human-oriented syntax.\nThis makes it easy for developers to learn and implement it in\napplications. Moreover\, there are many supporting resources that help\nthe integration of GraphQL into the development of such systems.\n\nThe purpose of our work is to show ways of querying the knowledge graph\,\nWikidata\, using GraphQL queries. This helps avoid the complexity of\ndealing with SPARQL queries\, and makes use of the flexibility and\nfeatures offered by GraphQL. In this work\, we show some key differences\nbetween GraphQL and SPARQL. We show some existing commercial and\nopen-source solutions to query RDF data via GraphQL. Our main focus is\nto introduce two existing open-source solutions\, GraphQL-LD and\nHyperGraphQL\, that can be used to query Wikidata via GraphQL queries.\nBoth these approaches use GraphQL queries to act as layer of abstraction\nthat hides the complexity of SPARQL queries. We show extensively how\nthese approaches operate and the respective features that they offer. We\nprovide details on how we can use GraphQL-LD and HyperGraphQL to fetch\ndata from Wikidata and demonstrate the results. Since they are\nopen-source\, we made appropriate changes to the source code to implement\nthe approaches on Wikidata. The changes were also made to help analyse\nthe steps in the implementation and facilitate querying. Our results\nshow that some key differences between GraphQL-LD and HyperGraphQL exist\nin terms of implementation and features. We demonstrate these in this\nwork extensively and compare them via examples against standard GraphQL\nand SPARQL features.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230605T112940
SEQUENCE:38277
END:VEVENT
BEGIN:VEVENT
SUMMARY:Database-Inspired Reasoning Problems in Description Logics With Path Expressions
URL://iccl.inf.tu-dresden.de/web/Database-Inspired_Reasoning_Problems_in_Description_Logics_With_Path_Expressions
UID://iccl.inf.tu-dresden.de/web/Database-Inspired_Reasoning_Problems_in_Description_Logics_With_Path_Expressions
DTSTART:20230601T110000
DTEND:20230601T120000
LOCATION:APB room 3027
DESCRIPTION:This is a status talk (i.e. pre-PHD-defense talk) for the ongoing PHD thesis of Bartosz Bednarczyk\, supervised by Sebastian Rudolph (TU Dresden) and Emanuel Kieroński (University of Wrocław). The main goal of the thesis is to study database-inspired reasoning problems (e.g. satisfiability\, query entailment or query containment problems) for the very expressive family Z of description logics.\n\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230529T143105
SEQUENCE:38255
END:VEVENT
BEGIN:VEVENT
SUMMARY:Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures
URL://iccl.inf.tu-dresden.de/web/Decidable_(Ac)counting_with_Parikh_and_Muller:_Adding_Presburger_Arithmetic_to_Monadic_Second-Order_Logic_over_Tree-Interpretable_Structures
UID://iccl.inf.tu-dresden.de/web/Decidable_(Ac)counting_with_Parikh_and_Muller:_Adding_Presburger_Arithmetic_to_Monadic_Second-Order_Logic_over_Tree-Interpretable_Structures
DTSTART:20230525T110000
DTEND:20230525T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: We propose ωMSO⋈BAPA\, an expressive logic for describing countable structures\, which subsumes and transcends both Counting Monadic Second-Order Logic (CMSO) and Boolean Algebra with Presburger Arithmetic (BAPA). We show that satisfiability of ωMSO⋈BAPA is decidable over the class of labeled infinite binary trees. This result is established by an elaborate multi-step transformation into a particular normal form\, followed by the deployment of Parikh-Muller Tree Automata\, a novel kind of automaton for infinite labeled binary trees\, integrating and generalizing both Muller and Parikh automata while still exhibiting a decidable (in fact PSpace-complete) emptiness problem. By means of MSO-interpretations\, we lift the decidability result to all tree-interpretable classes of structures\, including the classes of finite/countable structures of bounded treewidth/cliquewidth/partitionwidth. We observe that satisfiability over (finite or infinite) labeled trees becomes undecidable even for a rather mild extension of ωMSO⋈BAPA.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230517T121003
SEQUENCE:38185
END:VEVENT
BEGIN:VEVENT
SUMMARY:Discrete Linear Dynamical Systems: The Introduction.
URL://iccl.inf.tu-dresden.de/web/Discrete_Linear_Dynamical_Systems:_The_Introduction.
UID://iccl.inf.tu-dresden.de/web/Discrete_Linear_Dynamical_Systems:_The_Introduction.
DTSTART:20230512T110000
DTEND:20230512T120000
LOCATION:APB room 2026
DESCRIPTION:Abstract: Linear Dynamical systems are a fundamental modelling paradigm in many branches of science\, and have been the subject of extensive research for many decades and are of profound interest\, both from a theoretical and a practical standpoint. For example\, reachability problems for linear dynamical systems attract attention due to their frequent occurrence in practice and their deep and wide-ranging connections with other fascinating areas of study\, such as problems on Markov chains\, quantum automata. In this presentation we are going to motivate the topic\, give the basic definitions and will consider some famous problems.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus\n\nPlease take a note that the seminar will be held on Friday.
DTSTAMP:20230509T113046
SEQUENCE:38143
END:VEVENT
BEGIN:VEVENT
SUMMARY:Can AI explanations skew our causal intuitions about the world? If so\, can we correct for that?
URL://iccl.inf.tu-dresden.de/web/Can_AI_explanations_skew_our_causal_intuitions_about_the_world%3F_If_so,_can_we_correct_for_that%3F
UID://iccl.inf.tu-dresden.de/web/Can_AI_explanations_skew_our_causal_intuitions_about_the_world%3F_If_so,_can_we_correct_for_that%3F
DTSTART:20230504T110000
DTEND:20230504T120000
LOCATION:Online
DESCRIPTION:Abstract: Explainable Artificial Intelligence provides methods for bringing in transparency into black-box artificial intelligence (AI) systems. These methods produce explanations of AI systems’ predictions that are aimed at increasing the understanding of the AI systems’ behavior and help us to appropriately calibrate our trust in these systems. In this talk\, I will explore some of the potential undesirable effects of providing explanations of AI systems to human users and ways to mitigate such effects. I start from the observation that most AI systems capture correlations and associations in data and not causal relationships. Explanations of the AI systems’ predictions would make the correlations more transparent. They would not\, however\, make the explained relationships causal. In four experiments\, I show how providing counterfactual explanations of AI systems’ predictions unjustifiably changes people’s beliefs about causal relationships in the real world. I also show how we may go about preventing such a change in beliefs and hope to open doors for further exploration into psychological effects of AI explanations on human recipients.\n\nThe talk will take place virtually through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230428T131233
SEQUENCE:38097
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Pitch Rich with Width-Witchcraft – Model-Theoretic Criteria for Decidable Query Entailment
URL://iccl.inf.tu-dresden.de/web/A_Pitch_Rich_with_Width-Witchcraft_%E2%80%93_Model-Theoretic_Criteria_for_Decidable_Query_Entailment
UID://iccl.inf.tu-dresden.de/web/A_Pitch_Rich_with_Width-Witchcraft_%E2%80%93_Model-Theoretic_Criteria_for_Decidable_Query_Entailment
DTSTART:20230420T110000
DTEND:20230420T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: Decidability of inferencing is commonly considered a very important property of logic-based knowledge representation formalisms\, required for the algorithmization and automation of reasoning. Yet\, oftentimes\, the corresponding (un)decidability arguments are idiosyncratic and do not shed much light on the underlying principles governing the divide.\nIn my talk\, I will review generic model-theoretic criteria for decidability of querying in fragments of first-order logic. I will describe a general framework by means of which decidability of query entailment can be established based on the existence of countermodels with certain structural properties. These properties depend on the ontology and query language used and range from finite domain over forest-like shape to width-finiteness employing width notions like treewidth and cliquewidth.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230413T135216
SEQUENCE:38013
END:VEVENT
BEGIN:VEVENT
SUMMARY:Adventures in Computer Science -- Grades 1 & 2
URL://iccl.inf.tu-dresden.de/web/Adventures_in_Computer_Science_--_Grades_1_%26_2
UID://iccl.inf.tu-dresden.de/web/Adventures_in_Computer_Science_--_Grades_1_%26_2
DTSTART:20230330T110000
DTEND:20230330T120000
LOCATION:APB room 3027
DESCRIPTION:Have you sorted you toys at home by color or by size? Have you\never looked for this one particular pencil? Have you asked yourself\, why\ndid this search take so long or how can it be faster? The "World of\nAlgorithms" (German: Die Welt der Algorithmen) provides some useful\ntools for you to achieve your goals as quick as possible. This includes\nproblems that never crossed your minds before. We are going to look at\ncertain problems and their (algorithmic) solutions. It is our goal the\nlearn about the strategies leading to the solutions. We are also facing\nproblems that are so hard to solve for which a quick solutions is out of\nreach\, even for a modern computer.\n\nThis is a translation of the advertisement I provided for pupils at the\n39th Primary School here at Dresden for a so-called "Ganztagsangebot"\n(GTA for short) which is basically a 1 hour/week course\ninstitutionalized as afternoon activity. My target group has been\nchildren at the level of 1st and 2nd grade (ages 6 to 8). In this talk\,\nI will briefly explain what I planned to do\, what I did and what I'm\nplanning to do in this GTA. I will mainly elaborate on the experiences I\ngathered in teaching 6-8 year-olds over the course of this school year.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230327T211414
SEQUENCE:37949
END:VEVENT
BEGIN:VEVENT
SUMMARY:Static Program Analysis in Datalog
URL://iccl.inf.tu-dresden.de/web/Static_Program_Analysis_in_Datalog
UID://iccl.inf.tu-dresden.de/web/Static_Program_Analysis_in_Datalog
DTSTART:20230323T110000
DTEND:20230323T110000
LOCATION:APB room 3027
DESCRIPTION:Abstract: Doop is a framework for Program Analysis of Java code. It utilizes the Datalog engine Souffle to run high-speed analyses on an Intermediate Code Representation. Existing analyses mainly deal with larger-scope Pointer Analysis\, but not with local optimization possibilities. In this talk\, I focus on the implementation of local static analyses like Constant Folding\, Liveness and Available Expressions in Doop. I will give an introduction into the related frameworks\, and point out benefits and limitations of Doop and Souffle regarding each analysis. Furthermore I will compare my results to existing tools for static code analysis and give an outlook whether Doop is suitable for local static analysis.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230320T112131
SEQUENCE:37925
END:VEVENT
BEGIN:VEVENT
SUMMARY:Relating Description Complexity to Entropy
URL://iccl.inf.tu-dresden.de/web/Relating_Description_Complexity_to_Entropy
UID://iccl.inf.tu-dresden.de/web/Relating_Description_Complexity_to_Entropy
DTSTART:20230316T110000
DTEND:20230316T120000
LOCATION:APB room 3027
DESCRIPTION:We demonstrate some novel links between entropy and description complexity\, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic obtained by extending propositional logic with the universal modality\, and let GMLU be the corresponding extension with the ability to count. In the finite\, MLU is expressively complete for specifying sets of variable assignments\, while GMLU is expressively complete for multisets. We show that for MLU\, the model classes with maximal Boltzmann entropy are the ones with maximal description complexity. Concerning GMLU\, we show that expected Boltzmann entropy is asymptotically equivalent to expected description complexity multiplied by the number of proposition symbols considered. To contrast these results\, we prove that this link breaks when we move to considering first-order logic FO over vocabularies with higher-arity relations. To establish the aforementioned result\, we show that almost all finite models require relatively large FO-formulas to define them. Our results relate to links between Kolmogorov complexity and entropy\, demonstrating a way to conceive such results in the logic-based scenario where relational structures are classified by formulas of different sizes.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230313T182807
SEQUENCE:37902
END:VEVENT
BEGIN:VEVENT
SUMMARY:From Provenance Polynomials to Provenance Patterns: More Mileage for Mere Mortals
URL://iccl.inf.tu-dresden.de/web/From_Provenance_Polynomials_to_Provenance_Patterns:_More_Mileage_for_Mere_Mortals
UID://iccl.inf.tu-dresden.de/web/From_Provenance_Polynomials_to_Provenance_Patterns:_More_Mileage_for_Mere_Mortals
DTSTART:20230309T110000
DTEND:20230309T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: \nIt is well known that the commutative semiring of integer polynomials N[X] provides an elegant unifying framework (a.k.a. how-provenance) for a number of earlier provenance approaches in databases. A provenance-annotated answer A’ to a query Q reveals how outputs depend on inputs from the annotated database D′ and thus it can be used to answer strictly more questions than the original answer A = Q(D) without provenance. We propose to use provenance patterns\, a related notion implicit in earlier work\, to support answering additional questions\, not answerable by A′ alone. We show that the pattern-enhanced answer A* can be easily obtained as a by-product of computing A or A’. Using a detailed running example\, we illustrate questions that can and cannot be answered using A\, A′\, and A*\, respectively. Time allowing\, I’d also like to touch upon related research in answering why-not provenance questions. \n\nAbout the speaker:\nBertram Ludäscher is a professor at the School of Information Sciences at the University of Illinois\, Urbana-Champaign\, where he is also a faculty affiliate with the National Center for Supercomputing Applications (NCSA) and the CS department. Prior to joining UIUC\, he was a professor at the CS department and the UC Davis Genome Center at the University of California\, Davis. His research interests range from practical questions in scientific data management and workflow automation\, to database theory\, and knowledge representation & reasoning. Before his faculty appointments\, he was a research scientist at the San Diego Supercomputer Center (SDSC) and an adjunct faculty at the CSE department at UCSD. He holds a M.S. (Dipl.-Inform.) in CS from the University of Karlsruhe (K.I.T.) and a PhD (Dr. rer. nat.) from the University of Freiburg.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230303T202039
SEQUENCE:37892
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tunas - Fishing for Diverse Answer Sets: A Multi-Shot Trade up Strategy
URL://iccl.inf.tu-dresden.de/web/Tunas_-_Fishing_for_Diverse_Answer_Sets:_A_Multi-Shot_Trade_up_Strategy
UID://iccl.inf.tu-dresden.de/web/Tunas_-_Fishing_for_Diverse_Answer_Sets:_A_Multi-Shot_Trade_up_Strategy
DTSTART:20230302T110000
DTEND:20230302T120000
LOCATION:APB room 2026
DESCRIPTION:Abstract: Answer set programming (ASP) solvers have advanced in recent years\, with a variety of different specialisation and overall development. Thus\, even more complex and detailed programs can be solved. A side effect of this development are growing solution spaces and the problem of how to find those answer sets one is interested in. One general approach is to give an overview in form of a small number of highly diverse answer sets. By choosing a favourite and repeating the process\, the user is able to leap through the solution space. But finding highly diverse answer sets is computationally expensive. In this paper we introduce a new approach called Tunas for Trade Up Navigation for Answer Sets to find diverse answer sets by reworking existing solution collections. The core idea is to collect diverse answer sets one after another by iteratively solving and updating the program. Once no more answer sets can be added to the collection\, the program is allowed to trade answer sets from the collection for different answer sets\, as long as the collection grows and stays diverse. Elaboration of the approach is possible in three variations\, which we implemented and compared to established methods in an empirical evaluation. The evaluation shows that the Tunas approach is competitive with existing methods\, and that efficiency of the approach is highly connected to the underlying logic program.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230221T172612
SEQUENCE:37858
END:VEVENT
BEGIN:VEVENT
SUMMARY:Multilinguality in Knowledge Graphs
URL://iccl.inf.tu-dresden.de/web/Multilinguality_in_Knowledge_Graphs
UID://iccl.inf.tu-dresden.de/web/Multilinguality_in_Knowledge_Graphs
DTSTART:20230216T110000
DTEND:20230216T120000
LOCATION:APB 3027
DESCRIPTION:Abstract: In this talk\, I will give an overview of my work in the domain of\nmultilingual knowledge graphs with a focus on Wikidata.\nI will speak about how well knowledge graphs are covered in terms of\nmultilingual information\, how to measure and increase their\nmutlilinguality\, and finally about the reuse of the multilingual\ninformation.\nIn particular\, I introduce a framework to measure knowledge graphs'\nlabels and language information for reuse in applications. Then\, I will\ngive an overview of the topic of machine translation of knowledge graph\nlabels. Further\, we explore the generation of multilingual text from\ntriples.\nI will tie in my most recent work on language models with regard to\nmultilingual and cross-cultural understanding.\n\nThe talk will take place in a hybrid fashion\, physically in the APB room 3027\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20230208T210700
SEQUENCE:37838
END:VEVENT
BEGIN:VEVENT
SUMMARY:Strong Equivalence in Non-monotonic Reasoning
URL://iccl.inf.tu-dresden.de/web/Strong_Equivalence_in_Non-monotonic_Reasoning
UID://iccl.inf.tu-dresden.de/web/Strong_Equivalence_in_Non-monotonic_Reasoning
DTSTART:20230119T110000
DTEND:20230119T120000
LOCATION:APB room 3027
DESCRIPTION:Abstract: In classical logic\, when two theories have the same models\, they are\nmutually replaceable in arbitrary contexts. This is not the case in\nvarious non-monotonic formalisms\, e.g. logic programs under the stable\nmodel semantics\, or abstract argumentation frameworks. There\, two\ntheories (programs/frameworks) can have the same models (stable\nmodels/extensions)\, but yet differ in their semantics when both are\nextended with the same third theory. To obtain mutual replaceability\, a\nstronger notion is needed – this equivalence across all possible\nextensions is known as strong equivalence.\n\nWe address the question on how non-monotonicity is related to this\ndivergence of standard and strong equivalence\, show examples of how\nstrong equivalence for concrete formalisms is analysed in the\nliterature\, and finally preview an abstract\, algebraic approach to\ncharacterising strong equivalence model-theoretically.
DTSTAMP:20230116T210853
SEQUENCE:37756
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient Dependency Analysis for Rule-Based Ontologies
URL://iccl.inf.tu-dresden.de/web/Efficient_Dependency_Analysis_for_Rule-Based_Ontologies
UID://iccl.inf.tu-dresden.de/web/Efficient_Dependency_Analysis_for_Rule-Based_Ontologies
DTSTART:20230112T110000
DTEND:20230112T120000
LOCATION:APB room 3027
DESCRIPTION:Several types of dependencies have been proposed for the static analysis of existential rule ontologies\, promising insights about computational properties and possible practical uses of a given set of rules\, e.g.\, in ontology-based query answering. Unfortunately\, these dependencies are rarely implemented\, so their potential is hardly realised in practice. We focus on two kinds of rule dependencies - positive reliances and restraints - and design and implement optimised algorithms for their efficient computation. Experiments on real-world ontologies of up to more than 100\,000 rules show the scalability of our approach\, which lets us realise several previously proposed applications as practical case studies. In particular\, we can analyse to what extent rule-based bottom-up approaches of reasoning can be guaranteed to yield redundancy-free "lean" knowledge graphs (so-called cores) on practical ontologies.
DTSTAMP:20230106T113352
SEQUENCE:37707
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nested Sequents for First-Order Modal Logics via Reachability Rules
URL://iccl.inf.tu-dresden.de/web/Nested_Sequents_for_First-Order_Modal_Logics_via_Reachability_Rules
UID://iccl.inf.tu-dresden.de/web/Nested_Sequents_for_First-Order_Modal_Logics_via_Reachability_Rules
DTSTART:20221215T110000
DTEND:20221215T120000
LOCATION:APB room 3027
DESCRIPTION:In this talk\, we present cut-free nested sequent calculi for first-order modal logics. We consider a diverse class of first-order modal logics obtained by imposing certain Horn conditions on the relational and domain structure of QK models. Labeled sequent calculi are then obtained via standard techniques from the semantics of these logics. We show how to derive nested calculi from labeled via the 'structural refinement' technique\, which consists of eliminating structural rules\, introducing reachability rules\, and translating notation. The reachability rules obtained via this method possess a unique functionality\, consisting of propagating and/or checking if data exists along certain paths within a nested sequent. We demonstrate how such rules operate and touch on the significance of the nested sequent formulation (in the first-order setting) which emerges naturally from the structural refinement methodology.
DTSTAMP:20221211T170759
SEQUENCE:37645
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Relevance of Formal Logics for Cognitive Logics\, and Vice Versa
URL://iccl.inf.tu-dresden.de/web/The_Relevance_of_Formal_Logics_for_Cognitive_Logics,_and_Vice_Versa
UID://iccl.inf.tu-dresden.de/web/The_Relevance_of_Formal_Logics_for_Cognitive_Logics,_and_Vice_Versa
DTSTART:20221214T110000
DTEND:20221214T120000
LOCATION:APB room 2026
DESCRIPTION:Classical logics like propositional or predicate logic have been considered as the gold standard for rational human reasoning\, and hence as a solid\, desirable norm on which all human knowledge and decision making should be based\, ideally. For instance\, Boolean logic was set up as kind of an arithmetic framework that should help make rational reasoning computable in an objective way\, similar to the arithmetics of numbers. Computer scientists adopted this view to (literally) implement objective knowledge and rational deduction\, in particular for AI applications. Psychologists have used classical logics as norms to assess the rationality of human commonsense reasoning. However\, both disciplines could not ignore the severe limitations of classical logics\, e.g.\, computational complexity and undecidedness\, failures of logic-based AI systems in practice\, and lots of psychological paradoxes. Many of these problems are caused by the inability of classical logics to deal with uncertainty in an adequate way. Both disciplines have used probabilities as a way out of this dilemma\, hoping that numbers and the Kolmogoroff axioms can do the job (somehow). However\, psychologists have been observing also lots of paradoxes here (maybe even more).\n\nSo then\, are humans hopelessly irrational? Is human reasoning incompatible with formal\, axiomatic logics? In the end\, should computer-based knowledge and information processing be considered as superior in terms of objectivity and rationality?\n\nCognitive logics aim at overcoming the limitations of classical logics and resolving the observed paradoxes by proposing logic-based approaches that can model human reasoning consistently and coherently in benchmark examples. The basic idea is to reverse the normative way of assessing human reasoning in terms of logics resp. probabilities\, and to use typical human reasoning patterns as norms for assessing the cognitive quality of logics. Cognitive logics explore the broad field of logic-based approaches between the extreme points marked by classical logics and probability theory with the goal to find more suitable logics for AI applications\, on the one hand\, and to gain more insights into the rational structures of human reasoning\, on the other.
DTSTAMP:20221211T104845
SEQUENCE:37643
END:VEVENT
BEGIN:VEVENT
SUMMARY:IASCAR: Incremental Answer Set Counting by Anytime Refinement
URL://iccl.inf.tu-dresden.de/web/IASCAR:_Incremental_Answer_Set_Counting_by_Anytime_Refinement
UID://iccl.inf.tu-dresden.de/web/IASCAR:_Incremental_Answer_Set_Counting_by_Anytime_Refinement
DTSTART:20221124T110000
DTEND:20221124T120000
LOCATION:APB room 3027
DESCRIPTION:Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have so many answer sets that they cannot be enumerated in practice\, but counting still allows to quantify solution spaces. If one counts under assumptions on literals\, one obtains a tool to comprehend parts of the solution space\, so called answer set navigation. But navigating through parts of the solution space requires counting many times\, which is expensive in theory. There\, knowledge compilation compiles instances into representations on which counting works in polynomial time. However\, these techniques exist only for CNF formulas and compiling ASP programs into CNF formulas can introduce an exponential overhead. In this paper\, we introduce a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the principle of inclusion-exclusion to systematically improve bounds by over- and undercounting. In a preliminary empirical analysis we demonstrate promising results. After compiling the input (offline phase) our approach quickly (re)counts.
DTSTAMP:20221119T115255
SEQUENCE:37564
END:VEVENT
BEGIN:VEVENT
SUMMARY:Normalisations of Existential Rules: Not so Innocuous!
URL://iccl.inf.tu-dresden.de/web/Normalisations_of_Existential_Rules:_Not_so_Innocuous!
UID://iccl.inf.tu-dresden.de/web/Normalisations_of_Existential_Rules:_Not_so_Innocuous!
DTSTART:20221117T110000
DTEND:20221117T120000
LOCATION:APB room 3027
DESCRIPTION:Existential rules are an expressive knowledge representation language mainly developed to query data. In the literature\, they are often supposed to be in some normal form that simplifies technical developments. For instance\, a common assumption is that rule heads are atomic\, i.e.\, restricted to a single atom. Such assumptions are considered to be made without loss of generality as long as all sets of rules can be normalised while preserving entailment. However\, an important question is whether the properties that ensure the decidability of reasoning are preserved as well. We provide a systematic study of the impact of these procedures on the different chase variants with respect to chase (non-)termination and FO-rewritability. This also leads us to study open problems related to chase termination of independent interest.
DTSTAMP:20221114T103916
SEQUENCE:37538
END:VEVENT
BEGIN:VEVENT
SUMMARY:General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase
URL://iccl.inf.tu-dresden.de/web/General_Acyclicity_and_Cyclicity_Notions_for_the_Disjunctive_Skolem_Chase
UID://iccl.inf.tu-dresden.de/web/General_Acyclicity_and_Cyclicity_Notions_for_the_Disjunctive_Skolem_Chase
DTSTART:20221110T110000
DTEND:20221110T120000
LOCATION:APB room 3027
DESCRIPTION:The disjunctive skolem chase is a sound\, complete\, and potentially non-terminating procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. We develop novel acyclicity and cyclicity notions for this procedure\; that is\, we develop sufficient conditions to determine chase termination and non-termination. Our empirical evaluation shows that our novel notions are significantly more general than existing criteria.
DTSTAMP:20221107T205147
SEQUENCE:37513
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying
URL://iccl.inf.tu-dresden.de/web/Finite-Cliquewidth_Sets_of_Existential_Rules:_Toward_a_General_Criterion_for_Decidable_yet_Highly_Expressive_Querying
UID://iccl.inf.tu-dresden.de/web/Finite-Cliquewidth_Sets_of_Existential_Rules:_Toward_a_General_Criterion_for_Decidable_yet_Highly_Expressive_Querying
DTSTART:20221103T110000
DTEND:20221003T120000
LOCATION:APB room 3027
DESCRIPTION:In our pursuit of generic criteria for decidable ontology-based querying\, we introduce 'finite-cliquewidth sets' (FCS) of existential rules\, a model-theoretically defined class of rule sets\, inspired by the cliquewidth measure from graph theory. By a generic argument\, we show that FCS ensures decidability of entailment for a sizable class of queries (dubbed 'DaMSOQs') subsuming conjunctive queries (CQs). The FCS class properly generalizes the class of finite-expansion sets (FES)\, and for signatures of arity at most 2\, the class of bounded-treewidth sets (BTS). For higher arities\, BTS is only indirectly subsumed by FCS by means of reification. Despite the generality of FCS\, we provide a rule set with decidable CQ entailment (by virtue of first-order-rewritability) that falls outside FCS\, thus demonstrating the incomparability of FCS and the class of finite-unification sets (FUS). In spite of this\, we show that if we restrict ourselves to single-headed rule sets over signatures of arity at most 2\, then FCS subsumes FUS.
DTSTAMP:20221031T140937
SEQUENCE:37469
END:VEVENT
BEGIN:VEVENT
SUMMARY:How to Agree to Disagree: Managing Ontological Perspectives using Standpoint Logic
URL://iccl.inf.tu-dresden.de/web/How_to_Agree_to_Disagree:_Managing_Ontological_Perspectives_using_Standpoint_Logic
UID://iccl.inf.tu-dresden.de/web/How_to_Agree_to_Disagree:_Managing_Ontological_Perspectives_using_Standpoint_Logic
DTSTART:20221020T110000
DTEND:20221020T120000
LOCATION:APB room 3027
DESCRIPTION:The importance of taking individual\, potentially conflicting perspectives into account when dealing with knowledge has been widely recognised. Many existing ontology management approaches fully merge knowledge perspectives\, which may require weakening in order to maintain consistency\; others represent the distinct views in an entirely detached way. As an alternative\, we propose Standpoint Logic\, a simple\, yet versatile multi-modal logic ``add-on'' for existing KR languages intended for the integrated representation of domain knowledge relative to diverse\, possibly conflicting \\emph{standpoints}\, which can be hierarchically organised\, combined\, and put in relation with each other.\nStarting from the generic framework of First-Order Standpoint Logic (FOSL)\, we subsequently focus our attention on the fragment of sentential formulas\, for which we provide a polytime translation into the standpoint-free version. This result yields decidability and favourable complexities for a variety of highly expressive decidable fragments of first-order logic. Using some encoding tricks\, we then establish a similar translation for the very expressive description logic SROIQb_s underlying the OWL 2 DL ontology language. By virtue of this result\, existing highly optimised OWL reasoners can be used to provide practical reasoning support for ontology languages extended by standpoint modelling.
DTSTAMP:20221017T094452
SEQUENCE:37385
END:VEVENT
BEGIN:VEVENT
SUMMARY:Discovering Fine-Grained Semantics in Knowledge Graph Relations
URL://iccl.inf.tu-dresden.de/web/Discovering_Fine-Grained_Semantics_in_Knowledge_Graph_Relations
UID://iccl.inf.tu-dresden.de/web/Discovering_Fine-Grained_Semantics_in_Knowledge_Graph_Relations
DTSTART:20221006T110000
DTEND:20221006T120000
LOCATION:APB room 3027
DESCRIPTION:Knowledge graphs (KGs) provide structured representation of data in the\nform of relations between different entities. The semantics of relations\nbetween words and entities are often ambiguous\, where it is common to\nfind polysemous relations that represent multiple semantics based on the\ncontext. This ambiguity in relation semantics also proliferates KG\ntriples. While the guidance from custom-designed ontologies addresses\nthis issue to some extent\, our analysis shows that the heterogeneity and\ncomplexity of real-world data still results in substantial relation\npolysemy within popular KGs. The correct semantic interpretation of KG\nrelations is necessary for many downstream applications such as entity\nclassification and question answering.\n\nWe present the problem of fine-grained relation discovery and a\ndata-driven method towards this task that leverages the vector\nrepresentations of the knowledge graph entities and relations available\nfrom relational learning models.\n\nWe show that by performing clustering over these vectors\, our method is\nable to not only identify the polysemous relations in knowledge graphs\,\nbut also discover the different semantics associated with them.\nExtensive empirical evaluation shows that fine-grained relations\ndiscovered by the proposed approach lead to substantial improvement in\nthe semantics in the Yago and NELL datasets\, as compared to baselines.\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\nhttps://bbb.tu-dresden.de/b/pio-zwt-smp-aus
DTSTAMP:20220930T084721
SEQUENCE:37209
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computability and Complexity of (Iterated) Belief Revision
URL://iccl.inf.tu-dresden.de/web/Computability_and_Complexity_of_(Iterated)_Belief_Revision
UID://iccl.inf.tu-dresden.de/web/Computability_and_Complexity_of_(Iterated)_Belief_Revision
DTSTART:20221005T140000
DTEND:20221005T150000
LOCATION:APB 3027
DESCRIPTION:Belief revision denotes the process of the incorporation of new information while maintaining consistency whenever possible. In this talk\, at first\, we consider some known complexity results for belief revision. Second\, we consider the recent insight that the typical framework for iterated belief revision is computationally universal.
DTSTAMP:20221004T112955
SEQUENCE:37237
END:VEVENT
BEGIN:VEVENT
SUMMARY:An Existential Rule Framework for Computing Why-Provenance On-Demand for Datalog
URL://iccl.inf.tu-dresden.de/web/An_Existential_Rule_Framework_for_Computing_Why-Provenance_On-Demand_for_Datalog
UID://iccl.inf.tu-dresden.de/web/An_Existential_Rule_Framework_for_Computing_Why-Provenance_On-Demand_for_Datalog
DTSTART:20220922T110000
DTEND:20220922T120000
LOCATION:APB room 3027
DESCRIPTION:Why-provenance — explaining why a query result is obtained — is an essential asset for reaching the goal of Explainable AI. For instance\, recursive (Datalog) queries may show unexpected derivations due to complex entanglement of database atoms inside recursive rule applications. Provenance\, and why-provenance in particular\, helps debugging rule sets to eventually obtain the desired set of rules. There are three kinds of approaches to computing why-provenance for Datalog in the literature: (1) the complete ones\, (2) the approximate ones\, and (3) the theoretical ones. What all these approaches have in common is that they aim at computing provenance for all IDB atoms\, while only a few atoms might be requested to be explained. We contribute an on-demand approach: After deriving all entailed facts of a Datalog program\, we allow for querying for the provenance of particular IDB atoms and the structures involved in deriving provenance are computed only then. Our framework is based on terminating existential rules\, recording the different rule applications. We present two implementations of the framework\, one based on the semiring solver FPsolve\, the other one based Datalog(S)\, a recent extension of Datalog by set terms. We perform experiments on benchmark rule sets using both implementations and discuss feasibility of provenance on-demand.\n\nThe talk is based on the upcoming conference paper in RuleML+RR 2022 with Markus Krötzsch and Stephan Mennicke\, the paper can be found through the following link: https://iccl.inf.tu-dresden.de/web/Inproceedings3342\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220909T131327
SEQUENCE:37062
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finite Base Contraction and Expansion via Models - The ALC case
URL://iccl.inf.tu-dresden.de/web/Finite_Base_Contraction_and_Expansion_via_Models_-_The_ALC_case
UID://iccl.inf.tu-dresden.de/web/Finite_Base_Contraction_and_Expansion_via_Models_-_The_ALC_case
DTSTART:20220908T110000
DTEND:20220908T120000
LOCATION:APB room 3027
DESCRIPTION:We propose a new paradigm for Belief Change in which the new information is represented as sets of models\, while the agent’s body of knowledge is represented as a finite set of formulae\, that is\, a finite base. The focus on finiteness is crucial\nwhen we consider limited agents and reasoning algorithms. Moreover\, having the input as arbitrary set of models is more general than the usual treatment of formulae as input. In this setting\, we define new Belief Change operations akin to traditional expansion and contraction\, and we identify the rationality postulates that emerge due to the finite representability requirement. We also analyse different logics concerning compatibility with our framework. In this talk\, I will focus on the ALC description logic.\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\n\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220906T094832
SEQUENCE:37037
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tunas - Fishing for Diverse Answer Sets: A Multi-shot Trade up Strateg
URL://iccl.inf.tu-dresden.de/web/Tunas_-_Fishing_for_Diverse_Answer_Sets:_A_Multi-shot_Trade_up_Strateg
UID://iccl.inf.tu-dresden.de/web/Tunas_-_Fishing_for_Diverse_Answer_Sets:_A_Multi-shot_Trade_up_Strateg
DTSTART:20220901T113000
DTEND:20220901T120000
LOCATION:APB room 3027
DESCRIPTION:Answer set programming (ASP) solvers have advanced in\nrecent years\, with a variety of different specialisation and overall devel-\nopment. Thus\, even more complex and detailed programs can be solved.\nA side effect of this development are growing solution spaces and the\nproblem of how to find those answer sets one is interested in. One gen-\neral approach is to give an overview in form of a small number of highly\ndiverse answer sets. By choosing a favourite and repeating the process\,\nthe user is able to leap through the solution space. But finding highly\ndiverse answer sets is computationally expensive. In this paper we intro-\nduce a new approach called Tunas for Trade Up Navigation for Answer\nSets to find diverse answer sets by reworking existing solution collec-\ntions. The core idea is to collect diverse answer sets one after another by\niteratively solving and updating the program. Once no more answer sets\ncan be added to the collection\, the program is allowed to trade answer\nsets from the collection for different answer sets\, as long as the collection\ngrows and stays diverse. Elaboration of the approach is possible in three\nvariations\, which we implemented and compared to established methods\nin an empirical evaluation. The evaluation shows that the Tunas app-\nroach is competitive with existing methods\, and that efficiency of the\napproach is highly connected to the underlying logic program.\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\n\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220829T142934
SEQUENCE:36979
END:VEVENT
BEGIN:VEVENT
SUMMARY:Representing Abstract Dialectical Frameworks with Binary Decision Diagrams
URL://iccl.inf.tu-dresden.de/web/Representing_Abstract_Dialectical_Frameworks_with_Binary_Decision_Diagrams
UID://iccl.inf.tu-dresden.de/web/Representing_Abstract_Dialectical_Frameworks_with_Binary_Decision_Diagrams
DTSTART:20220901T110000
DTEND:20220901T113000
LOCATION:APB room 3027
DESCRIPTION:Abstract dialectical frameworks (ADFs) are a well-studied generalisation of the prominent argumentation frameworks due to Phan Minh Dung. In this paper we propose to use reduced ordered binary decision diagrams (roBDDs) as a suitable representation of the acceptance conditions of arguments within ADFs. We first show that computational complexity of reasoning on ADFs represented by roBDDs is milder than in the general case\, with a drop of one level in the polynomial hierarchy. Furthermore\, we present a framework to systematically define heuristics for search space exploitation\, based on easily retrievable properties of roBDDs and the recently proposed approach of weighted faceted navigation for answer set programming. Finally\, we present preliminary experiments of an implementation of our approach showing promise both when compared to state-of-the-art solvers and when developing heuristics for reasoning.\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\n\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220829T142659
SEQUENCE:36977
END:VEVENT
BEGIN:VEVENT
SUMMARY:The More the Worst-Case-Merrier: A Generalized Condorcet Jury Theorem for Belief Fusion
URL://iccl.inf.tu-dresden.de/web/The_More_the_Worst-Case-Merrier:_A_Generalized_Condorcet_Jury_Theorem_for_Belief_Fusion
UID://iccl.inf.tu-dresden.de/web/The_More_the_Worst-Case-Merrier:_A_Generalized_Condorcet_Jury_Theorem_for_Belief_Fusion
DTSTART:20220728T110000
DTEND:20220728T120000
LOCATION:APB room 3027
DESCRIPTION:In multi-agent belief fusion\, there is increasing interest in results and methods from social choice theory. As a theoretical cornerstone\, the Condorcet Jury Theorem (CJT) states that given a number of equally competent\, independent agents where each is more likely to guess the true out of two alternatives\, the chances of determining this objective truth by majority voting increase with the number of participating agents\, approaching certainty. Past generalizations of the CJT have shown that some of its underlying assumptions can be weakened. Motivated by requirements from practical belief fusion scenarios\, we provide a significant further generalization that subsumes several of the previous ones. Our considered setting simultaneously allows for heterogeneous competence levels across the agents (even tolerating entirely incompetent or even malicious voters)\, and voting for any number of alternatives from a finite set. We derive practical lower bounds for the numbers of agents needed to give probabilistic guarantees for determining the true state through approval voting. We also demonstrate that the non-asymptotic part of the CJT fails in our setting for arbitrarily high numbers of voters.\n\nThe talk will take place in a hybrid fashion\, physically in the seminar room\, and online through the link:\n\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220726T080754
SEQUENCE:36870
END:VEVENT
BEGIN:VEVENT
SUMMARY:KLM-Style Defeasible Reasoning
URL://iccl.inf.tu-dresden.de/web/KLM-Style_Defeasible_Reasoning
UID://iccl.inf.tu-dresden.de/web/KLM-Style_Defeasible_Reasoning
DTSTART:20220721T110000
DTEND:20220721T120000
LOCATION:APB room 3027
DESCRIPTION:This talk will give an overview of KLM-style defeasible reasoning\, a form of non-monotonic reasoning initially introduced by Kraus\, Lehmann\, and Magidor. The overview will start with the propositional roots of defeasible reasoning and its links with the theory of Belief Revision. I will then discuss its application to description logics and other fragments of first-order logic\, and the challenges inherent in lifting the intuition underlying propositional versions of defeasible reasoning to more expressive logics.\n\nThe talk will take place in a hybrid fashion\, physically in our seminar room\, and online through the link:\nhttps://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220704T081604
SEQUENCE:36809
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Glimpse into Propositional Model Counting
URL://iccl.inf.tu-dresden.de/web/A_Glimpse_into_Propositional_Model_Counting
UID://iccl.inf.tu-dresden.de/web/A_Glimpse_into_Propositional_Model_Counting
DTSTART:20220707T110000
DTEND:20220707T120000
LOCATION:Online
DESCRIPTION:Model counting (#SAT) asks to compute the number of satisfying assignments for a propositional formula. The decision version (SAT) received widespread interest in computational complexity\, formed many applications in modern combinatorial problem solving\, and can be solved effectively for millions of variables on structured instances. #SAT is much harder than SAT and requires more elaborate solving techniques. In this talk\, we revisit the problem\, its complexity\, and explain its connection to quantitative AI. We briefly overview solving techniques and illustrate a parameterized algorithm and implementation to tackle the problem. While purely parameterized approaches from theory often suffer practical limitations\, we elaborate that a parameterized algorithm can be successful when combining it with modern hardware that takes advantage of parallelism.
DTSTAMP:20220630T122522
SEQUENCE:36779
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient Emulation of Datalog(S) in the Existential Rules Engine VLog
URL://iccl.inf.tu-dresden.de/web/Efficient_Emulation_of_Datalog(S)_in_the_Existential_Rules_Engine_VLog
UID://iccl.inf.tu-dresden.de/web/Efficient_Emulation_of_Datalog(S)_in_the_Existential_Rules_Engine_VLog
DTSTART:20220630T110000
DTEND:20220630T120000
LOCATION:APB room 3027
DESCRIPTION:We propose a translation of the expressive logic Datalog(S)\, a subset of Datalog^CV\, into optimised existential rules. We look into applications of the language\, in particular regarding description logic and graph theory\, as well as into expressivity. We explain the translation from earlier work in detail\, identify issues and propose solutions to increase performance. We explain the need for singularisation\, propose partial congruence as an alternative and define criteria for when this handling is not necessary. Furthermore\, we propose an alternative translation for which the standard chase universally terminates. To measure the impact of each optimisation\, we conduct an empirical evaluation on real-world data.\n\nThe talk is a defence\, with a hybrid attendance.\n\nlink: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220630T132340
SEQUENCE:36784
END:VEVENT
BEGIN:VEVENT
SUMMARY:Statistics for Knowledge Graph Modelling
URL://iccl.inf.tu-dresden.de/web/Statistics_for_Knowledge_Graph_Modelling
UID://iccl.inf.tu-dresden.de/web/Statistics_for_Knowledge_Graph_Modelling
DTSTART:20220623T110000
DTEND:20220623T120000
LOCATION:APB room 3027
DESCRIPTION:In this talk I will provide a high level overview of how statistical approaches can be used to model knowledge graphs. The talk is intended for everyone\, regardless of statistics background\, and will cover the basic vocabulary and concepts before moving on to a high level view of inference and how it can be used to approximate joint distributions. Finally\, I will tie these ideas with my current work.\n\nThe talk will take place in a hybrid fashion\, physical attendance is in our seminar room.\nLink: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220620T110446
SEQUENCE:36671
END:VEVENT
BEGIN:VEVENT
SUMMARY:Satisfiability Testing -- Recent Developments and Open Problems
URL://iccl.inf.tu-dresden.de/web/Satisfiability_Testing_--_Recent_Developments_and_Open_Problems
UID://iccl.inf.tu-dresden.de/web/Satisfiability_Testing_--_Recent_Developments_and_Open_Problems
DTSTART:20220616T110000
DTEND:20220616T120000
LOCATION:APB room 3027
DESCRIPTION:With the introduction of clause learning in 1996\,\nsatisfiability testing (SAT) solvers have become effective to replace\nother state-of-the-art algorithm in applications. Shortly after\,\nefficient data structures and heuristics have been introduced\, boosting\nthe performance of these solvers further. Recent developments shift SAT\nsolvers towards anytime algorithms\, to attempt to find a good average\nsolving time for a wide range of input problems. Consequently\, SAT\nsolvers have become the core tool to solve many industrial applications.\nHowever\, there are still limitations\, and open research questions that\nwould allow to make SAT solving even more effective. This presentation\nwill shed some light on various past and recent developments\, as well as\npoint out current known limitations as well as open research questions.\n\nThe talk is Hybird\, with a 20 person maximum capacity in the seminar room APB 3027\n\nOnline link: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220630T132015
SEQUENCE:36782
END:VEVENT
BEGIN:VEVENT
SUMMARY:The World Avatar project – a universal digital twin
URL://iccl.inf.tu-dresden.de/web/The_World_Avatar_project_%E2%80%93_a_universal_digital_twin
UID://iccl.inf.tu-dresden.de/web/The_World_Avatar_project_%E2%80%93_a_universal_digital_twin
DTSTART:20220615T100000
DTEND:20220615T110000
LOCATION:APB room 3027
DESCRIPTION:“The World Avatar” (TWA) project aims to create a digital ‘avatar’ of the real world. The digital world is represented using a dynamic knowledge graph that contains concepts and data that describe the world\, and an ecosystem of autonomous computational agents that simulate the behaviour of the world and that update the concepts and data so that the digital world remains current in time. In this manner\, it is proposed that it is possible to create digital twins that can describe the behaviour of any complex system\, and by doing so provide the ability to make data-driven decisions about how to optimise the systems. Examples will be presented from TWA including chemical knowledge creation\, laboratory automation\, building management\, smart city operation\, climate resilience and national energy scenarios. \n\nThe talk is Hybird!\, with a 20 person maximum capacity in the seminar room APB 3027\n\nOnline link: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220610T112318
SEQUENCE:36602
END:VEVENT
BEGIN:VEVENT
SUMMARY:Blockmodelling Knowledge Graphs
URL://iccl.inf.tu-dresden.de/web/Blockmodelling_Knowledge_Graphs
UID://iccl.inf.tu-dresden.de/web/Blockmodelling_Knowledge_Graphs
DTSTART:20220602T110000
DTEND:20220602T120000
LOCATION:APB room 3027
DESCRIPTION:In this talk\, I provide an introductory overview of knowledge graphs\, stochastic blockmodelling\, and the area where these two domains intersect. Furthermore\, I will highlight some of the work I have contributed to and am currently working on. The aim of the talk is to provide a gentle introduction to my work that can be a starting point for future discussion and collaboration.\n\nThe talk is Hybird!\, with a 20 person maximum capacity in the seminar room APB 3027\nOnline link: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220530T091347
SEQUENCE:36552
END:VEVENT
BEGIN:VEVENT
SUMMARY:Communication with Automata
URL://iccl.inf.tu-dresden.de/web/Communication_with_Automata
UID://iccl.inf.tu-dresden.de/web/Communication_with_Automata
DTSTART:20220519T110000
DTEND:20220519T120000
LOCATION:Online
DESCRIPTION:In this talk I will give an overview on the basic notions of Petri nets\, in order to derive two results and their proofs. The selection of the particular results is (1) a personal choice (because I like them) and (2) taught in the course "Models of Concurrent Systems" (apparently also known as "Concurrency Theory") this semester.\n\nThe talk is online\, \nLink: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DTSTAMP:20220516T214636
SEQUENCE:36485
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weighted Automata with Storage
URL://iccl.inf.tu-dresden.de/web/Weighted_Automata_with_Storage
UID://iccl.inf.tu-dresden.de/web/Weighted_Automata_with_Storage
DTSTART:20220512T110000
DTEND:20220512T120000
LOCATION:Https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DESCRIPTION:This talk is an excerpt of the PhD defense talk by Luisa Hermann.\n\nIn this thesis\, we investigate weighted tree automata with storage theoretically. This model generalises finite state automata in three dimensions: (i) from words to trees\, (ii) by using an arbitrary storage type in addition to a finite-state control\, and (iii) by considering languages in a quantitative setting using a weight structure.
DTSTAMP:20220427T201150
SEQUENCE:36324
END:VEVENT
BEGIN:VEVENT
SUMMARY:Causality meets Configurable Systems
URL://iccl.inf.tu-dresden.de/web/Causality_meets_Configurable_Systems
UID://iccl.inf.tu-dresden.de/web/Causality_meets_Configurable_Systems
DTSTART:20220505T110000
DTEND:20220505T120000
LOCATION:Https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DESCRIPTION:Detecting and understanding reasons for defects and inadvertent behavior in computing systems is challenging due to increasing complexity of such systems. Configurability adds a further layer of complexity as the number of system variants can be exponential in the number of configuration options. Determining reasons of configuration decisions that yield an effect\, e.g.\, ensuring quality of service\, is hence a crucial and difficult task. In this talk\, I will present a notion of causality at the level of configuration options and algorithms to compute such causes from (functional and non-functional) analysis results. The presented notion of causality is based on counterfactual reasoning and inspired by the seminal definition of actual causality by Halpern and Pearl. I will present various methods to explicate such reasons for effects\, e.g.\, based on well-established notions of responsibility and blame. By means of an evaluation on a wide range of configurable software systems\, including community benchmarks and real-world systems\, the feasibility of this approach is demonstrated by identifying root causes\, estimate the effects of configuration options\, and detect feature interactions.
DTSTAMP:20220427T201132
SEQUENCE:36323
END:VEVENT
BEGIN:VEVENT
SUMMARY:Expressivity of Planning with Horn Description Logic Ontologies
URL://iccl.inf.tu-dresden.de/web/Expressivity_of_Planning_with_Horn_Description_Logic_Ontologies
UID://iccl.inf.tu-dresden.de/web/Expressivity_of_Planning_with_Horn_Description_Logic_Ontologies
DTSTART:20220428T110000
DTEND:20220428T120000
LOCATION:Https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n
DESCRIPTION:State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously\, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates\, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ\, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast\, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally\, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies\, and is feasible on new benchmarks taking advantage of more expressive ontologies.\n\nThis talk is about joint work with Jörg Hoffmann\, Alisa Kovtunova\, [[Markus Krötzsch]]\, Bernhard Nebel\, and Marcel Steinmetz. It has been presented at the [https://aaai.org/Conferences/AAAI-22/ AAAI conference] 2022.\n\nAccess the [https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n BBB Room] for the seminar room on April 28\, 11am.
DTSTAMP:20220427T195720
SEQUENCE:36319
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing Generalizations of Temporal EL Concepts with Next and Global
URL://iccl.inf.tu-dresden.de/web/Computing_Generalizations_of_Temporal_EL_Concepts_with_Next_and_Global
UID://iccl.inf.tu-dresden.de/web/Computing_Generalizations_of_Temporal_EL_Concepts_with_Next_and_Global
DTSTART:20220414T110000
DTEND:20220414T120000
LOCATION:Online
DESCRIPTION:In ontology-based applications\, the authoring of complex concepts or queries written in a description logic (DL) is a difficult task. An established approach to generate complex expressions from examples provided a user\, is the bottom-up approach. This approach employs two inferences: the most specific concept (MSC)\, which generalizes an ABox individual into a concept and the least common subsumer (LCS)\, which generalizes a collection of concepts into a single concept. In ontology-based situation recognition the situation to be recognized is formalized by a DL query using temporal operators and that is to answered over a sequence of ABoxes. Now\, while the bottom-up approach is well-investigated for the DL EL\, there are so far no methods for temporalized DLs. We consider here the temporalized DL that extends the DL EL with the LTL operators next (X) and global (G) and we present an approach that extends the LCS and the MSC to the temporalized setting.
DTSTAMP:20220401T123703
SEQUENCE:35908
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2EXPTIME-hard
URL://iccl.inf.tu-dresden.de/web/The_Price_of_Selfishness:_Conjunctive_Query_Entailment_for_ALCSelf_is_2EXPTIME-hard
UID://iccl.inf.tu-dresden.de/web/The_Price_of_Selfishness:_Conjunctive_Query_Entailment_for_ALCSelf_is_2EXPTIME-hard
DTSTART:20220407T110000
DTEND:20220407T120000
LOCATION:Online
DESCRIPTION:In logic-based knowledge representation\, query answering has essentially replaced mere satisfiability checking as the infer encing problem of primary interest. For knowledge bases in the basic description logic ALC\, the computational complexity of conjunctive query (CQ) answering is well known to be EXPTIME-complete and hence not harder than satisfiability. This does not change when the logic is extended by certain features (such as counting or role hierarchies)\, whereas adding others (inverses\, nominals or transitivity together with role-hierarchies) turns CQ answering exponentially harder. We contribute to this line of results by showing the surprising fact that even extending ALC by just the Self operator – which proved innocuous in many other contexts – increases the complexity of CQ entailment to 2EXPTIME. As common for this type of problem\, our proof establishes a reduction from alternating Turing machines running in exponential space\, but several novel ideas and encoding tricks are required to make the approach work in that specific\, restricted setting.
DTSTAMP:20220401T123114
SEQUENCE:35906
END:VEVENT
END:VCALENDAR