BEGIN:VCALENDAR
PRODID:-//SMW Project//Semantic Result Formats
VERSION:2.0
METHOD:PUBLISH
X-WR-CALNAME:ICCL-Veranstaltungen
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:20180803T123339
SEQUENCE:26242
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\nModal 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.
DTSTAMP:20180805T164014
SEQUENCE:26244
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:20180723T135840
SEQUENCE:26162
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\nAbout the speaker: 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:20180629T121603
SEQUENCE:26046
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\nBio: 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:20180517T105551
SEQUENCE:25826
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:20180531T155408
SEQUENCE:25886
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:20180525T145003
SEQUENCE:25846
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:20180418T104052
SEQUENCE:25662
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:20180420T061945
SEQUENCE:25677
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:20180405T133414
SEQUENCE:25513
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:20180329T175939
SEQUENCE:25449
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:20180327T105439
SEQUENCE:25430
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:20180302T083731
SEQUENCE:25196
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:20180228T100148
SEQUENCE:25186
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:20180219T122634
SEQUENCE:25147
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:20180205T220906
SEQUENCE:25070
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:20171128T091435
SEQUENCE:24652
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:20171115T101048
SEQUENCE:24546
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:20171107T164828
SEQUENCE:24489
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:20171019T083203
SEQUENCE:24328
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:20171019T083033
SEQUENCE:24326
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:20171016T121508
SEQUENCE:24281
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:20171009T120712
SEQUENCE:24203
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:20170804T073311
SEQUENCE:23911
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:20170724T074354
SEQUENCE:23830
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:20170713T100839
SEQUENCE:23778
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:20170704T155937
SEQUENCE:23731
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:20170627T145516
SEQUENCE:23702
END:VEVENT
BEGIN:VEVENT
SUMMARY:Query Rewriting for DL-Lite with n-ary Concrete Domains
URL://iccl.inf.tu-dresden.de/web/Query_Rewriting_for_DL-Lite_with_n-ary_Concrete_Domains
UID://iccl.inf.tu-dresden.de/web/Query_Rewriting_for_DL-Lite_with_n-ary_Concrete_Domains
DTSTART:20170622T130000
DTEND:20170622T140000
LOCATION:APB 3027
DESCRIPTION:We investigate ontology-based query answering (OBQA) in a setting where both the ontology and the query can refer to concrete values such as numbers and strings. In contrast to previous work on this topic\, the built-in predicates used to compare values are not restricted to being unary. We introduce restrictions on these predicates and on the ontology language that allow us to reduce OBQA to query answering in databases using the so-called combined rewriting approach. Though at first sight our restrictions are different from the ones used in previous work\, we show that our results strictly subsume some of the existing first-order rewritability results for unary predicates.
DTSTAMP:20170620T074005
SEQUENCE:23651
END:VEVENT
BEGIN:VEVENT
SUMMARY:Most Probable Explanations for Probabilistic Database Queries
URL://iccl.inf.tu-dresden.de/web/Most_Probable_Explanations_for_Probabilistic_Database_Queries
UID://iccl.inf.tu-dresden.de/web/Most_Probable_Explanations_for_Probabilistic_Database_Queries
DTSTART:20170601T130000
DTEND:20170601T140000
LOCATION:APB 3027
DESCRIPTION:Forming the foundations of large-scale knowledge bases\, probabilistic databases have been widely studied in the literature. In particular\, probabilistic query evaluation has been investigated intensively as a central inference mechanism. However\, despite its power\, query evaluation alone cannot extract all the relevant information encompassed in large-scale knowledge bases. To exploit this potential\, we study two inference tasks\; namely finding the most probable database and the most probable hypothesis for a given query. As natural counterparts of most probable explanations (MPE) and maximum a posteriori hypotheses (MAP) in probabilistic graphical models\, they can be used in a variety of applications that involve prediction or diagnosis tasks. We investigate these problems relative to a variety of query languages\, ranging from conjunctive queries to ontology-mediated queries\, and provide a detailed complexity analysis.
DTSTAMP:20170529T150457
SEQUENCE:23542
END:VEVENT
BEGIN:VEVENT
SUMMARY:Question Answering over Real-World Knowledge Graphs
URL://iccl.inf.tu-dresden.de/web/Question_Answering_over_Real-World_Knowledge_Graphs
UID://iccl.inf.tu-dresden.de/web/Question_Answering_over_Real-World_Knowledge_Graphs
DTSTART:20170518T130000
DTEND:20170518T140000
LOCATION:APB 3027
DESCRIPTION:With more and more data created and stored in databases there is a need for more user-friendly interfaces to query this data. Question Answering Systems\, also called Natural Language Interfaces\, are one of the approaches that try to provide such interfaces. Instead of typing a query in a formal query language the user asks the question in natural language.\n\nWe present a novel formalism for semantic composition called Phrase Representation Structures and based on this formalism we propose an architecture and a prototypical implementation for interactive Question Answering Systems. We address one of the main issues of such systems: the manual creation of a Lexicon for large knowledge bases. To create the Lexicon we use the lexical information contained in the knowledge base. Additionally\, we provide an user interface such that users can complete the lexical information.\n\nOur findings indicate that our proposed architecture could be used as a foundation for Question Answering Systems focused on professional users. Finally\, we discuss promising directions for future research to improve the quality and the user-friendliness of such systems.
DTSTAMP:20170406T124422
SEQUENCE:23092
END:VEVENT
BEGIN:VEVENT
SUMMARY:Revisiting Circumscription
URL://iccl.inf.tu-dresden.de/web/Revisiting_Circumscription
UID://iccl.inf.tu-dresden.de/web/Revisiting_Circumscription
DTSTART:20170511T130000
DTEND:20170511T140000
LOCATION:APB 3027
DESCRIPTION:Circumscription is one of the classic formalisms for introducing non-monotonicity in a logic. In this talk\, we show that the current version of circumscription in certain cases does not allow to draw conclusions that would be expected intuitively. We analyze the cases in which that happens and introduce a novel definition of circumscription that subsumes the original circumscription\, and behaves as intuitively expected. We show that the new formulation has useful properties\, in particular that it reduces to standard first-order logic in certain setups.
DTSTAMP:20170508T125631
SEQUENCE:23359
END:VEVENT
BEGIN:VEVENT
SUMMARY:Logic on MARS: Ontologies for Generalised Property Graphs
URL://iccl.inf.tu-dresden.de/web/Logic_on_MARS:_Ontologies_for_Generalised_Property_Graphs
UID://iccl.inf.tu-dresden.de/web/Logic_on_MARS:_Ontologies_for_Generalised_Property_Graphs
DTSTART:20170504T130000
DTEND:20170504T140000
LOCATION:APB 3027
DESCRIPTION:Graph-structured data is used to represent large information collections\, called knowledge graphs\, in many applications. Their exact format may vary\, but they often share the concept that edges can be annotated with additional information\, such as validity time or provenance information. Property Graph is a popular graph database format that also provides this feature. We give a formalization of a\ngeneralised notion of Property Graphs\, called multi-attributed relational structures (MARS)\, and introduce a matching knowledge representation formalism\, multi-attributed predicate logic (MAPL). We analyze the expressive power of MAPL and suggest a simpler\, rule-based fragment of MAPL that can be used for ontological reasoning on Property Graphs. To the best of our knowledge\, this is the first approach to making Property Graphs and related data structures accessible to symbolic AI.
DTSTAMP:20170502T114206
SEQUENCE:23314
END:VEVENT
BEGIN:VEVENT
SUMMARY:Restricted Chase (Non)Termination for Existential Rules with Disjunctions
URL://iccl.inf.tu-dresden.de/web/Restricted_Chase_(Non)Termination_for_Existential_Rules_with_Disjunctions
UID://iccl.inf.tu-dresden.de/web/Restricted_Chase_(Non)Termination_for_Existential_Rules_with_Disjunctions
DTSTART:20170427T130000
DTEND:20170427T140000
LOCATION:APB 3027
DESCRIPTION:The restricted chase is a sound and complete algorithm for conjunctive query answering over ontologies of disjunctive existential rules. We develop acyclicity conditions to ensure its termination. Our criteria cannot always detect termination (the problem is undecidable)\, and we develop the first cyclicity criteria to show non-termination of the restricted chase. Experiments on real-world ontologies show that our acyclicity notions improve significantly over known criteria and that most remaining ontologies are indeed cyclic.
DTSTAMP:20170424T075409
SEQUENCE:23191
END:VEVENT
BEGIN:VEVENT
SUMMARY:Selected Advances in Data Semantics
URL://iccl.inf.tu-dresden.de/web/Selected_Advances_in_Data_Semantics
UID://iccl.inf.tu-dresden.de/web/Selected_Advances_in_Data_Semantics
DTSTART:20170418T140000
DTEND:20170418T150000
LOCATION:APB 3105
DESCRIPTION:We present some recent advances in ontology engineering and its applications. This includes two Protege plug-ins and an extension to the OWL API which simplify the dealing with logical axioms in ontology modeling: The ROWLTab allows the user to enter OWL axioms in the form or rules\; a formal evaluation which we conducted shows that this form of OWL modeling is quicker and less error-prone than the standard Protege interface. The OWLAX plug-in provides a diagram-based approach to the modeling of most common logical axioms. The OWL API LaTeX renderer provides transcriptions into description logic syntax. We will also present first results of some ongoing work on explaining trained neural networks by means of semantic background knowledge.
DTSTAMP:20170418T103427
SEQUENCE:23153
END:VEVENT
BEGIN:VEVENT
SUMMARY:Suche struktureller Ähnlichkeiten in großen Graphen
URL://iccl.inf.tu-dresden.de/web/Searching_for_Structural_Similarities_in_Large_Graphs
UID://iccl.inf.tu-dresden.de/web/Searching_for_Structural_Similarities_in_Large_Graphs
DTSTART:20170413T130000
DTEND:20170413T140000
LOCATION:APB 3027
DESCRIPTION:Structural Similarity\, ein Maß\, welches die Ähnlichkeit von Knoten anhand struktureller Eigenschaften im Graphen misst\, findet Anwendung in vielen Gebieten der Informatik. Bisherige Algorithmen zur Bestimmung von Structural Similarity sind für große Graphen nicht geeignet\, oder beschränken sich darauf die direkte Nachbarschaft der Knoten zu observieren. Daher möchte ich ein alternatives Scoring-Verfahren vorstellen mit dem sich Structural Similarity auch für große Graphen in geeigneter Weise quantifizieren lässt.
DTSTAMP:20170411T191009
SEQUENCE:23131
END:VEVENT
BEGIN:VEVENT
SUMMARY:Decomposition of regular languages
URL://iccl.inf.tu-dresden.de/web/Decomposation_of_regular_languages
UID://iccl.inf.tu-dresden.de/web/Decomposation_of_regular_languages
DTSTART:20170316T110000
DTEND:20170316T120000
LOCATION:APB 3027
DESCRIPTION:I will discuss a problem how to decompose a regular language with respect to a set of alphabets and will show how to overcome undecidability by using a small trick\, which leads to polynomial complexity.
DTSTAMP:20170313T143948
SEQUENCE:22914
END:VEVENT
BEGIN:VEVENT
SUMMARY:Automata\, Logic\, Algebra... What do they have in common?
URL://iccl.inf.tu-dresden.de/web/Automata,_Logic,_Algebra..._What_do_they_have_in_common%3F
UID://iccl.inf.tu-dresden.de/web/Automata,_Logic,_Algebra..._What_do_they_have_in_common%3F
DTSTART:20170302T110000
DTEND:20170302T120000
LOCATION:APB 3027
DESCRIPTION:In this talk\, a few language classes will be discussed including their automata\, logical\, and algebraic characterizations.
DTSTAMP:20170228T115232
SEQUENCE:22787
END:VEVENT
BEGIN:VEVENT
SUMMARY:Solving Angry Birds with Reinforcement Learning
URL://iccl.inf.tu-dresden.de/web/Solving_Angry_Birds_with_Reinforcement_Learning
UID://iccl.inf.tu-dresden.de/web/Solving_Angry_Birds_with_Reinforcement_Learning
DTSTART:20170223T110000
DTEND:20170223T120000
LOCATION:APB 3027
DESCRIPTION:Reinforcement Learning is an area of machine learning tackling the problem\, which action an agent should take to get a maximum reward. After explaining the model-free reinforcement learning technique Q-learning the result of implementing it for solving the popular puzzle video game Angry Birds is being presented.
DTSTAMP:20170220T094707
SEQUENCE:22730
END:VEVENT
END:VCALENDAR