BEGIN:VCALENDAR
PRODID:-//SMW Project//Semantic Result Formats
VERSION:2.0
METHOD:PUBLISH
X-WR-CALNAME:ICCL-Veranstaltungen
BEGIN:VEVENT
SUMMARY:Ontological Modelling in Wikidata
URL://iccl.inf.tu-dresden.de/web/Ontological_Modelling_in_Wikidata
UID://iccl.inf.tu-dresden.de/web/Ontological_Modelling_in_Wikidata
DTSTART:20181025T130000
DTEND:20181025T143000
LOCATION:APB 3027
DESCRIPTION:This was an invited keynote talk at the 9th Workshop on Ontology Design and Patterns (WOP'18)\, 2018.\n\n\n'''Abstract:''' Wikidata\, the knowledge base of Wikimedia\, has been extremely successful in building and sustaining new communities of editors and users. Since its inception in 2012\, it has developed from an experimental “data wiki” into a well-organised reference knowledge base with an amazing array of applications. Developing an ontological schema for such an open and rapidly expanding project is a huge undertaking\, and difficult challenges arise on many levels. The community has directed significant efforts towards vocabulary development\, many guidelines and rules have been created\, and tools are used for helping editors to avoid and correct modelling errors. Nevertheless\, the distributed nature of Wikidata editing often means that ontology design\, too\, is distributed\, and a coherent global view is only being worked on once significant amounts of data have been added. The result is a knowledge graph with a widely varying modelling quality across different sub-domains.\n\nThe big question for researchers is how their insights and methods can help here. The Wikidata community is widely aware of semantic web activities and existing standards and academic publications play a role in many discussions. Yet\, there seems to be only little direct exchange between the communities. In this talk\, I will review the current state of Wikidata and its connection to semantic web standards such as RDF and SPARQL. I will try to raise awareness of the particular requirements of Wikidata\, and argue that these are of general interest for the data-driven curation of knowledge graphs.
DTSTAMP:20181019T105041
SEQUENCE:26935
END:VEVENT
BEGIN:VEVENT
SUMMARY:Making Repairs in Description Logics More Gentle
URL://iccl.inf.tu-dresden.de/web/Making_Repairs_in_Description_Logics_More_Gentle
UID://iccl.inf.tu-dresden.de/web/Making_Repairs_in_Description_Logics_More_Gentle
DTSTART:20181018T133000
DTEND:20181018T143000
LOCATION:APB 3027
DESCRIPTION:Abstract:\n"The classical approach for repairing a Description Logic ontology O in the sense of removing an unwanted consequence α is to delete a minimal number of axioms from O such that the resulting ontology O′ does not have the consequence α. However\, the complete deletion of axioms may be too rough\, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem\, we propose a more gentle notion of repair in which axioms are not deleted but only weakened. On the one hand\, we investigate the general properties of this gentle repair method. On the other hand\, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic EL."\n\nThis is a rehearsal talk for KR 2018.
DTSTAMP:20181018T083442
SEQUENCE:26904
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Combined Approach to Query Answering in Horn-ALCHOIQ
URL://iccl.inf.tu-dresden.de/web/The_Combined_Approach_to_Query_Answering_in_Horn-ALCHOIQ2
UID://iccl.inf.tu-dresden.de/web/The_Combined_Approach_to_Query_Answering_in_Horn-ALCHOIQ2
DTSTART:20181018T130000
DTEND:20181018T133000
LOCATION:APB 3027
DESCRIPTION:Abstract:\n"Combined approaches have become a successful technique for solving\nconjunctive query (CQ) answering over description logics (DL) ontologies.\nNevertheless\, existing approaches are restricted to tractable DL languages.\nIn this work\, we extend the combined method to the more expressive DL\nHorn-ALCHOIQ---a language for which CQ answering is ExpTime-complete—\nin order to develop an efficient and scalable CQ answering procedure which\nis worst-case optimal for \\halchoiq and \\elho ontologies. We implement and\nstudy the feasibility of our algorithm\, and compare its performance to the DL\nreasoner Konclude."\n\nThis is a rehearsal talk for KR 2018.
DTSTAMP:20181018T083532
SEQUENCE:26905
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient Model Construction for Horn Logic with VLog: Extended Abstract
URL://iccl.inf.tu-dresden.de/web/Efficient_Model_Construction_for_Horn_Logic_with_VLog:_Extended_Abstract
UID://iccl.inf.tu-dresden.de/web/Efficient_Model_Construction_for_Horn_Logic_with_VLog:_Extended_Abstract
DTSTART:20181011T130000
DTEND:20181011T143000
LOCATION:APB 3027
DESCRIPTION:Abstract: "We extend the Datalog engine VLog to develop a column-oriented implementation of the skolem and the restricted chase – two variants of a sound and complete algorithm used for model construction over theories of existential rules. We conduct an extensive evaluation over several data-intensive theories with millions of facts and thousands of rules\, and show that VLog can compete with the state of the art\, regarding runtime\, scalability\, and memory efficiency."\n\n\nThis is a rehearsal talk for the DL Workshop 2018.
DTSTAMP:20181018T013010
SEQUENCE:26721
END:VEVENT
BEGIN:VEVENT
SUMMARY:Report on research visit to NRC
URL://iccl.inf.tu-dresden.de/web/A_New_Semantic_Relatedness_Dataset_for_Evaluating_Compositional_Distributional_Models
UID://iccl.inf.tu-dresden.de/web/A_New_Semantic_Relatedness_Dataset_for_Evaluating_Compositional_Distributional_Models
DTSTART:20181004T130000
DTEND:20181004T143000
LOCATION:APB 3027
DTSTAMP:20181019T120001
SEQUENCE:26940
END:VEVENT
BEGIN:VEVENT
SUMMARY:Report on research visit to NRC
URL://iccl.inf.tu-dresden.de/web/Report_on_research_visit_to_NRC
UID://iccl.inf.tu-dresden.de/web/Report_on_research_visit_to_NRC
DTSTART:20181004T130000
DTEND:20181004T143000
LOCATION:APB 3027
DTSTAMP:20181019T140519
SEQUENCE:26945
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extending Matching in Description Logics
URL://iccl.inf.tu-dresden.de/web/Extending_Matching_in_Description_Logics
UID://iccl.inf.tu-dresden.de/web/Extending_Matching_in_Description_Logics
DTSTART:20180927T130000
DTEND:20180927T143000
LOCATION:APB 2026
DESCRIPTION:Matching concept descriptions against concept patterns was introduced as a non-standard inference task in Description Logics motivated by applications in knowledge bases. It was first investigated for the DL FL0\, for which a polynomial-time algorithm was obtained. In this talk\, we will present recent results that extend matching in FL0 in two aspects. Initially\, we investigate approximate matching\, that increases the recall of the method by checking whether the input description and pattern can “almost” match\, rather than become equivalent. The meaning of almost is formalised using distance measures between concepts. Afterwards\, we examine matching in the presence of TBoxes\, i.e.\, background knowledge of concept inclusions. It is well-known that subsumption reasoning in FL0 rises from P to ExpTime when TBoxes are considered\, and we prove that the same is true for matching. Finally\, we present some preliminary ideas on approximate matching in the presence of TBoxes.
DTSTAMP:20181018T013053
SEQUENCE:26723
END:VEVENT
BEGIN:VEVENT
SUMMARY:Complexity of Projection with Stochastic Actions in a Probabilistic Description Logic
URL://iccl.inf.tu-dresden.de/web/Complexity_of_Projection_with_Stochastic_Actions_in_a_Probabilistic_Description_Logic
UID://iccl.inf.tu-dresden.de/web/Complexity_of_Projection_with_Stochastic_Actions_in_a_Probabilistic_Description_Logic
DTSTART:20180920T130000
DTEND:20180920T143000
LOCATION:APB 3027
DESCRIPTION:Integrating probabilistic notions of uncertainty into languages for reasoning about actions is a popular approach to adequately deal for instance with possibly fallible acting and sensing. In this talk\, an action language extended with quantitative notions of uncertainty is considered. In our setting\, the initial beliefs of an agent are represented as a probabilistic knowledge base with axioms formulated in the Description Logic ALCO. Action descriptions describe the possibly context-sensitive and nondeterministic effects of actions and provide likelihood distributions over the different possible outcomes. A decidability result for the probabilistic projection problem\, which is the basic reasoning task needed for predicting the outcome of action sequences\, is presented. Furthermore\, I will talk about the problem of how the nondeterminism in the action model affects the complexity of the projection problem.
DTSTAMP:20181018T013111
SEQUENCE:26724
END:VEVENT
BEGIN:VEVENT
SUMMARY:Faceted Answer-Set Navigation
URL://iccl.inf.tu-dresden.de/web/Faceted_Answer-Set_Navigation
UID://iccl.inf.tu-dresden.de/web/Faceted_Answer-Set_Navigation
DTSTART:20180906T130000
DTEND:20180906T143000
LOCATION:APB 3027
DESCRIPTION:Abstract: Even for small logic programs\, the number of resulting answer-sets can be tremendous. In such cases\, users might be incapable of comprehending the space of answer-sets as a whole nor being able to identify a specific answer-set according to their needs. To overcome this difficulty\, we propose a general formal framework that takes an arbitrary logic program as input\, and allows for navigating the space of answer-sets in a systematic interactive way analogous to faceted browsing. The navigation is carried out stepwise\, where each step narrows down the remaining solutions\, eventually arriving at a single one. We formulate two navigation modes\, one stringent conflict avoiding\, and a “free” mode\, where conflicting selections of facets might occur. For the latter mode\, we provide efficient algorithms for resolving the conflicts. We provide an implementation of our approach and demonstrate that our framework is able to handle logic programs for which it is currently infeasible to retrieve all answer sets.\n\n\nThis is joint work with Sebastian Rudolph and Lukas Schweizer\, to appear in the Proceedings of the 2nd International Joint Conference on Rules and Reasoning\, 2018.
DTSTAMP:20181018T013124
SEQUENCE:26725
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weighted Model Counting on the GPU by Exploiting Small Treewidth
URL://iccl.inf.tu-dresden.de/web/Weighted_Model_Counting_on_the_GPU_by_Exploiting_Small_Treewidth
UID://iccl.inf.tu-dresden.de/web/Weighted_Model_Counting_on_the_GPU_by_Exploiting_Small_Treewidth
DTSTART:20180830T130000
DTEND:20180830T143000
LOCATION:APB 3027
DESCRIPTION:We propose a novel solver that efficiently finds almost the exact number of solutions of a Boolean formula (#Sat) and the weighted model count of a weighted Boolean formula (WMC) if the treewidth of the given formula is sufficiently small. The basis of our approach are dynamic programming algorithms on tree decompositions\, which we engineered towards efficient parallel execution on the GPU. We provide thorough experiments and compare the runtime of our system with state-of-the-art #Sat and WMC solvers. Our results are encouraging in the sense that also complex reasoning problems can be tackled by parameterized algorithms executed on the GPU if instances have treewidth at most 30\, which is the case for more than half of counting and weighted counting benchmark instances.
DTSTAMP:20181018T013201
SEQUENCE:26727
END:VEVENT
BEGIN:VEVENT
SUMMARY:Classification of the finite polymorphism-homogeneous tournaments with loops
URL://iccl.inf.tu-dresden.de/web/Classification_of_the_finite_polymorphism-homogeneous_tournaments_with_loops
UID://iccl.inf.tu-dresden.de/web/Classification_of_the_finite_polymorphism-homogeneous_tournaments_with_loops
DTSTART:20180823T130000
DTEND:20180823T143000
LOCATION:APB 3027
DESCRIPTION:The classical notion of "homogeneity" plays a part in model theory. In this talk we look at a variant of this property\, the so called "polymorphism-homogeneity"\, first explicitly examined by Christian and Maja Pech\, by classifying the finite tournaments (loops allowed)\, which are polymorphism-homogeneous. For this we utilize the classification of the finite homomorphism-homogeneous tournaments with loops\, done by A. Ilić\, D. Mašulović and U. Rajković.
DTSTAMP:20181018T013335
SEQUENCE:26728
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Single Approach to Decide Chase Termination on Linear Existential Rules
URL://iccl.inf.tu-dresden.de/web/A_Single_Approach_to_Decide_Chase_Termination_on_Linear_Existential_Rules
UID://iccl.inf.tu-dresden.de/web/A_Single_Approach_to_Decide_Chase_Termination_on_Linear_Existential_Rules
DTSTART:20180809T130000
DTEND:20180809T143000
LOCATION:APB 3027
DESCRIPTION:**Abstract:** Existential rules are a knowledge representation and reasoning formalism that extends both positive rules a la Datalog and most description logics used in ontology-based query answering. The chase is a fundamental tool for reasoning on knowledge bases composed of an instance and a set of existential rules. It is well-known that deciding\, given a chase variant and a set of existential rules\, whether the chase will halt for any instance is an undecidable problem. Hence\, a crucial issue is whether it becomes decidable for known classes of existential rules. We focus on three main chase variants\, namely semi-oblivious\, restricted and core chase\, and consider linear existential rules\, a simple yet important subclass of existential rules. We show that the termination problem is decidable in these three variants with a novel unified approach based on a single graph and a single notion of forbidden pattern.\n\nJoint work with M. Leclère\, M.-L. Mugnier and F. Ulliana.\n\n**Speaker Bio:** Michaël Thomazo is an INRIA researcher (CEDAR team)\, currently working on ontology-based query answering\, and especially efficient evaluation of reformulated queries. He had been a post-doc at TU Dresden\, working with S. Rudolph\, and got his Ph.D from the University of Montpellier\, supervised by J.-F. Baget and M.-L. Mugnier. You can find more details at http://pages.saclay.inria.fr/michael.thomazo/.
DTSTAMP:20181018T013523
SEQUENCE:26730
END:VEVENT
BEGIN:VEVENT
SUMMARY:Modal Separation Logic: an ongoing quest for elementary complexity
URL://iccl.inf.tu-dresden.de/web/Modal_Separation_Logic:_an_ongoing_quest_for_elementary_complexity
UID://iccl.inf.tu-dresden.de/web/Modal_Separation_Logic:_an_ongoing_quest_for_elementary_complexity
DTSTART:20180808T130000
DTEND:20180808T140000
LOCATION:TBA
DESCRIPTION:The talk will be dedicated to my recent work on Quantified Computation Tree Logic (QCTL) with Stephane Demri (LSV at ENS P-S\, France) and my ongoing work \nwith Stephane and Raul Fervari (Universidad Nacional de Córdoba\, Argentina) \non Modal Separation Logic (MSL).\n\n'''Abstract:''' Modal separation logic MSL is a logic introduced recently by Demri and Fervari \nin [DF-aiml18]\, whose models are memory states as in separation logic and \nthe logical connectives include modal operators as well as separating \nconjunction and magic wand. With these operators\, some fragments of MSL can be \nseen as genuine modal logics whereas some others capture standard separation \nlogics\, leading to an original language to speak about memory states. \nThe decidability status and the computational complexity of several fragments \nof MSL were established in [DF-aiml18]\, leading to surprising hardness or \neasiness results\, obtained by designing proof methods that take into \naccount the modal and separation features of MSL.\n\nWe will focus on a fragment of MSL\, where only <>^{-1} (predecessor) \nand * (separating conjunction) operators are allowed. It is not hard to see that\nsuch a fragment is decidable by employing a theorem about decidability of MSO \nwith one functional symbol. However the exact complexity of the logic remains \nunknown. During the talk I will present an approach to solve this problem by \ntranslating MSL into QCTL_EX\, an extension of well-known CTL (where only EX \noperator is allowed) with propositional quantification. We will see how this \napproach failed\, but as a sub-product we obtain several nice complexity and \nexpressivity results for QCTL_EX. We will also see what makes QCTL_EX hard \nand why there is still a chance that the mentioned fragment of MSL could \nhave an elementary complexity.\n\n[DF-aiml18] S. Demri and R. Fervari. On the complexity of modal separation logics. In AiML'18. College Publications\, August 2018. To appear.\n\n'''Bio:''' Bartosz Bednarczyk - University of Wrocław & LSV ENS Paris-Saclay & University of Oxford
DTSTAMP:20181019T105240
SEQUENCE:26936
END:VEVENT
BEGIN:VEVENT
SUMMARY:Towards Conjunctive Query Answering in Defeasible EL_bot
URL://iccl.inf.tu-dresden.de/web/Towards_Conjunctive_Query_Answering_in_Defeasible_EL_bot
UID://iccl.inf.tu-dresden.de/web/Towards_Conjunctive_Query_Answering_in_Defeasible_EL_bot
DTSTART:20180726T130000
DTEND:20180726T143000
LOCATION:APB 3027
DESCRIPTION:In Defeasible Description Logics (DDLs)\, typical or default information about concepts can be stated in the form of defeasible concept inclusions (DCIs) in a DBox. As opposed to general concept inclusions (GCIs)\, which are strict in the sense that e.g. "every element of C must be an element of D"\, defeasible statements are more vague and allow to state that "elements of C are usually elements of D"\, where the term usually insinuates that DCIs are satisfied individually for elements not satisfying properties contradicting the DCI. In 2017\, we have discovered and resolved a severe shortcoming of earlier approaches to define semantics for DDLs rooted in the preferential approach by KLM. We introduce a new kind of canonical model in order to determine consequences in defeasible EL_bot. These so-called typicality models extend classical canonical models by additional concept representatives\, which are individually forced to satisfy certain DCIs. Typicality models allow us to reconstruct the consequences obtained by previous approaches and extend them appropriately to alleviate the discovered insufficiency. More recently\, we have extended this formalism beyond the reasoning service subsumption\, to also be capable of deciding defeasible instance checks.\n\nThe natural next step is to strengthen the deductive power of our formalism to enable conjunctive query answering (CQA) in defeasible EL_bot\, a reasoning service that\, to the best of our knowledge\, has not been studied for DDLs. We conjecture that the query rewriting approach by Lutz et al. (2009)\, allowing the use of classical canonical models to answer conjunctive queries\, can be adopted to answer defeasible conjunctive queries by using typicality models\, due to their canonical nature.\n\nThis endeavour is still in its very early stages and aspects of this talk concerning CQA are preliminary ideas and working theories. Input and feedback from the audience is greatly appreciated.
DTSTAMP:20181018T013556
SEQUENCE:26731
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Dichotomy for Evaluating Simple Regular Path Queries
URL://iccl.inf.tu-dresden.de/web/A_Dichotomy_for_Evaluating_Simple_Regular_Path_Queries
UID://iccl.inf.tu-dresden.de/web/A_Dichotomy_for_Evaluating_Simple_Regular_Path_Queries
DTSTART:20180705T130000
DTEND:20180705T143000
LOCATION:APB 3027
DESCRIPTION:Regular path queries (RPQs) are a central component of graph databases. We investigate decision- and enumeration problems concerning the evaluation of RPQs under several semantics that have recently been considered: arbitrary paths\, shortest paths\, and simple paths.\nWhereas arbitrary and shortest paths can be enumerated in polynomial delay\, the situation is much more intricate for simple paths. For instance\, already the question if a given graph contains a simple path of a certain length has cases with highly non-trivial solutions and cases that are long-standing open problems. We study RPQ evaluation for simple paths from a parameterized complexity perspective and define a class of simple transitive expressions that is prominent in practice and for which we can prove a dichotomy for the evaluation problem. We observe that\, even though simple path semantics is intractable for RPQs in general\, it is feasible for the vast majority of RPQs that are used in practice. At the heart of our study on simple paths is a result of independent interest: the two disjoint paths problem in directed graphs is W[1]-hard if parameterized by the length of one of the two paths.\n\n'''Bio:''' Wim Martens is a professor for Theoretical Computer Science at the University of Bayreuth. He is interested in theoretical aspects of data management\, formal language theory\, logic\, and complexity. He was an invited speaker at STOC 2017 and his research received several awards\, including the ACM SIGMOD research highlight award and the Dissertation Award for Computer Science\, Belgium. Currently\, he is on the editorial board of ACM TODS and he is chairing the ICDT Council. His talk reports about research for which he recently received the Best Paper Award of the International Conference on Database Theory 2018.
DTSTAMP:20181019T105441
SEQUENCE:26938
END:VEVENT
BEGIN:VEVENT
SUMMARY:Provenance and Probabilities in Relational Databases
URL://iccl.inf.tu-dresden.de/web/Provenance_and_Probabilities_in_Relational_Databases
UID://iccl.inf.tu-dresden.de/web/Provenance_and_Probabilities_in_Relational_Databases
DTSTART:20180622T093000
DTEND:20180622T110000
LOCATION:APB 3027
DESCRIPTION:We review the basics of data provenance in relational databases. We describe different provenance formalisms\, from Boolean provenance to provenance semirings and beyond\, that can be used for a wide variety of purposes\, to obtain additional information on the output of a query. We discuss representation systems for data provenance\, circuits in particular\, with a focus on practical implementation. Finally\, we explain how provenance is practically used for probabilistic query evaluation in probabilistic databases.\n\n\n'''Bio:''' Pierre Senellart is a Professor in the Computer Science Department at the École normale supérieure (ENS\, PSL University) in Paris\, France\, and an Adjunct Professor at Télécom ParisTech. He is an alumnus of ENS and obtained his M.Sc. (2003) and Ph.D. (2007) in computer science from Université Paris-Sud\, studying under the supervision of Serge Abiteboul. Before joining ENS\, he was an Associate Professor (2008–2013) then a Professor (2013–2016) at Télécom ParisTech. He also held secondary appointments as Lecturer at the University of Hong Kong in 2012–2013\, and as Senior Research Fellow at the National University of Singapore from 2014 to 2016. His research interests focus around practical and theoretical aspects of Web data management\, including Web crawling and archiving\, Web information extraction\, uncertainty management\, Web mining\, and intensional data management.
DTSTAMP:20181019T105352
SEQUENCE:26937
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Combined Approach to Query Answering in Horn-ALCHOIQ
URL://iccl.inf.tu-dresden.de/web/The_Combined_Approach_to_Query_Answering_in_Horn-ALCHOIQ
UID://iccl.inf.tu-dresden.de/web/The_Combined_Approach_to_Query_Answering_in_Horn-ALCHOIQ
DTSTART:20180607T130000
DTEND:20180607T143000
LOCATION:APB 3027
DESCRIPTION:Abstract: "Combined approaches have become a successful technique for solving conjunctive query (CQ) answering over description logics (DL) ontologies. Nevertheless\, existing approaches are restricted to tractable DL languages. In this work\, we extend the combined method to the more expressive DL Horn-ALCHOIQ—a language for which CQ answering is EXPTIME-complete—in order to develop an efficient and scalable CQ answering procedure which is worst case optimal for Horn-ALCHOIQ and ELHO ontologies. We implement and study the feasibility of our algorithm\, and compare its performance to the DL reasoner Konclude." \n\n\nThis paper has been submitted to KR 2018. The extended technical report can be found at https://iccl.inf.tu-dresden.de/web/Techreport3024/en.
DTSTAMP:20181018T013645
SEQUENCE:26734
END:VEVENT
BEGIN:VEVENT
SUMMARY:Efficient Model Construction for Horn Logic with VLog
URL://iccl.inf.tu-dresden.de/web/Efficient_Model_Construction_for_Horn_Logic_with_VLog
UID://iccl.inf.tu-dresden.de/web/Efficient_Model_Construction_for_Horn_Logic_with_VLog
DTSTART:20180531T130000
DTEND:20180531T143000
LOCATION:APB 3027
DESCRIPTION:Abstract: \n "We extend the Datalog engine VLog to develop a column-oriented\nimplementation of the skolem and the restricted chase – two variants of a sound\nand complete algorithm used for model construction over theories of existential\nrules. We conduct an extensive evaluation over several data-intensive theories\nwith millions of facts and thousands of rules\, and show that VLog can compete\nwith the state of the art\, regarding runtime\, scalability\, and memory efficiency."\n\nThis work was developed is a collaboration with Jacopo Urbani and Ceriel Jacobs from Vrije Universiteit Amsterdam. \nThe paper will be presented and published at IJCAR 2018. It is available at https://iccl.inf.tu-dresden.de/web/Article3046/en.
DTSTAMP:20181018T013657
SEQUENCE:26735
END:VEVENT
BEGIN:VEVENT
SUMMARY:A proof of CSP Dichotomy conjecture
URL://iccl.inf.tu-dresden.de/web/A_proof_of_CSP_Dichotomy_conjecture
UID://iccl.inf.tu-dresden.de/web/A_proof_of_CSP_Dichotomy_conjecture
DTSTART:20180525T131500
DTEND:20180525T144500
LOCATION:WIL/C115\, or in WIL/C204 if more space is needed
DESCRIPTION:Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general\, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NP-complete. It was conjectured that if a constraint language has a weak near unanimity polymorphism then the corresponding constraint satisfaction problem is tractable\, otherwise it is NP-complete. The hardness result is known since 2001. We present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism\, which proves the remaining part of the conjecture.
DTSTAMP:20180517T104618
SEQUENCE:25823
END:VEVENT
BEGIN:VEVENT
SUMMARY:Adaptive Language Interaction
URL://iccl.inf.tu-dresden.de/web/Adaptive_Language_Interaction
UID://iccl.inf.tu-dresden.de/web/Adaptive_Language_Interaction
DTSTART:20180503T110000
DTEND:20180503T123000
LOCATION:APB 1004
DESCRIPTION:This talk is part of Dresden Talks on Interaction & Visualization: \n\n\nLanguage-based interaction with digital agents (e.g. Siri\, Alexa) has become ubiquitous\, and is used in various situations and by an increasingly large variety of different users. Research shows however that a dialog system should not just be able to understand and generate language correctly\, but that it should also adapt the way it formulates its messages to fit the user and the situation (for instance\, it should use simpler formulations to avoid distraction during driving).\n\nIn this talk\, I will start out by presenting an information-theoretic measure\, surprisal\, as a way of quantifying linguistically induced cognitive load on a word-by-word basis. I will then proceed to talk about neural network models that we have recently developed to estimate semantic surprisal\, i.e. the amount of cognitive load that will be caused by an unexpected word like "bathtub" in context\, such as "I did the dishes in the bathtub.".\n\nFinally\, I will report on our recent work using a novel pupillometry-based measure of cognitive load\, the Index of Cognitive Activity (ICA)\, which allows us to assess cognitive load in dual task settings such as driving a car.
DTSTAMP:20180418T103555
SEQUENCE:25660
END:VEVENT
BEGIN:VEVENT
SUMMARY:A pragmatic approach to translation: Vocabulary alignment through Multiagent Interaction and Observation
URL://iccl.inf.tu-dresden.de/web/A_pragmatic_approach_to_translation:_Vocabulary_alignment_through_Multiagent_Interaction_and_Observation
UID://iccl.inf.tu-dresden.de/web/A_pragmatic_approach_to_translation:_Vocabulary_alignment_through_Multiagent_Interaction_and_Observation
DTSTART:20180426T130000
DTEND:20180426T143000
LOCATION:APB 3027
DESCRIPTION:Talk by: Paula Chocrón \nInstitute: Artificial Intelligence Research Institute (IIIA-CSIC)\, Barcelona\, Spain \n\nAbstract: \n"Every speaker that has been abroad knows that understanding a foreign language is easier when performing simple\, well-defined interactions. For example\, it is easier to ask for a coffee than to discuss politics in a language we do not master. In this talk I will discuss how this idea can be applied to help achieve meaningful communication in artificial multi-agent systems. In open\, heterogeneous environments\, it is likely that interlocutors with different backgrounds use different languages. Can the contextual information about the tasks being performed be used to learn a translation that allows agents to interact?"\n\nI will start by presenting a notion of context that is based on the formal specifications of the tasks performed by agents. I will then show how this context can be used by agents to align their vocabularies dynamically\, by learning mappings from the experience of previous interactions. In doing so\, we will also rethink the traditional approach to semantic matching and its evaluation\, tackling the following questions: What does it mean for agents to "understand each other"? When is an alignment good for a particular application? Finally\, I will present an application to agents that interact using procedural protocols obtained from the WikiHow website\, showing how they can infer a translation between English and Spanish without using external resources.
DTSTAMP:20181018T013833
SEQUENCE:26736
END:VEVENT
BEGIN:VEVENT
SUMMARY:Getting the most out of Wikidata: Semantic Technology Usage in Wikipedia’s Knowledge Graph
URL://iccl.inf.tu-dresden.de/web/Seminar_talk,_title:_%22Practical_Linked_Data_Access_via_SPARQL:_The_Case_of_Wikidata%22
UID://iccl.inf.tu-dresden.de/web/Seminar_talk,_title:_%22Practical_Linked_Data_Access_via_SPARQL:_The_Case_of_Wikidata%22
DTSTART:20180420T095000
DTEND:20180420T110000
LOCATION:APB 3105
DESCRIPTION:Abstract:\n"Wikidata\, the knowledge base of Wikimedia\, has been extremely successful in building and sustaining new communities of editors and users. Since its inception in 2012\, it has developed from an experimental “data wiki” into a well-organised reference knowledge base with an amazing array of applications. You can now come across Wikidata content in your mobile phone\, in newspaper articles\, and even in aeroplanes. A key towards this success has been the development of a whole ecosystem of tools and APIs for accessing\, querying\, and analysing Wikidata content. The most prominent such feature is Wikidata's powerful query service\, which is based on the Semantic Web data exchange standard RDF and its related query language SPARQL. The talk will give an overview over these developments and focus specifically on the possibilities and current usage of SPARQL on Wikidata."\n\nThis is joined work with Adrian Bielefeldt and Julius Gonsior. The paper is at https://iccl.inf.tu-dresden.de/web/Inproceedings3196. This talk is a preparation for the presentation at WWW.
DTSTAMP:20180420T062015
SEQUENCE:25678
END:VEVENT
BEGIN:VEVENT
SUMMARY:Integrating Semantic Web in the Real World: A journey between two cities
URL://iccl.inf.tu-dresden.de/web/Integrating_Semantic_Web_in_the_Real_World:_A_journey_between_two_cities
UID://iccl.inf.tu-dresden.de/web/Integrating_Semantic_Web_in_the_Real_World:_A_journey_between_two_cities
DTSTART:20180420T090000
DTEND:20180420T095000
LOCATION:APB 3105
DESCRIPTION:Abstract: \n"An early vision in Computer Science has been to create intelligent systems capable of reasoning on large amounts of data. Today\, this vision can be delivered by integrating Relational Databases with the Semantic Web using the W3C standards: a graph data model (RDF)\, ontology language (OWL)\, mapping language (R2RML) and query language (SPARQL). The research community has successfully been showing how intelligent systems can be created with Semantic Web technologies\, dubbed now as Knowledge Graphs. However\, where is the mainstream industry adoption? What are the barriers to adoption? Are these engineering and social barriers or are they open scientific problems that need to be addressed? This talk will chronicle our journey of deploying Semantic Web technologies with real world users to address Business Intelligence and Data Integration needs\, describe technical and social obstacles that are present in large organizations\, and scientific and engineering challenges that require attention."\n\n\nSpeaker's Biography:\nJuan F. Sequeda is the co-founder of Capsenta\, a spin-off from his research\, and the Senior Director of Capsenta Labs. He holds a PhD in Computer Science from the University of Texas at Austin. His research interests are on the intersection of Logic and Data and in particular between the Semantic Web and Relational Databases for data integration\, ontology based data access and semantic/graph data management. Juan is the recipient of the NSF Graduate Research Fellowship\, received 2nd Place in the 2013 Semantic Web Challenge for his work on ConstituteProject.org\, Best Student Research Paper at the 2014 International Semantic Web Conference and the 2015 Best Transfer and Innovation Project awarded by Institute for Applied Informatics. Juan is the General Chair of 2018 Alberto Mendelzon Workshop on Foundations of Databases (AMW2018)\, was the PC chair of the ISWC 2017 In-Use track\, is on the Editorial Board of the Journal of Web Semantics and member of multiple program committees (ISWC\, ESWC\, WWW\, AAAI\, IJCAI). Juan is a member of the Linked Data Benchmark Council (LDBC) Graph Query Languages task force and has also been an invited expert and standards editor at the World Wide Web Consortium (W3C).
DTSTAMP:20181018T013853
SEQUENCE:26737
END:VEVENT
BEGIN:VEVENT
SUMMARY:Learning Word Representation in Compositional Matrix-Space Models
URL://iccl.inf.tu-dresden.de/web/Learning_Word_Representation_in_Compositional_Matrix-Space_Models
UID://iccl.inf.tu-dresden.de/web/Learning_Word_Representation_in_Compositional_Matrix-Space_Models
DTSTART:20180412T130000
DTEND:20180412T143000
LOCATION:APB 3027
DESCRIPTION:Learning word representations to capture the semantics and compositionality of language has received much research interest in natural language processing. Beyond the popular vector space models for word representations and compositionality\, Compositional Matrix-Space Models (CMSMs) have been proposed. In this talk\, I introduce the principle idea of CMSM and its application in NLP tasks. Then\, I address the problem of learning matrix representation of words in CMSMs for the task of fine-grained sentiment analysis. I show that our approach\, which learns the word matrices gradually in two steps\, outperforms other approaches in CMSMs in terms of quality and computational cost.
DTSTAMP:20181018T013913
SEQUENCE:26738
END:VEVENT
BEGIN:VEVENT
SUMMARY:Second Workshop on Human Reasoning and Computational Logic
URL://iccl.inf.tu-dresden.de/web/Second_Workshop_on_Human_Reasoning_and_Computational_Logic
UID://iccl.inf.tu-dresden.de/web/Second_Workshop_on_Human_Reasoning_and_Computational_Logic
DTSTART:20180410T090000
DTEND:20180412T180000
LOCATION:APB 2026
DESCRIPTION:From the 10th to the 12th of April 2018\, we organize the second workshop on Human Reasoning and Computational Logic at TU Dresden\, Germany. The goal of this workshop is to provide a platform for the scientific exchange with respect to Human Reasoning between the areas of Cognitive Science and Computational Logic.
DTSTAMP:20180306T115908
SEQUENCE:25240
END:VEVENT
BEGIN:VEVENT
SUMMARY:Modelling Dynamics in Semantic Web Knowledge Graphs with Formal Concept Analysis
URL://iccl.inf.tu-dresden.de/web/Modelling_Dynamics_in_Semantic_Web_Knowledge_Graphs_with_Formal_Concept_Analysis
UID://iccl.inf.tu-dresden.de/web/Modelling_Dynamics_in_Semantic_Web_Knowledge_Graphs_with_Formal_Concept_Analysis
DTSTART:20180405T130000
DTEND:20180405T143000
LOCATION:APB 3027
DESCRIPTION:In this paper\, we propose a novel data-driven schema for large-scale heterogeneous knowledge graphs inspired by Formal Concept Analysis (FCA). We first extract the sets of properties associated with individual entities\; these property sets (aka. characteristic sets) are annotated with cardinalities and used to induce a lattice based on set-containment relations\, forming a natural hierarchical structure describing the knowledge graph. We then propose an algebra over such schema lattices\, which allows to compute diffs between lattices (for example\, to summarise the changes from one version of a knowledge graph to another)\, to add lattices (for example\, to project future changes)\, and so forth. While we argue that this lattice structure (and associated algebra) may have various applications\, we currently focus on the use-case of modelling and predicting the dynamic behaviour of knowledge graphs. We instantiate and evaluate our methods for analysing how versions of the Wikidata knowledge graph have changed over a period of 11 weeks. We propose algorithms for constructing the lattice-based schema from Wikidata\, and evaluate their efficiency and scalability. We then evaluate use of the resulting schema(ta) for predicting how the knowledge graph will evolve in future versions.\n\n\nAuthors: Larry Gonzalez and Aidan Hogan
DTSTAMP:20181018T013940
SEQUENCE:26739
END:VEVENT
BEGIN:VEVENT
SUMMARY:Functional models and Data Complexity for FL0
URL://iccl.inf.tu-dresden.de/web/Functional_models_and_Data_Complexity_for_FL0
UID://iccl.inf.tu-dresden.de/web/Functional_models_and_Data_Complexity_for_FL0
DTSTART:20180315T092000
DTEND:20180315T105000
LOCATION:APB 3027
DESCRIPTION:In the early days of Description Logic research\, the inexpressive DL FL0 was considered to be the smallest possible DL. When it was later shown that subsumption reasoning wrt general TBoxes is as hard as for the more expressive ALC\, the community lost interest in this DL. However\, the recent approach of reasoning with so-called functional models has rekindled the interest\, since\, on the one hand it has the potential to outperform ALC reasoners (even though it stays ExpTime-hard in the worst case)\, and on the other hand\, it has already helped in answering open problems about non-standard inferences for FL0\, like existence and computation of least common subsumer and most specific concept\, and the exact data complexity of query answering.\nIn this talk\, we will describe the approach of functional models\, and demonstrate how it has been used to show that answering instance queries for FL0 is tractable regarding data complexity.
DTSTAMP:20181018T014002
SEQUENCE:26740
END:VEVENT
BEGIN:VEVENT
SUMMARY:Preserving Constraints with the Stable Chase
URL://iccl.inf.tu-dresden.de/web/Preserving_Constraints_with_the_Stable_Chase
UID://iccl.inf.tu-dresden.de/web/Preserving_Constraints_with_the_Stable_Chase
DTSTART:20180308T092000
DTEND:20180308T105000
LOCATION:APB 3027
DESCRIPTION:Conjunctive query answering over databases with constraints – also known as (tuple-generating)\ndependencies – is considered a central database task. To this end\, several versions of a con-\nstruction called chase have been described. Given a set Σ of dependencies\, it is interesting to\nask which constraints not contained in Σ that are initially satisfied in a given database instance\nare preserved when computing a chase over Σ. Such constraints are an example for the more\ngeneral class of incidental constraints\, which when added to Σ as new dependencies do not affect\ncertain answers and might even speed up query answering. After formally introducing incidental\nconstraints\, we show that deciding incidentality is undecidable for tuple-generating dependencies\,\neven in cases for which query entailment is decidable. For dependency sets with a finite universal\nmodel\, the core chase can be used to decide incidentality. For the infinite case\, we propose the\nstable chase\, which generalises the core chase\, and study its relation to incidental constraints.
DTSTAMP:20181018T014018
SEQUENCE:26741
END:VEVENT
BEGIN:VEVENT
SUMMARY:Notes on Computational Learning Theory and the problem of learning CNFs
URL://iccl.inf.tu-dresden.de/web/Notes_on_Computational_Learning_Theory_and_the_problem_of_learning_CNFs
UID://iccl.inf.tu-dresden.de/web/Notes_on_Computational_Learning_Theory_and_the_problem_of_learning_CNFs
DTSTART:20180301T092000
DTEND:20180301T105000
LOCATION:APB 3027
DESCRIPTION:This is an informal talk where I first talk about the PAC learning model and the classical problem of learning the CNF class. Then I will present the MVDF class\, which non-trivially lies between Horn and CNF\, and discuss some results related to this class in the PAC learning model extended with membership queries.
DTSTAMP:20181018T014031
SEQUENCE:26742
END:VEVENT
BEGIN:VEVENT
SUMMARY:VLog: A Column-oriented Rule-Based Engine
URL://iccl.inf.tu-dresden.de/web/VLog:_A_Column-oriented_Rule-Based_Engine
UID://iccl.inf.tu-dresden.de/web/VLog:_A_Column-oriented_Rule-Based_Engine
DTSTART:20180222T092000
DTEND:20180222T105000
LOCATION:APB 3027
DESCRIPTION:In this talk\, I will first introduce our young research group in Amsterdam which is concerned with the design and implementation of efficient large-scale systems for AI. Then\, I will present VLog\, one of such a systems which is designed to execute Datalog reasoning and is developed in collaboration with TUD. VLog adopts the distinctive approach of computing the Datalog materialisation by storing the inference with a columnar layout. It has been shown that columnar relational technology can execute efficiently analytical SQL queries\, but it deals poorly with updates. For Datalog queries\, however\, the problem of updates can be avoided altogether by working in append-only mode and by producing the inferences one "set-at-a-time” instead of one "fact-at-a-time”. I will first introduce the core design principles of VLog\, and describe how its approach leads to good data compression and allows the implementation of techniques for avoiding duplicates. Then\, I will present some experiments and give a short demo that illustrates its potential on large knowledge bases. In the last part of the talk\, I will briefly report on some ongoing work on extending VLog to handle existentially quantified rules\, statistical inference\, and on a novel machine learning technique for improving query-driven evaluation.
DTSTAMP:20181018T014100
SEQUENCE:26743
END:VEVENT
BEGIN:VEVENT
SUMMARY:12. EMCL Workshop
URL://iccl.inf.tu-dresden.de/web/12th_EMCL_Workshop
UID://iccl.inf.tu-dresden.de/web/12th_EMCL_Workshop
DTSTART:20180220T090000
DTEND:20180221T170000
DESCRIPTION:Am 20. und 21. Februar findet der 12. Workshop der EMCL-Studenten in Dresden statt.\nDer Workshop wird durch die Studenten des Europäischem Master Programm in Computational Logic der Universitäten Bozen\, Dresden\, Wien und Lissabon selbst organisiert und beinhaltet Vorträge der Studierenden\, Alumni\, Doktoranten und anderer Wissenschaftler über ihre Forschungsprojekte. Dabei wird der Best Master Thesis Award 2017 verliehen.
DTSTAMP:20180201T081004
SEQUENCE:25054
END:VEVENT
BEGIN:VEVENT
SUMMARY:STEP by Step\, towards Smart Services
URL://iccl.inf.tu-dresden.de/web/STEP_by_Step,_towards_Smart_Services
UID://iccl.inf.tu-dresden.de/web/STEP_by_Step,_towards_Smart_Services
DTSTART:20180208T092000
DTEND:20180208T105000
LOCATION:APB 3027
DESCRIPTION:The past few years have been marked by the increased use of sensor technologies\, abundant availability of mobile devices\, and growing popularity of wearables\, which enable the direct integration of their data as part of rich client applications. Despite the potential and added value that such aggregate applications bring\, the implementations are usually custom solutions for particular use cases and do not support easy integration of further devices. To this end\, the vision of the Web of Things (WoT) is to leverage Web standards in order to interconnect all types of devices and real-world objects\, and thus to make them a part of the World Wide Web (WWW) and provide overall interoperability. Especially in the context of Industry 4.0\, where processes\, hardware and applications are integrated beyond the individual companies’ borders\, interoperability\, connectivity and data integration are key for developing Smart Services – a vision of tomorrow's way of delivering services\, which build on top of intelligent machines and products that communicate with each other\, cooperatively driving production. Within this setup\, the STEP project aims to provide architectural solutions\, process optimisation\, and data representation approaches that support the realisation of predictive.
DTSTAMP:20181018T014112
SEQUENCE:26744
END:VEVENT
BEGIN:VEVENT
SUMMARY:SOQE 2017: Workshop on Second-Order Quantifier Elimination and Related Topics
URL://iccl.inf.tu-dresden.de/web/SOQE_2017
UID://iccl.inf.tu-dresden.de/web/SOQE_2017
DTSTART:20171206T090000
DTEND:20171208T180000
DESCRIPTION:Workshop on Second-Order Quantifier Elimination and Related Topics
DTSTAMP:20170913T104347
SEQUENCE:24073
END:VEVENT
BEGIN:VEVENT
SUMMARY:Generalized Consistent Query Answering under Existential Rules
URL://iccl.inf.tu-dresden.de/web/Generalized_Consistent_Query_Answering_under_Existential_Rules
UID://iccl.inf.tu-dresden.de/web/Generalized_Consistent_Query_Answering_under_Existential_Rules
DTSTART:20171130T092000
DTEND:20171130T105000
LOCATION:APB 3027
DESCRIPTION:In the talk\, I give an overview of recent results on generalised consistent query answering under existential rules. Previous work has proposed consistent query answering as a way to resolve inconsistencies in ontologies. In these approaches to consistent query answering\, however\, only inconsistencies due to errors in the underlying database are considered. In recent works\, we additionally assume that ontological axioms may be erroneous\, and that some database atoms and ontological axioms may not be removed to resolve inconsistencies. This problem is especially well suited in debugging mappings between distributed ontologies. We define two different semantics\, one where ontological axioms as a whole are ignored to resolve an inconsistency\, and one where only some of their instances are ignored. We then give a precise picture of the complexity of consistent query answering under these two semantics when ontological axioms are encoded as different classes of existential rules.
DTSTAMP:20181018T014144
SEQUENCE:26745
END:VEVENT
BEGIN:VEVENT
SUMMARY:Body-Mind-Language: Embodied Cognition in Natural Language
URL://iccl.inf.tu-dresden.de/web/Body-Mind-Language:_Embodied_Cognition_in_Natural_Language
UID://iccl.inf.tu-dresden.de/web/Body-Mind-Language:_Embodied_Cognition_in_Natural_Language
DTSTART:20171123T092000
DTEND:20171123T105000
LOCATION:APB 3027
DESCRIPTION:Embodied cognition starts from the assumption that conceptual structure in our minds derives from sensorimotor experiences. Cognitive linguistics has provided compelling evidence that semantic structure in natural language reflects that conceptual structure arising from our embodied experience in the world. Thus\, natural language provides an excellent source of knowledge to study embodied cognition. To capture this cognitive conceptual structure\, a set of spatio-temporal building blocks called image schemas was introduced by George Lakoff and Mark Johnson. Detecting image schemas in natural language can provide further insights into how we encode embodied experiences in our communication and potentially contribute to research on conceptual understanding and symbol grounding in cognitive systems. However\, due to their abstract nature and lack of formalization they are difficult to detect in language. \n\nIn this talk\, I will first briefly introduce the general idea of image schemas\, which has been presented to this group before by my co-author Maria Hedblom\, and then proceed to machine learning techniques to extract them from multilingual text. Furthermore\, I will provide a short overview on existing approaches and our ongoing work on formalizing image schemas.
DTSTAMP:20181018T014201
SEQUENCE:26746
END:VEVENT
BEGIN:VEVENT
SUMMARY:SQID: Reasonable Wikidata
URL://iccl.inf.tu-dresden.de/web/SQID:_Reasonable_Wikidata
UID://iccl.inf.tu-dresden.de/web/SQID:_Reasonable_Wikidata
DTSTART:20171109T092000
DTEND:20171109T105000
DESCRIPTION:SQID is a data browser for Wikidata that integrates data from various\nsources\, including the Wikidata Query service\, the Wikidata API\,\nWikidata dumps (analysed offline)\, and further Wikimedia sources. It\nfeatures class and property browsers\, and provides a concise display of\nboth outgoing and incoming statements for items.\n\nA recent addition to SQID is the integration of proposals from Primary\nSources\, where proposed references may be approved or rejected with just\na single click.\n\nWe extend SQID with a reasoning component that is able to infer new\nstatements from existing data. These rules can be used to:\n- materialise statements that should be present\, but are not (such as inverses of “spouse” statements)\;\n- find inconsistencies in the data (e.g.\, statements missing mandatory qualifiers)\; and to\n- display statements that logically follow from the data\, but do not need to be materialised (e.g.\, “relative” statements obtained from following “father”/“mother”-paths).\n\nRules of the latter type contribute to a better browsing experience by\nmaking explicit data that could only be obtained by combining different\nstatements (not necessarily belonging to the same item)\, whereas rules\nof the former types help to improve the quality of the data itself.\n\nWe introduce the basic usage of SQID and demonstrate applications for\nrules in the use cases above.
DTSTAMP:20181018T014215
SEQUENCE:26747
END:VEVENT
BEGIN:VEVENT
SUMMARY:Verification of Golog Programs over Description Logic Actions
URL://iccl.inf.tu-dresden.de/web/Verification_of_Golog_Programs_over_Description_Logic_Actions
UID://iccl.inf.tu-dresden.de/web/Verification_of_Golog_Programs_over_Description_Logic_Actions
DTSTART:20171102T091500
DTEND:20171102T101500
LOCATION:APB 3027
DESCRIPTION:Golog is a powerful programming language for logic-based agents. The primitives of the language are actions whose preconditions and effects are defined in a Situation Calculus action theory using first-order logic. To describe possible courses of actions the programmer can freely combine imperative control structures with constructs for non-deterministic choice\, leaving it to the system to resolve the non-determinism in a suitable manner. Golog has been successfully used for high-level decision making in the area of cognitive robotics. Obviously\, it is important to verify certain properties of a Golog program before executing it on a physical robot. However\, due to the high expressiveness of the language the verification problem is in general undecidable. In this thesis\, we study the verification problem for Golog programs over actions defined in action languages based on Description Logics and explore the boundary between decidable and undecidable fragments.
DTSTAMP:20181018T014357
SEQUENCE:26748
END:VEVENT
BEGIN:VEVENT
SUMMARY:Context Reasoning for Role-Based Models
URL://iccl.inf.tu-dresden.de/web/Context_Reasoning_for_Role-Based_Models
UID://iccl.inf.tu-dresden.de/web/Context_Reasoning_for_Role-Based_Models
DTSTART:20171027T091500
DTEND:20171027T101500
LOCATION:APB 1004
DESCRIPTION:Nowadays\, we are literally everywhere surrounded by software systems. These should cope with very complex scenarios including the ability of context-awareness and self-adaptability. The concept of roles provide the means to model such complex\, context-dependent systems. In role-based systems\, the relational and context-dependent properties of objects are transferred into the roles that the object plays in a certain context. However\, even if the domain can be expressed in a well-structured and modular way\, role-based models can still be hard to comprehend due to the sophisticated semantics of roles\, contexts and different constraints. Hence\, unintended implications or inconsistencies may be overlooked. A feasible logical formalism is required here. In this setting Description Logics (DLs) fit very well as a starting point for further considerations since as a decidable fragment of first-order logic they have both an underlying formal semantics and decidable reasoning problems. DLs are a well-understood family of knowledge representation formalisms which allow to represent application domains in a well-structured way by DL-concepts\, i.e. unary predicates\, and DL-roles\, i.e. binary predicates. However\, classical DLs lack expressive power to formalise contextual knowledge which is crucial for formalising role-based systems. We investigate a novel family of contextualised description logics that is capable of expressing contextual knowledge and preserves decidability even in the presence of rigid DL-roles\, i.e. relational structures that are context-independent. For these contextualised description logics we thoroughly analyse the complexity of the consistency problem. Furthermore\, we present a mapping algorithm that allows for an automated translation from a formal role-based model\, namely a Compartment Role Object Model (CROM)\, into a contextualised DL ontology. We prove the semantical correctness and provide ideas how features extending CROM can be expressed in our contextualised DLs. As final step for a completely automated analysis of role-based models\, we investigate a practical reasoning algorithm and implement the first reasoner that can process contextual ontologies.
DTSTAMP:20181018T014414
SEQUENCE:26749
END:VEVENT
BEGIN:VEVENT
SUMMARY:Attributed Description Logics: Ontologies for Knowledge Graphs
URL://iccl.inf.tu-dresden.de/web/Attributed_Description_Logics:_Ontologies_for_Knowledge_Graphs
UID://iccl.inf.tu-dresden.de/web/Attributed_Description_Logics:_Ontologies_for_Knowledge_Graphs
DTSTART:20171019T092000
DTEND:20171019T105000
LOCATION:APB 2026
DESCRIPTION:In modelling real-world knowledge\, there often arises a need to represent and reason with meta-knowledge. To equip description logics (DLs) for dealing with such ontologies\, we enrich DL concepts and roles with finite sets of attribute-value pairs\, called annotations\, and allow concept inclusions to express constraints on annotations. We show that this may lead to increased complexity or even undecidability\, and we identify cases where this increased expressivity can be achieved without incurring increased complexity of reasoning. In particular\, we describe a tractable fragment based on the lightweight description logic EL\, and we cover SROIQ\, the DL underlying OWL 2 DL.
DTSTAMP:20181018T014426
SEQUENCE:26750
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tractable Query Answering for Expressive Ontologies and Existential Rules
URL://iccl.inf.tu-dresden.de/web/Tractable_Query_Answering_for_Expressive_Ontologies_and_Existential_Rules
UID://iccl.inf.tu-dresden.de/web/Tractable_Query_Answering_for_Expressive_Ontologies_and_Existential_Rules
DTSTART:20171012T092000
DTEND:20171012T105000
LOCATION:APB 2026
DESCRIPTION:The disjunctive skolem chase is a sound and complete (albeit non-terminating) algorithm that can be used to solve conjunctive query answering over DL ontologies and programs with disjunctive existential rules.\nEven though acyclicity notions can be used to ensure chase termination for a large subset of real-world knowledge bases\, the complexity of reasoning over acyclic theories still remains high.\nHence\, we study several restrictions which not only guarantee chase termination but also ensure polynomiality.\nWe include an evaluation that shows that almost all acyclic DL ontologies do indeed satisfy these general restrictions.
DTSTAMP:20181018T014443
SEQUENCE:26751
END:VEVENT
BEGIN:VEVENT
SUMMARY:ICCL Summer School 'Bridging the Gap between Human and Automated Reasoning'\, September 18-29\, 2017\, Dresden
URL://iccl.inf.tu-dresden.de/web/ICCL_Summer_School_%27Bridging_the_Gap_between_Human_and_Automated_Reasoning%27,_September_18-29,_2017,_Dresden
UID://iccl.inf.tu-dresden.de/web/ICCL_Summer_School_%27Bridging_the_Gap_between_Human_and_Automated_Reasoning%27,_September_18-29,_2017,_Dresden
DTSTART:20170918T090000
DTEND:20170929T170000
DESCRIPTION:In September 2017 we organize a summer school at TU Dresden\, Germany.\n\nThe topic of this year's summer school is ''Bridging the Gap between Human and Automated Reasoning''.\n\nAs in the past summer schools at TU Dresden in 2002\, 2003\, 2004\, 2005\, 2006\, 2007\, 2008\, 2010\, 2013 and 2015 people from distinct\, but communicating communities will gather in an informal and friendly atmosphere. This two-week event is aimed at graduate students\, researchers and practitioners.
DTSTAMP:20170307T141608
SEQUENCE:22885
END:VEVENT
BEGIN:VEVENT
SUMMARY:Monotone Monadic SNP 2: Proof of the Universal-algebraic Dichotomy Conjecture
URL://iccl.inf.tu-dresden.de/web/Monotone_Monadic_SNP_2:_Proof_of_the_Universal-algebraic_Dichotomy_Conjecture
UID://iccl.inf.tu-dresden.de/web/Monotone_Monadic_SNP_2:_Proof_of_the_Universal-algebraic_Dichotomy_Conjecture
DTSTART:20170901T134500
DTEND:20170901T141500
LOCATION:WIL C115
DESCRIPTION:The forbidden patterns problem of the set of vertex-coloured graphs {H1\,…\,Hk} is the decision problem of the form: given a finite graph G as input\, is it possible to colour the vertices of G in a way that none of H1\, …\, Hk homomorphically maps to the resulting coloured graph. The logic MMSNP can be seen as a complexity class whose problems are forbidden patterns problems of finite sets of coloured relational structures. It was conjectured by Feder and Vardi that this complexity class exhibits a complexity dichotomy (i.e.\, that every forbidden patterns problem is in P or NP-complete). Feder and Vardi showed that every problem in MMSNP reduces in probabilistic polynomial-time to the CSP of a structure with finite domain\, and Kun later derandomized this reduction. Thus\, MMSNP and finite-domain CSPs are computationally equivalent.\n\n\nFollowing up on Manuel's talk\, I will present a completely new reduction from MMSNP to finite-domain CSPs that uses recent techniques and results from universal algebra\, model theory\, and Ramsey theory. This proves a stronger form of the Feder-Vardi-Kun result\, and shows in particular that the Bodirsky-Pinsker tractability conjecture holds for all CSPs in MMSNP.
DTSTAMP:20170825T071641
SEQUENCE:23946
END:VEVENT
BEGIN:VEVENT
SUMMARY:Monotone Monadic SNP 1: Classical Results and Applications
URL://iccl.inf.tu-dresden.de/web/Monotone_Monadic_SNP_1:_Classical_Results_and_Applications
UID://iccl.inf.tu-dresden.de/web/Monotone_Monadic_SNP_1:_Classical_Results_and_Applications
DTSTART:20170901T131500
DTEND:20170901T134500
LOCATION:WIL C115
DESCRIPTION:The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory\, database theory\, and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is polynomially equivalent to a finite-domain constraint satisfaction problem (CSP)\; the clever probabilistic reduction was derandomized by Kun using explicit constructions of expander structures. Several authors have recently announced proofs that every finite-domain CSP is either in P or NP-complete\; hence\, the same is true for MMSNP.\n\n\nWe present a new proof of the complexity dichotomy for MMSNP. Our new proof has the advantage that it confirms a tractability conjecture by Pinsker and myself that we have made for a much larger class of computational problems. Another advantage is that it does not rely on the intricate expander constructions of Kun (but we do use the finite \ndomain CSP dichotomy). Our approach is based on the fact that every MMSNP sentence can be effectively rewritten into a finite union of CSPs for countably infinite omega-categorical structures\; moreover\, by a recent result of Hubička and Nešetřil\, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.\n\nIn this first part of the talk we will give an introduction to MMSNP with many examples and the classical results\, including the Feder-Vardi reduction to finite-domain CSPs\, but also usages of MMSNP to classify the complexity of problems that arose in the context of descriptions logics (by Bienvenu\, ten Cate\, Lutz\, Wolter). In the second part\, Antoine presents our new analysis of MMSNP sentences using the universal-algebraic approach and Ramsey theory.
DTSTAMP:20170825T070724
SEQUENCE:23944
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantum Computing and the Limits of the Efficiently Computable
URL://iccl.inf.tu-dresden.de/web/Quantum_Computing_and_the_Limits_of_the_Efficiently_Computable
UID://iccl.inf.tu-dresden.de/web/Quantum_Computing_and_the_Limits_of_the_Efficiently_Computable
DTSTART:20170828T140000
DTEND:20170828T150000
LOCATION:APB E023
DESCRIPTION:I'll offer a crash course on quantum computing\, which seeks to exploit the strange rules of quantum physics to solve certain problems dramatically faster than we know how to solve them with any existing computer. I promise no hype: just a a sober summary of how a quantum computer would actually work (hint: it's not just by "trying every possible answer in parallel")\, for which problems quantum computers are and aren't expected to provide an advantage\, and the current status of the effort to make quantum computing practical. I'll also say something about the ultimate physical limits of computation\, and about speculative proposals for going beyond even quantum computers.\n\n \n'''Bio'''\n\n[http://www.scottaaronson.com/ Scott Aaronson] is David J. Bruton Centennial Professor of Computer Science at the University of Texas at Austin. He received his bachelor's from Cornell University and his PhD from UC Berkeley\, and did postdoctoral fellowships at the Institute for Advanced Study as well as the University of Waterloo. Before coming to UT Austin\, he spent nine years as a professor in Electrical Engineering and Computer Science at MIT. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book\, Quantum Computing Since Democritus\, was published in 2013 by Cambridge University Press. He’s received the National Science Foundation’s Alan T. Waterman Award\, the United States PECASE Award\, the Vannevar Bush Fellowship\, and MIT's Junior Bose Award for Excellence in Teaching.
DTSTAMP:20170711T080609
SEQUENCE:23758
END:VEVENT
BEGIN:VEVENT
SUMMARY:Logical Foundations of Linked Data Anonymisation
URL://iccl.inf.tu-dresden.de/web/Logical_Foundations_of_Linked_Data_Anonymisation
UID://iccl.inf.tu-dresden.de/web/Logical_Foundations_of_Linked_Data_Anonymisation
DTSTART:20170814T140000
DTEND:20170814T150000
LOCATION:APB 1004
DESCRIPTION:The widespread adoption of the Linked Data paradigm has been driven by the increasing demand for information exchange between organisations\, as well as by regulations in domains such as health care and governance that require certain data to be published. In this setting\, sensitive information is at high risk of disclosure since published data can be often seamlessly linked with arbitrary external data sources.\n\n\nIn this talk I will discuss the logical foundations of privacy-preserving data publishing (PPDP) in the context of Linked Data. Specifically\, we consider anonymisations of RDF graphs (and\, more generally\, relational datasets with labelled nulls) and define notions of safe and optimal anonymisations. Safety ensures that an anonymised dataset can be published with provable protection guarantees against linking attacks\, whereas optimality ensures that the published data preserves as much information from the original data as possible\, while still satisfying the safety requirement. I will establish the computational complexity of the underpinning decision problems both under the open-world semantics inherent to RDF and a closed-world semantics\, where we assume that an attacker has complete knowledge over some part of the original data.
DTSTAMP:20181018T014617
SEQUENCE:26752
END:VEVENT
BEGIN:VEVENT
SUMMARY:Advances in Abstract Argumentation - Expressiveness and Dynamics
URL://iccl.inf.tu-dresden.de/web/Advances_in_Abstract_Argumentation_-_Expressiveness_and_Dynamics
UID://iccl.inf.tu-dresden.de/web/Advances_in_Abstract_Argumentation_-_Expressiveness_and_Dynamics
DTSTART:20170727T130000
DTEND:20170727T140000
LOCATION:APB 3027
DESCRIPTION:In recent years the research field of argumentation has become a major\ntopic in the study of artificial intelligence (AI). Within the\nargumentation process\, the focus of this work is on the evaluation of\nthe acceptability of conflicting arguments using the formal models of\nabstract argumentation frameworks (AFs) and abstract dialectical\nframeworks (ADFs). While an AF is a directed graph where nodes\nrepresent arguments and directed edges represent conflicts between\narguments\, ADFs constitute a very powerful generalization of AFs by\nadditionally assigning to each argument an acceptance condition. In\nthis work we contribute to the advancement of the study of abstract\nargumentation by addressing aspects of expressiveness and dynamics of\nargumentation semantics. In terms of expressiveness we complement\nrecent work on realizability in AFs\, investigate the role of rejected\narguments\, and study the induced class of compact argumentation\nframeworks. Then\, we lift the study of expressiveness to the concept\nof input-output AFs. Finally\, we present a unifying algorithmic\napproach to realizability capturing AFs and ADFs as well as\nintermediate formalisms in a modular way\, which is also implemented in\nASP. Taking into account the dynamic nature of argumentation\, we\nstudy two central issues therein: revision and splitting. For\nrevision we apply the seminal AGM theory of belief change to\nargumentation by presenting representation theorems for revision\noperators which guarantee to result in a single framework. We also\npresent concrete belief change operators and analyze their\ncomputational complexity. Finally\, we study splitting of ADFs\, aiming\nfor optimization of computation by incremental computation of\nsemantics.
DTSTAMP:20181018T014701
SEQUENCE:26753
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Identity Problem in Description Logic Ontologies
URL://iccl.inf.tu-dresden.de/web/The_Identity_Problem_in_Description_Logic_Ontologies
UID://iccl.inf.tu-dresden.de/web/The_Identity_Problem_in_Description_Logic_Ontologies
DTSTART:20170713T130000
DTEND:20170713T140000
LOCATION:APB 3027
DESCRIPTION:The work in this paper is motivated by a privacy scenario in which the identity of certain persons (represented as anonymous individuals) should be hidden. We assume that factual information about known individuals (i.e.\, individuals whose identity is known) and anonymous individuals is stored in an ABox and general background information is expressed in a TBox\, where both the TBox and the ABox are publicly accessible. The identity problem then asks whether one can deduce from the TBox and the ABox that a given anonymous individual is equal to a known one. Since this would reveal the identity of the anonymous individual\, such a situation needs to be avoided. We first observe that not all Description Logics (DLs) are able to derive any such equalities between individuals\, and thus the identity problem is trivial in these DLs. We then consider DLs with nominals\, number restrictions\, or function dependencies\, in which the identity problem is non-trivial. We show that in these DLs the identity problem has the same complexity as the instance problem. Finally\, we consider an extended scenario in which users with different rôles can access different parts of the TBox and ABox\, and we want to check whether\, by a sequence of rôle changes and queries asked in each rôle\, one can deduce the identity of an anonymous individual.
DTSTAMP:20181018T014717
SEQUENCE:26754
END:VEVENT
BEGIN:VEVENT
SUMMARY:Using Ontologies to Query Probabilistic Numerical Data
URL://iccl.inf.tu-dresden.de/web/Using_Ontologies_to_Query_Probabilistic_Numerical_Data
UID://iccl.inf.tu-dresden.de/web/Using_Ontologies_to_Query_Probabilistic_Numerical_Data
DTSTART:20170706T133000
DTEND:20170706T140000
LOCATION:APB 3027
DESCRIPTION:We consider ontology-based query answering in a setting where some of the data are numerical and of a probabilistic nature\, such as data obtained from uncertain sensor readings. The uncertainty for such numerical values can be more precisely represented by continuous probability distributions than by discrete probabilities for numerical facts concerning exact values. For this reason\, we extend existing approaches using discrete probability distributions over facts by continuous probability distributions over numerical values. We determine the exact (data and combined) complexity of query answering in extensions of the well-known description logics EL and ALC with numerical comparison operators in this probabilistic setting.
DTSTAMP:20170704T160113
SEQUENCE:23733
END:VEVENT
BEGIN:VEVENT
SUMMARY:Metric Temporal Description Logics with Interval-Rigid Names
URL://iccl.inf.tu-dresden.de/web/Metric_Temporal_Description_Logics_with_Interval-Rigid_Names
UID://iccl.inf.tu-dresden.de/web/Metric_Temporal_Description_Logics_with_Interval-Rigid_Names
DTSTART:20170706T130000
DTEND:20170706T133000
LOCATION:APB 3027
DESCRIPTION:In contrast to qualitative linear temporal logics\, which can be used to state that some property will eventually be satisfied\, metric temporal logics allow to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining Description Logics (DLs) with temporal logics has concentrated on qualitative temporal logics\, there has recently been a growing interest in extending this work to the quantitative case. In this paper\, we complement existing results on the combination of DLs with metric temporal logics over the natural numbers by introducing interval-rigid names. This allows to state that elements in the extension of certain names stay in this extension for at least some specified amount of time.
DTSTAMP:20181018T014733
SEQUENCE:26755
END:VEVENT
BEGIN:VEVENT
SUMMARY:Not too Big\, Not too Small ... Complexities of Fixed-Domain Reasoning in First-Order and Description Logics
URL://iccl.inf.tu-dresden.de/web/Not_too_Big,_Not_too_Small_..._Complexities_of_Fixed-Domain_Reasoning_in_First-Order_and_Description_Logics
UID://iccl.inf.tu-dresden.de/web/Not_too_Big,_Not_too_Small_..._Complexities_of_Fixed-Domain_Reasoning_in_First-Order_and_Description_Logics
DTSTART:20170629T130000
DTEND:20170629T140000
LOCATION:APB 3027
DESCRIPTION:We consider reasoning problems in description logics and variants of first-order logic under the fixed-domain semantics\, where the model size is finite and explicitly given. It follows from previous results that standard reasoning is NP-complete for a very wide range of logics\, if the domain size is given in unary encoding. In this paper\, we complete the complexity overview for unary encoding and investigate the effects of binary encoding with partially surprising results. Most notably\, fixed-domain standard reasoning becomes NExpTime for the rather low-level description logics ELI and ELF (as opposed to ExpTime when no domain size is given). On the other hand\, fixed-domain reasoning remains NExpTime even for first-order logic\, which is undecidable under the unconstrained semantics. For less expressive logics\, we establish a generic criterion ensuring NP-completeness of fixed-domain reasoning. Amongst other logics\, this criterion captures all the tractable profiles of OWL 2.
DTSTAMP:20181018T014749
SEQUENCE:26756
END:VEVENT
END:VCALENDAR