International Center for Computational Logic - Benutzerbeiträge [de]

Inproceedings3022/en

2015-05-15T09:06:17Z

Michael Thomazo: Page created automatically by parser function on page Inproceedings3022

#REDIRECT [[Inproceedings3022]]

Inproceedings3022

2015-05-15T09:06:16Z

Michael Thomazo: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Tomáš |ErsterAutorNachname=Masopust |FurtherAuthors=Michaël Thomazo; }} {{Inproceedings |Referiert=1 |Title=…“

{{Publikation Erster Autor
|ErsterAutorVorname=Tomáš
|ErsterAutorNachname=Masopust
|FurtherAuthors=Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=On the Complexity of k-Piecewise Testability and the Depth of Automata
|To appear=1
|Year=2015
|Booktitle=Proc. 19th International Conference on Developments in Language Theory (DLT'15)
}}
{{Publikation Details
|Abstract=For a non-negative integer k, a language is k-piecewise testable (k-PT) if it is a finite boolean combination of languages of the form
\Sigma^*a1\Sigma^*...\Sigma^*an for ai in \Sigma and 0 <= n <= k. We study the following problem: Given a DFA recognizing a piecewise testable language, decide whether the language is k-PT. We provide a complexity bound on this problem and a detailed analysis for small k's. The result can be use to find the minimal k for which the language is k-PT. We show that the upper bound on k given by the depth of the minimal DFA can be exponentially bigger than the minimal possible k, and provide a tight upper bound on the depth of the minimal DFA recognizing a k-PT language.
|Download=Dlt2015 camera ready 3.pdf
|Forschungsgruppe=Knowledge Systems
}}

Datei:Dlt2015 camera ready 3.pdf

2015-05-15T09:03:52Z

Michael Thomazo:

News16

2015-05-15T08:59:00Z

Michael Thomazo:

{{Neuigkeit
|Titel DE=ICCL mit gleich sieben Papieren bei IJCAI vertreten
|Titel EN=ICCL Researchers Score Seven Papers at IJCAI 2015
|Beschreibung DE=Die ''International Joint Conference on Artificial Intelligence'' (IJCAI) ist die weltweit wichtigste Konferenz im Bereich Künstliche Intelligenz, bei der sich aller zwei Jahre weltweit führende Forscher und Forscherinnen dieses Fachs treffen. In diesem Jahr findet IJCAI in Buenos Aires statt und konnte mit 1.996 Einreichungen einen neuen Rekord verbuchen, wobei 575 Papiere akzeptiert worden sind (28,8%). Es ist daher besonders erfreulich, dass Forschern und Forscherinnen des [[International Center for Computational Logic]] gleich mit sieben ihrer Forschungspapiere Erfolg hatten.

Die akzeptierten Papiere sind:
* [[Stefan Borgwardt]], Marco Cerami, [[Rafael Peñaloza]]: [[Inproceedings3017|The Complexity of Subsumption in Fuzzy EL]]
* [[Stefan Borgwardt]], [[Veronika Thost]]: [[Inproceedings3016|Temporal Query Answering in the Description Logic EL]]
* Pierre Bourhis, [[Markus Krötzsch]], [[Sebastian Rudolph]]: [[Inproceedings3015|Reasonable Highly Expressive Query Languages]]
* [[Sarah Gaggl]], [[Sebastian Rudolph]], Hannes Strass: [[Inproceedings3019|On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks]]
* [[Sebastian Rudolph]], Christian Sacarea, [[Diana Troanca]]: Membership Constraints in Formal Concept Analysis
* [[Sebastian Rudolph]], [[Michaël Thomazo]]: [[Inproceedings3018|Characterization of the Expressivity of Existential Rule Queries]]
* [[Benjamin Zarrieß]], Jens Claßen: Verification of Knowledge-Based Programs over Description Logic Actions

Wir gratulieren allen Autoren zu diesem bemerkenswerten Erfolg. Ab 2015 soll IJCAI übrigens jährlich stattfinden.
|Beschreibung EN=The ''International Joint Conference on Artificial Intelligence'' (IJCAI) is the most important conference in artificial intelligence, which brings together world-leading researchers in this field every other year (from 2016 on every year). IJCAI 2015 takes place in Buenos Aires and registered a record number of 1,996 submissions, of which 575 papers have been accepted (28.8%). It is therefore remarkable that [[ICCL/en|ICCL]] researchers have been successful with a total of seven accepted papers.

The accepted papers are:
* [[Stefan Borgwardt/en|Stefan Borgwardt]], Marco Cerami, [[Rafael Peñaloza/en|Rafael Peñaloza]]: [[Inproceedings3017|The Complexity of Subsumption in Fuzzy EL]]
* [[Stefan Borgwardt/en|Stefan Borgwardt]], [[Veronika Thost/en|Veronika Thost]]: [[Inproceedings3016|Temporal Query Answering in the Description Logic EL]]
* Pierre Bourhis, [[Markus Krötzsch/en|Markus Krötzsch]], [[Sebastian Rudolph/en|Sebastian Rudolph]]: [[Inproceedings3015|Reasonable Highly Expressive Query Languages]]
* [[Sarah Gaggl/en|Sarah Gaggl]], [[Sebastian Rudolph/en|Sebastian Rudolph]], Hannes Strass: [[Inproceedings3019|On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks]]
* [[Sebastian Rudolph/en|Sebastian Rudolph]], Christian Sacarea, [[Diana Troanca/en|Diana Troanca]]: Membership Constraints in Formal Concept Analysis
* [[Sebastian Rudolph/en|Sebastian Rudolph]], [[Michaël Thomazo/en|Michaël Thomazo]]: [[Inproceedings3018|Characterization of the Expressivity of Existential Rule Queries]]
* [[Benjamin Zarrieß/en|Benjamin Zarrieß]], Jens Claßen: Verification of Knowledge-Based Programs over Description Logic Actions

Congratulations to all authors for this remarkable success.
|URL=http://ijcai-15.org/
|Datum=2015/04/19
|Bild=Ijcai2015-logo.png
|Forschungsgruppe=Knowledge Systems
}}

Inproceedings3018/en

2015-04-30T17:19:36Z

Michael Thomazo: Page created automatically by parser function on page Inproceedings3018

#REDIRECT [[Inproceedings3018]]

Inproceedings3018

2015-04-30T17:19:36Z

Michael Thomazo: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Sebastian |ErsterAutorNachname=Rudolph |FurtherAuthors=Michaël Thomazo; }} {{Inproceedings |Referiert=1 |Title…“

{{Publikation Erster Autor
|ErsterAutorVorname=Sebastian
|ErsterAutorNachname=Rudolph
|FurtherAuthors=Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=Characterization of the Expressivity of Existential Rule Queries
|To appear=1
|Year=2015
|Booktitle=Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15)
|Publisher=AAAI Press
}}
{{Publikation Details
|Abstract=Existential rules (also known as Datalog+/- or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Los-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.
|Download=Ijcai-15-rt.pdf
|Forschungsgruppe=Computational Logic
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Ijcai-15-rt.pdf

2015-04-30T17:19:00Z

Michael Thomazo:

Techreport3019/en

2015-04-30T09:44:20Z

Michael Thomazo: Page created automatically by parser function on page Techreport3019

#REDIRECT [[Techreport3019]]

Techreport3019

2015-04-30T09:44:20Z

{{Publikation Erster Autor
|ErsterAutorVorname=Sebastian
|ErsterAutorNachname=Rudolph
|FurtherAuthors=Michaël Thomazo
}}
{{Techreport
|Title=Characterization of the Expressivity of Existential Rule Queries
|Year=2015
|Month=Mai
|Institution=TU Dresden
|Archivierungsnummer=IJCAI-15-RT-RR
}}
{{Publikation Details
|Abstract=Existential rules (also known as Datalog+/- or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Los-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.
|Download=Ijcai-15-rt-rr.pdf
|Forschungsgruppe=Computational Logic
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Ijcai-15-rt-rr.pdf

2015-04-30T09:39:01Z

Michael Thomazo:

Existenzielle Regeln

2014-11-06T13:15:59Z

Michael Thomazo:

{{Forschungsgebiet
|Name EN=Existential Rules
|Beschreibung DE=Existenzielle Regeln sind ein Formalismus zur Wissensrepräsentation mit Anwendungen in der künstlichen Intelligenz und Datenbanken.
|Beschreibung EN=Existential Rules are a knowledge representation formalism used in artificial intelligence and database theory. Their syntactic flexibility enables an easy integration of both semantic knowledge and databases. Syntactically close to Datalog rules, an important distinguishing feature is the possibility to describe individuals whose existence was not originally known, which is of great help for modeling purposes. All these features have motivated an intense research effort on how to query data under such rules. Questions typically tackled with this respect are the following: which query language achieve a good tradeoff between expressivity and complexity? What ensures the decidability of the query answering problem? What is the complexity of specific classes of rules? How to build efficient reasoners?
}}

Michaël Thomazo

2014-11-04T17:41:11Z

Michael Thomazo:

{{Mitarbeiter
|Vorname=Michaël
|Nachname=Thomazo
|Akademischer Titel=Dr.
|Forschungsgruppe=Computational Logic
|Stellung=Stipendiat
|Ehemaliger=0
|Telefon=+49 351 463 43560
|Fax=+49 351 463 32827
|Email=michael.thomazo@tu-dresden.de
|Raum=INF 2036
|Bild=thomazo.JPG
|Info=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013, and an Alexander von Humboldt Fellow since July 2014.
|Info EN=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013, and an Alexander von Humboldt Fellow since July 2014.
|DBLP=http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thomazo:Micha=euml=l
|Publikationen anzeigen=1
|Abschlussarbeiten anzeigen=0
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Thomazo.JPG

2014-11-04T17:40:48Z

Michael Thomazo:

Inproceedings4059

2014-10-28T15:38:27Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Compact Rewritings for Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
|Pages=1125-1131
}}
{{Publikation Details
|Abstract=Querying large databases while taking ontologies into account is currently a very active domain research. In this paper, we consider ontologies described by existential rules (also known as Datalog+/-), a framework that generalizes lightweight description logics. A common approach is to rewrite a conjunctive query w.r.t an ontology into a union of conjunctive queries (UCQ) which can be directly evaluated against a database. However, the practicability of this approach is questionable due to 1) the weak expressivity of classes for which efficient rewriters have been implemented 2) the large size of optimal rewritings using UCQ. We propose to use semi-conjunctive queries (SCQ), which are a restricted form of positive existential formulas, and compute sound and complete rewritings, which are union of SCQ (USCQ). A novel algorithm for query rewriting, Compact, is presented. It computes sound and complete rewritings for large classes of ontologies. First experiments show that USCQ are both efficiently computable and more efficiently evaluable than their equivalent UCQ.
|Link=http://ijcai.org/papers13/Papers/IJCAI13-170.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6826
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4059

2014-10-28T15:36:36Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Compact Rewritings for Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
|Pages=1125-1131
}}
{{Publikation Details
|Abstract=Querying large databases while taking ontologies into account is currently a very active domain research. In this paper, we consider ontologies described by existential rules (also known as Datalog+/-), a framework that generalizes lightweight description logics. A common approach is to rewrite a conjunctive query w.r.t an ontology into a union of conjunctive queries (UCQ) which can be directly evaluated against a database. However, the practicability of this approach is questionable due to 1) the weak expressivity of classes for which efficient rewriters have been implemented 2) the large size of optimal rewritings using UCQ. We propose to use semi-conjunctive queries (SCQ), which are a restricted form of positive existential formulas, and compute sound and complete rewritings, which are union of SCQ (USCQ). A novel algorithm for query rewriting, Compact, is presented. It computes sound and complete rewritings for large classes of ontologies. First experiments show that USCQ are both efficiently computable and more efficiently evaluable than their equivalent UCQ.
|Slides=Ijcai-13-t.pdf
|Link=http://ijcai.org/papers13/Papers/IJCAI13-170.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6826
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Ijcai-13-t.pdf

2014-10-28T15:36:31Z

Michael Thomazo:

Inproceedings4060

2014-10-28T15:36:04Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Ontology Based Query Answering with Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
|Pages=3245-3246
}}
{{Publikation Details
|Abstract=The aim of my Ph.D thesis is to identify expressive decidable classes, study the complexity of reasoning for these classes, and design efficient algorithms in the sense that they improve state of the art algorithms.
|Download=Ijcai-dc-13-t.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6784
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Ijcai-dc-13-t.pdf

2014-10-28T15:35:57Z

Michael Thomazo:

Inproceedings4059

2014-10-28T15:35:07Z

Michael Thomazo:

Inproceedings4059

2014-10-28T15:34:18Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Compact Rewritings for Existential Rules
|To appear=0
|Year=2013
|Booktitle=IJCAI
}}
{{Publikation Details
|Abstract=Querying large databases while taking ontologies into account is currently a very active domain research. In this paper, we consider ontologies described by existential rules (also known as Datalog+/-), a framework that generalizes lightweight description logics. A common approach is to rewrite a conjunctive query w.r.t an ontology into a union of conjunctive queries (UCQ) which can be directly evaluated against a database. However, the practicability of this approach is questionable due to 1) the weak expressivity of classes for which efficient rewriters have been implemented 2) the large size of optimal rewritings using UCQ. We propose to use semi-conjunctive queries (SCQ), which are a restricted form of positive existential formulas, and compute sound and complete rewritings, which are union of SCQ (USCQ). A novel algorithm for query rewriting, Compact, is presented. It computes sound and complete rewritings for large classes of ontologies. First experiments show that USCQ are both efficiently computable and more efficiently evaluable than their equivalent UCQ.
|Link=http://ijcai.org/papers13/Papers/IJCAI13-170.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6826
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4058

2014-10-28T14:04:12Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Mélanie
|ErsterAutorNachname=König
|FurtherAuthors=Michel Leclère;Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=Sound, Complete, and Minimal Query Rewriting for Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
|Pages=3017-3025
}}
{{Publikation Details
|Abstract=We address the issue of Ontology-Based Data Access which consists of exploiting the semantics expressed in ontologies while querying data. Ontologies are represented in the framework of existential rules, also known as Datalog+/-. We focus on the backward chaining paradigm, which involves rewriting the query (assumed to be a conjunctive query, CQ) into a set of CQs (seen as a union of CQs). The proposed algorithm accepts any set of existential rules as input and stops for so-called finite unification sets of rules (fus). The rewriting step relies on a graph notion, called a piece, which allows to identify subsets of atoms from the query that must be processed together. We first show that our rewriting method computes a minimal set of CQs when this set is finite, i.e., the set of rules is a fus. We then focus on optimizing the rewriting step. First experiments are reported in the associated technical report.
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6641
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4060

2014-10-28T14:03:49Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Ontology Based Query Answering with Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
}}
{{Publikation Details
|Abstract=The aim of my Ph.D thesis is to identify expressive decidable classes, study the complexity of reasoning for these classes, and design efficient algorithms in the sense that they improve state of the art algorithms.
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6784
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4060

2014-10-28T14:03:23Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Ontology Based Query Answering with Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
}}
{{Publikation Details
|Abstract=The aim of my Ph.D thesis is to identify expressive decidable classes, study the complexity of reasoning for these classes, and design efficient algorithms in the sense that they improve state of the art algorithms.
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6784
}}

Inproceedings4058

2014-10-28T14:02:19Z

Michael Thomazo:

Datei:Ijcai-13-klmt.pdf

2014-10-28T14:01:19Z

Michael Thomazo:

Techreport4008

2014-10-28T13:52:23Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Stepan
|ErsterAutorNachname=Holub
|FurtherAuthors=Tomáš Masopust; Michaël Thomazo;
}}
{{Techreport
|Title=Alternating Towers and Piecewise Testable Separators
|Year=2014
|Institution=Technischen Universität Dresden
|Referiert=0
}}
{{Publikation Details
|Abstract=Two languages are separable by a piecewise testable language if and only if there exists no infinite tower between them. An infinite tower is an infinite sequence of strings alternating between the two languages such that every string is a subsequence (scattered substring) of all the strings that follow. For regular languages represented by nondeterministic finite automata, the existence of an infinite tower is decidable in polynomial time. In this paper, we investigate the complexity of a particular method to compute a piecewise testable separator. We show that it is closely related to the height of maximal finite towers, and provide the upper and lower bounds with respect to the size of the given nondeterministic automata. Specifically, we show that the upper bound is polynomial with respect to the number of states with the cardinality of the alphabet in the exponent. Concerning the lower bound, we show that towers of exponential height with respect to the cardinality of the alphabet exist. Since these towers mostly turn out to be sequences of prefixes, we also provide a comparison with towers of prefixes.
|Download=Report-14-hmt.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://arxiv.org/abs/1409.3943
}}

Michaël Thomazo

2014-10-28T10:15:40Z

Michael Thomazo:

{{Mitarbeiter
|Vorname=Michaël
|Nachname=Thomazo
|Akademischer Titel=Dr.
|Forschungsgruppe=Computational Logic
|Stellung=Stipendiat
|Ehemaliger=0
|Telefon=+49 351 463 43560
|Fax=+49 351 463 32827
|Email=michael.thomazo@tu-dresden.de
|Raum=INF 2036
|Bild=thomazo-photo.jpg
|Info=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013, and an Alexander von Humboldt Fellow since July 2014.
|Info EN=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013, and an Alexander von Humboldt Fellow since July 2014.
|DBLP=http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thomazo:Micha=euml=l
|Publikationen anzeigen=1
|Abschlussarbeiten anzeigen=0
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Aktivitaet2005/en

2014-10-28T10:12:57Z

Michael Thomazo: Page created automatically by parser function on page Aktivitaet2005

#REDIRECT [[Aktivitaet2005]]

Aktivitaet2005

2014-10-28T10:12:57Z

Michael Thomazo: Die Seite wurde neu angelegt: „{{Aktivität |Beschreibung DE=Mitglied im Programmkomitee der 9th International Web Rule Symposium (RuleML 2015) |Beschreibung EN=Member in the program committ…“

{{Aktivität
|Beschreibung DE=Mitglied im Programmkomitee der 9th International Web Rule Symposium (RuleML 2015)
|Beschreibung EN=Member in the program committee of the 9th International Web Rule Symposium (RuleML 2015)
|Person=Michaël Thomazo
|URL=http://www.csw.inf.fu-berlin.de/ruleml2015/
|Start(Jahr)=2014
|Ende(Jahr)=2015
}}

Inproceedings4042

2014-10-28T10:09:07Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
|FurtherAuthors=Jean-François Baget; Marie-Laure Mugnier; Sebastian Rudolph
}}
{{Inproceedings
|Referiert=1
|Title=A Generic Querying Algorithm for Greedy Sets of Existential Rules
|To appear=0
|Year=2012
|Booktitle=Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning (KR'12)
|Publisher=AAAI
}}
{{Publikation Details
|Abstract=Answering queries in information systems that allow for ex- pressive inferencing is currently a field of intense research. This problem is often referred to as ontology-based data ac- cess (OBDA). We focus on conjunctive query entailment un- der logical rules known as tuple-generating dependencies, existential rules or Datalog+/-. One of the most expressive decidable classes of existential rules known today is that of greedy bounded treewidth sets (gbts). We propose an algo- rithm for this class, which is worst-case optimal for data and combined complexities, with or without bound on the pred- icate arity. A beneficial feature of this algorithm is that it allows for separation between offline and online processing steps: the knowledge base can be compiled independently from queries, which are evaluated against the compiled form. Moreover, very simple adaptations of the algorithm lead to worst-case-optimal complexities for specific subclasses of gbts which have lower complexities, such as guarded rules.
|Download=Kr-12-bmrt.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4542
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Kr-12-bmrt.pdf

2014-10-28T10:08:57Z

Michael Thomazo:

Inproceedings4029

2014-10-28T10:06:23Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
|FurtherAuthors=Sebastian Rudolph
}}
{{Inproceedings
|Referiert=1
|Title=Mixing Materialization and Query Rewriting for Existential Rules
|To appear=0
|Year=2014
|Booktitle=Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14)
|Pages=897-902
|Publisher=IOS Press
}}
{{Publikation Details
|Abstract=Ontology-Based Data Access (OBDA) is a recent paradigm aiming at enhancing data access by taking ontological knowledge into account. When using existential rules as ontological language, query answering is an undecidable problem, whence numerous decidable classes of ontologies have been defined, ranging from classes with very good computational complexities (AC0 in data complexity) to classes with much larger expressivity. However, actually implementable algorithms have been proposed only for very restricted classes (typically those coinciding with lightweight description logics). The aim of this paper is to show how to deal with more expressive ontologies by proposing an algorithm that performs both materialization and rewriting and is applicable for a significant generalization of lightweight description logics. To this end, we first modify an existing algorithm previously proposed for a very generic class of rules, namely greedy bounded treewidth sets of rules. We then exhibit a special case, called pattern oblivious rule sets, which significantly generalizes the ELHdr description logic, which underlies the OWL 2 EL ontology standard, while keeping the beneficial worst-case computational complexity. We last define a subclass of pattern oblivious rules that is recognizable in polynomial time.
|Download=Ecai-14-tr.pdf
|DOI Name=10.3233/978-1-61499-419-0-897
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.3233/978-1-61499-419-0-897
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4029

2014-10-28T10:04:03Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
|FurtherAuthors=Sebastian Rudolph
}}
{{Inproceedings
|Referiert=1
|Title=Mixing Materialization and Query Rewriting for Existential Rules
|To appear=0
|Year=2014
|Booktitle=ECAI
|Pages=897-902
}}
{{Publikation Details
|Abstract=Ontology-Based Data Access (OBDA) is a recent paradigm aiming at enhancing data access by taking ontological knowledge into account. When using existential rules as ontological language, query answering is an undecidable problem, whence numerous decidable classes of ontologies have been defined, ranging from classes with very good computational complexities (AC0 in data complexity) to classes with much larger expressivity. However, actually implementable algorithms have been proposed only for very restricted classes (typically those coinciding with lightweight description logics). The aim of this paper is to show how to deal with more expressive ontologies by proposing an algorithm that performs both materialization and rewriting and is applicable for a significant generalization of lightweight description logics. To this end, we first modify an existing algorithm previously proposed for a very generic class of rules, namely greedy bounded treewidth sets of rules. We then exhibit a special case, called pattern oblivious rule sets, which significantly generalizes the ELHdr description logic, which underlies the OWL 2 EL ontology standard, while keeping the beneficial worst-case computational complexity. We last define a subclass of pattern oblivious rules that is recognizable in polynomial time.
|Download=Ecai-14-tr.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.3233/978-1-61499-419-0-897
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Ecai-14-tr.pdf

2014-10-28T10:03:52Z

Michael Thomazo:

Inproceedings3152

2014-10-28T10:01:04Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Jean-François
|ErsterAutorNachname=Baget
|FurtherAuthors=Marie-Laure Mugnier; Sebastian Rudolph; Michaël Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=Walking the Complexity Lines for Generalized Guarded Existential Rules
|To appear=0
|Year=2011
|Month=Juli
|Booktitle=Proceedings of the 22nd International Joint Conference on Artificial Intelligence
|Pages=712-717
|Publisher=IJCAI/AAAI
|Editor=Toby Walsh
}}
{{Publikation Details
|Abstract=We establish complexities of the conjunctive query entailment problem for classes of existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of greedy bounded treewidth sets (gbts) of rules, which covers guarded rules, and their known generalizations, namely (weakly) frontier-guarded rules. We provide a generic algorithm for query entailment with gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several gbts classes, whose complexity was unknown, namely frontier-one, frontier-guarded and weakly frontier-guarded rules, with respect to combined complexity (with both unbounded and bounded predicate arity) and data complexity.
|Download=Ijcai-11-bmrt.pdf
|Forschungsgruppe=Computational Logic
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}
{{Forschungsgebiet Auswahl}}
{{Forschungsgebiet Auswahl}}

Datei:Ijcai-11-bmrt.pdf

2014-10-28T10:00:54Z

Michael Thomazo:

Inproceedings4061

2014-10-28T09:58:10Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Mélanie
|ErsterAutorNachname=König
|FurtherAuthors=Michel Leclère;Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=On the Exploration of the Query Rewriting Space with Existential Rules
|To appear=0
|Year=2013
|Booktitle=Proceedings of the 7th International Conference on Web Reasoning and Rule Systems (RR 2013)
|Pages=123-137
|Publisher=Springer
}}
{{Publikation Details
|Abstract=We address the issue of Ontology-Based Data Access, with ontologies represented in the framework of existential rules, also known as Datalog+/-. A well-known approach involves rewriting the query using ontological knowledge. We focus here on the basic rewriting technique which consists of rewriting a conjunctive query (CQ) into a union of CQs. We assume that the set of rules is a finite unification set, i.e., for any CQ, there exists a finite sound and complete rewriting of this CQ with the rules. First, we study a generic breadth-first rewriting algorithm, which takes as input any rewriting operator. We define properties of the rewriting operator that ensure the correctness and the termination of this algorithm. Second, we study some operators with respect to the exhibited properties. All these operators have in common to be based on so-called piece-unifiers but they lead to different explorations of the rewriting space. Finally, an experimental comparison of these operators within an implementation of the generic breadth-first rewriting algorithm is presented.
|Download=Rr-13-klmt.pdf
|DOI Name=10.1007/978-3-642-39666-3_10
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-642-39666-3_10
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Rr-13-klmt.pdf

2014-10-28T09:56:36Z

Michael Thomazo:

Michaël Thomazo

2014-10-28T09:54:52Z

Michael Thomazo:

{{Mitarbeiter
|Vorname=Michaël
|Nachname=Thomazo
|Akademischer Titel=Dr.
|Forschungsgruppe=Computational Logic
|Stellung=Stipendiat
|Ehemaliger=0
|Telefon=+49 351 463 43560
|Fax=+49 351 463 32827
|Email=michael.thomazo@tu-dresden.de
|Raum=INF 2036
|Bild=thomazo-photo.jpg
|Info=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013.
|Info EN=I graduated from MPRI in 2010 at the Ecole Normale Supérieure de Cachan, France. I then started a Ph.D. in knowledge representation and reasoning within the INRIA team GraphIK, based in Montpellier, at LIRMM, supervised jointly by Marie-Laure Mugnier and Jean-François Baget. My thesis, entitled “Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms”, focused on data access when taking general domain knowledge into account. I am now a post-doctoral research assistant at the Computational Logic Group at the TU Dresden, since October 2013.
|DBLP=http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thomazo:Micha=euml=l
|Publikationen anzeigen=1
|Abschlussarbeiten anzeigen=0
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4064

2014-10-28T09:51:12Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Mélanie
|ErsterAutorNachname=König
|FurtherAuthors=Michel Leclère;Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=A Sound and Complete Backward Chaining Algorithm for Existential Rules
|To appear=0
|Year=2012
|Booktitle=Proceedings of the 6th International Conference on Web Reasoning and Rule Systems (RR 2012)
|Pages=122-138
|Publisher=Springer
}}
{{Publikation Details
|Abstract=We address the issue of Ontology-Based Data Access which consists
of exploiting the semantics expressed in ontologies while querying data.
Ontologies are represented in the framework of existential rules, also known as
Datalog+/-.We focus on the backward chaining paradigm, which involves rewriting
the query (assumed to be a conjunctive query, CQ) into a set of CQs (seen as a
union of CQs). The proposed algorithm accepts any set of existential rules as input
and stops for so-called finite unification sets of rules (fus). The rewriting step
relies on a graph notion, called a piece, which allows to identify subsets of atoms
from the query that must be processed together. We first show that our rewriting
method computes a minimal set of CQs when this set is finite, i.e., the set of rules
is a fus. We then focus on optimizing the rewriting step. First experiments are
reported.
|Download=Rr-12-klmt.pdf
|DOI Name=10.1007/978-3-642-33203-6_10
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-642-33203-6_10
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Rr-12-klmt.pdf

2014-10-28T09:51:03Z

Michael Thomazo:

Inproceedings4057

2014-10-28T09:45:26Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Marie-Laure
|ErsterAutorNachname=Mugnier
|FurtherAuthors=Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=An Introduction to Ontology-Based Query Answering with Existential Rules
|To appear=0
|Year=2014
|Booktitle=Reasoning Web Summer School
|Pages=245-278
|Publisher=Springer
}}
{{Publikation Details
|Abstract=The need for an ontological layer on top of data, associated
with advanced reasoning mechanisms able to exploit ontological knowledge,
has been acknowledged in the database, knowledge representation
and Semantic Web communities. We focus here on the ontology-based
data querying problem, which consists in querying data while taking ontological
knowledge into account. To tackle this problem, we consider a
logical framework based on existential rules, also called Datalog+/-.
In this course, we introduce fundamental notions on ontology-based query
answering with existential rules. We present basic reasoning techniques,
explain the relationships with other formalisms such as lightweight description
logics, and review decidability results as well as associated algorithms.
We end with ongoing research and some challenging issues.
|Download=Main.pdf
|DOI Name=10.1007/978-3-319-10587-1_6
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-319-10587-1_6
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4062

2014-10-28T09:42:26Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=From EL to Tractable Existential Rules with Complex Role Inclusions
|To appear=0
|Year=2012
|Booktitle=Description Logics
}}
{{Publikation Details
|Abstract=Ontology-based data access consists in using ontologies while querying data. Due to the high complexity of this problem, considering lightweight description logics like EL is especially relevant. Another strand of research is based on existential rules. In this paper, we use this latter formalism in order to cover EL with the same complexity of reasoning while allowing any predicate arity and some cycles on variables. We then add complex role inclusions to enhance expressivity, while staying polynomial in data complexity and generalizing existing results. In particular, we consider transitivity and right/left identity rules, which do not behave well with respect to usual decidability paradigms.
|Download=Dl-12-t.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://ceur-ws.org/Vol-846/paper_24.pdf
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4062

2014-10-28T09:41:49Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Michaël
|ErsterAutorNachname=Thomazo
}}
{{Inproceedings
|Referiert=1
|Title=From EL to Tractable Existential Rules with Complex Role Inclusions
|To appear=0
|Year=2012
|Booktitle=Description Logics
}}
{{Publikation Details
|Abstract=Ontology-based data access consists in using ontologies while querying
data. Due to the high complexity of this problem, considering lightweight
description logics like EL is especially relevant. Another strand of research is
based on existential rules. In this paper, we use this latter formalism in order to
cover EL with the same complexity of reasoning while allowing any predicate
arity and some cycles on variables. We then add complex role inclusions to enhance
expressivity, while staying polynomial in data complexity and generalizing
existing results. In particular, we consider transitivity and right/left identity rules,
which do not behave well with respect to usual decidability paradigms.
|Download=Dl-12-t.pdf
|Forschungsgruppe=Computational Logic
|DOI=http://ceur-ws.org/Vol-846/paper_24.pdf
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Datei:Dl-12-t.pdf

2014-10-28T09:41:39Z

Michael Thomazo:

Inproceedings4066

2014-10-28T09:36:14Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Jean-François
|ErsterAutorNachname=Baget
|FurtherAuthors=Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=Towards Farsighted Dependencies for Existential Rules
|To appear=0
|Year=2011
|Booktitle=Proceedings of the 5th International Conference on Web Reasoning and Rule Systems (RR 2011)
|Pages=30-45
|Publisher=Springer
}}
{{Publikation Details
|Abstract=We consider existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). These rules are particularly well-suited to the timely ontological query answering problem, which consists of querying data while taking terminological knowledge into account. Since this problem is not decidable in general, various conditions ensuring decidability have been proposed in the literature. In this paper, we focus on conditions that restrict the way rules may interact to ensure that the forward chaining mechanism is finite. After a review of existing proposals, we propose a generalization of the notion of rule dependency, namely k-dependency, that allows to enlarge halting cases. It can also be used to compile the rule base, which leads to improve query answering algorithms.
|Download=Rr-11-bmt.pdf
|DOI Name=10.1007/978-3-642-23580-1_4
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-642-23580-1_4
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Article4019

2014-10-28T09:32:59Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Marie-Laure
|ErsterAutorNachname=Mugnier
|FurtherAuthors=Geneviève Simonet;Michaël Thomazo;
}}
{{Article
|Referiert=1
|Title=On the complexity of entailment in existential conjunctive first-order logic with atomic negation
|To appear=0
|Year=2012
|Journal=Information and Computation
|Volume=215
|Pages=8-31
|Publisher=Elsevier
|Address=
}}
{{Publikation Details
|Download=Iac-12-mst.pdf
|DOI Name=10.1016/j.ic.2012.03.001
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1016/j.ic.2012.03.001
}}

Datei:Iac-12-mst.pdf

2014-10-28T09:32:53Z

Michael Thomazo:

Inproceedings4066

2014-10-28T09:30:11Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Jean-François
|ErsterAutorNachname=Baget
|FurtherAuthors=Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=Towards Farsighted Dependencies for Existential Rules
|To appear=0
|Year=2011
|Booktitle=Web Reasoning and Rule Systems (RR 2011)
|Pages=30-45
|Publisher=Springer
}}
{{Publikation Details
|Abstract=We consider existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). These rules are particularly well-suited to the timely ontological query answering problem, which consists of querying data while taking terminological knowledge into account. Since this problem is not decidable in general, various conditions ensuring decidability have been proposed in the literature. In this paper, we focus on conditions that restrict the way rules may interact to ensure that the forward chaining mechanism is finite. After a review of existing proposals, we propose a generalization of the notion of rule dependency, namely k-dependency, that allows to enlarge halting cases. It can also be used to compile the rule base, which leads to improve query answering algorithms.
|Download=Rr-11-bmt.pdf
|DOI Name=10.1007/978-3-642-23580-1_4
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-642-23580-1_4
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}

Inproceedings4066

2014-10-28T09:29:22Z

Michael Thomazo:

{{Publikation Erster Autor
|ErsterAutorVorname=Jean-François
|ErsterAutorNachname=Baget
|FurtherAuthors=Marie-Laure Mugnier;Michaël Thomazo;
}}
{{Inproceedings
|Referiert=1
|Title=Towards Farsighted Dependencies for Existential Rules
|To appear=0
|Year=2011
|Booktitle=Web Reasoning and Rule Systems (RR 2011)
|Pages=30-45
|Publisher=Springer
}}
{{Publikation Details
|Abstract=We consider existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). These rules are particularly well-suited to the timely ontological query answering problem, which consists of querying data while taking terminological knowledge into account. Since this problem is not decidable in general, various conditions ensuring decidability have been proposed in the literature. In this paper, we focus on conditions that restrict the way rules may interact to ensure that the forward chaining mechanism is finite. After a review of existing proposals, we propose a generalization of the notion of rule dependency, namely k-dependency, that allows to enlarge halting cases. It can also be used to compile the rule base, which leads to improve query answering algorithms.
|Download=Rr-11-bmt.pdf
|DOI Name=10.1016/j.ic.2012.03.001
|Forschungsgruppe=Computational Logic
|DOI=http://dx.doi.org/10.1007/978-3-642-23580-1_4
}}
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Existenzielle Regeln
}}