Georg Gottlob

Last updated

Georg Gottlob
Georg gottlob-official3.png
Born (1956-06-30) 30 June 1956 (age 68) [1]
Vienna, Austria
NationalityAustrian and Italian
Alma mater Vienna University of Technology
Awards
Scientific career
Fields
Institutions
Thesis Mehrwertige Logik – Aufbau und Anwendung in der Informatik  (1981)
Doctoral advisor Curt Christian [5]
Doctoral students
Website cs.ox.ac.uk/people/georg.gottlob

Georg Gottlob FRS is an Austrian-Italian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Calabria. He was Professor at the University of Oxford. [4] [6] [7] [8] [9] [10] [11] [12] [13]

Contents

Education

Gottlob obtained his undergraduate and PhD degrees in computer science at Vienna University of Technology in 1981.

Career and research

Gottlob is currently a chaired professor at the University of Calabria in Italy where he joined in 2023 due to the "Fantastic Équipe and great potential" [14] [15] . Until then, he was a professor of computing science at the Oxford University Department of Computer Science, where he helped establish the information systems research group. He is also a Fellow of St John's College, Oxford. Previously, he was a professor of computer science at Vienna University of Technology, where he still maintains an adjunct position. He was elected a member of the Royal Society in May 2010. [3] He is a founding member of the Oxford-Man Institute.

He has published more than 250 scientific articles in the areas of computational logic, database theory, and artificial intelligence, and one textbook on logic programming and databases. [16]

In the area of artificial intelligence, he is best known for his influential early work on the complexity of nonmonotonic logics [17] [18] and on (generalised) hypertree decompositions, [19] [20] a framework for obtaining tractable structural classes of constraint satisfaction problems, and a generalisation of the notion of tree decomposition from graph theory. This work has also had substantial impact in database theory, since it is known that the problem of evaluating conjunctive queries on relational databases is equivalent to the constraint satisfaction problem. [21] His recent work on XML query languages (notably XPath) has helped create the complexity-theoretical foundations of this area. [22] [23] [24]

Awards and honours

Gottlob has received numerous awards and honours including election to the Royal Society in 2010. His nomination for the Royal Society reads:

Georg Gottlob has made fundamental contributions to both artificial intelligence and to database systems. His research has centred on the algorithmic and logical aspects of knowledge representation, database queries, and recently for web data processing. His work has resulted in the invention of several efficient algorithms for constraint satisfaction, web data extraction and database query processing, some of which are now in widespread use. He has developed a common core to the underlying principles of artificial intelligence and databases. In his work on clarifying the intrinsic complexity of problems in these areas, Gottlob has solved open problems in computational logic, non-monotonic reasoning and database theory. [25]

Gottlob has also been designated as an ECCAI fellow in 2002, and received honorary doctorates from the University of Klagenfurt (2016) and the University of Vienna (2020).

Related Research Articles

Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving and computational linguistics.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

<span class="mw-page-title-main">Gödel Prize</span> Computer science award

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is closed under complementation. It is situated between NL and AC1, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs:

<span class="mw-page-title-main">Moshe Vardi</span> Israeli mathematicien and computer scientist

Moshe Ya'akov Vardi is an Israeli theoretical computer scientist. He is the Karen Ostrum George Distinguished Service Professor in Computational Engineering at Rice University, United States. and a faculty advisor for the Ken Kennedy Institute. His interests focus on applications of logic to computer science, including database theory, finite model theory, knowledge of multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science.

In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational databases can be expressed in this way. Conjunctive queries also have a number of desirable theoretical properties that larger classes of queries do not share.

<span class="mw-page-title-main">Ryan Williams (computer scientist)</span> Computer scientist

Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.

ACM SIGLOG or SIGLOG is the Association for Computing Machinery Special Interest Group on Logic and Computation. It publishes a news magazine, and has the annual ACM–IEEE Symposium on Logic in Computer Science (LICS) as its flagship conference. In addition, it publishes an online newsletter, the SIGLOG Monthly Bulletin, and "maintains close ties" with the related academic journal ACM Transactions on Computational Logic.

Stefan Szeider is an Austrian computer scientist who works on the areas of algorithms, computational complexity, theoretical computer science, and more specifically on propositional satisfiability, constraint satisfaction problems, and parameterised complexity. He is a full professor at the Faculty of Informatics at the Vienna University of Technology, the head of the Algorithms and Complexity Group, and co-chair of the Vienna Center for Logic and Algorithms (VCLA) of TU Wien.

Phokion G. KolaitisACM is a computer scientist who is currently a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.

<span class="mw-page-title-main">Nicola Leone</span> Italian computer scientist

Nicola Leone is an Italian computer scientist who works in the areas of artificial intelligence, knowledge representation and reasoning, and database theory. Leone is currently the rector of the University of Calabria and a professor of Computer Science. Previously, he was a professor of Database Systems at the TU Wien.

Deepak Kapur is a Distinguished Professor in the Department of Computer Science at the University of New Mexico.

Vadalog is a system for performing complex logic reasoning tasks over knowledge graphs. Its language is based on an extension of the rule-based language Datalog, Warded Datalog±.

Disjunctive Datalog is an extension of the logic programming language Datalog that allows disjunctions in the heads of rules. This extension enables disjunctive Datalog to express several NP-hard problems that are not known to be expressable in plain Datalog. Disjunctive Datalog has been applied in the context of reasoning about ontologies in the semantic web. DLV is an implementation of disjunctive Datalog.

DatalogZ is an extension of Datalog with integer arithmetic and comparisons. The decision problem of whether or not a given ground atom (fact) is entailed by a DatalogZ program is RE-complete, which can be shown by a reduction to diophantine equations.

References

  1. ↑ "GOTTLOB, Prof. Georg". Who's Who 2014, A & C Black, an imprint of Bloomsbury Publishing plc, 2014; online edn, Oxford University Press.(subscription required)
  2. ↑ "ACM Fellows". Association for Computing Machinery. 2009. Retrieved 24 May 2010.
  3. 1 2 "New Royal Society Fellows for 2010". Oxford University. 21 May 2010. Archived from the original on 27 May 2010. Retrieved 24 May 2010.
  4. 1 2 Georg Gottlob publications indexed by Google Scholar
  5. 1 2 Georg Gottlob at the Mathematics Genealogy Project
  6. ↑ Georg Gottlob author profile page at the ACM Digital Library
  7. ↑ Winslett, M. (2007). "Georg Gottlob speaks out". ACM SIGMOD Record. 36 (2): 27–33. doi:10.1145/1328854.1328860. S2CID   20605617. Archived from the original (PDF) on 11 June 2011.
  8. ↑ Georg Gottlob's publications indexed by the Scopus bibliographic database. (subscription required)
  9. ↑ Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F. (2006). "The DLV system for knowledge representation and reasoning". ACM Transactions on Computational Logic. 7 (3): 499. arXiv: cs/0211004 . doi:10.1145/1149114.1149117. S2CID   1189466.
  10. ↑ Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A. (2001). "Complexity and expressive power of logic programming". ACM Computing Surveys. 33 (3): 374. CiteSeerX   10.1.1.28.4997 . doi:10.1145/502807.502810. S2CID   518049.
  11. ↑ Georg Gottlob at DBLP Bibliography Server OOjs UI icon edit-ltr-progressive.svg
  12. ↑ Eiter, T.; Gottlob, G.; Mannila, H. (1997). "Disjunctive datalog". ACM Transactions on Database Systems. 22 (3): 364. doi: 10.1145/261124.261126 . S2CID   8755376.
  13. ↑ Eiter, T.; Gottlob, G. (1995). "The complexity of logic-based abduction". Journal of the ACM. 42: 3–42. doi: 10.1145/200836.200838 . S2CID   14167261.
  14. ↑ "L'esordio di Georg Gottlob all'Unical: "Équipe fantastica e grandi potenzialità"". Corriere della Calabria (in Italian). 15 September 2023. Retrieved 20 September 2023.
  15. ↑ "Da Oxford alla Calabria: il re dell'AI sceglie l'Italia". La Voce di New York. 18 September 2023. Retrieved 20 September 2023.
  16. ↑ Stefano Ceri, Georg Gottlob, and Letizia Tanca: Logic programming and databases. Springer-Verlag, 1990. ISBN   9783642839542
  17. ↑ Gottlob, G. (1992). "Complexity Results for Nonmonotonic Logics". Journal of Logic and Computation. 2 (3): 397–425. doi:10.1093/logcom/2.3.397.
  18. ↑ Eiter, T.; Gottlob, G. (1992). "On the complexity of propositional knowledge base revision, updates, and counterfactuals". Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '92. p. 261. doi:10.1145/137097.137886. ISBN   978-0897915199. S2CID   674242.
  19. ↑ Eiter, T.; Gottlob, G. (1995). "Identifying the Minimal Transversals of a Hypergraph and Related Problems". SIAM Journal on Computing. 24 (6): 1278. CiteSeerX   10.1.1.37.883 . doi:10.1137/S0097539793250299.
  20. ↑ Gottlob, G.; Leone, N.; Scarcello, F. (2002). "Hypertree Decompositions and Tractable Queries". Journal of Computer and System Sciences. 64 (3): 579. arXiv: cs/9812022 . doi:10.1006/jcss.2001.1809. S2CID   121575202.
  21. ↑ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "Conjunctive-Query Containment and Constraint Satisfaction". Journal of Computer and System Sciences . 61 (2): 302–332. doi: 10.1006/jcss.2000.1713 .
  22. ↑ Furche, T.; Gottlob, G.; Grasso, G.; Schallhart, C.; Sellers, A. (2012). "OXPath: A language for scalable data extraction, automation, and crawling on the deep web". The VLDB Journal. 22: 47–72. doi:10.1007/s00778-012-0286-6. S2CID   14542107.
  23. ↑ Gottlob, G.; Koch, C.; Pichler, R. (2005). "Efficient algorithms for processing XPath queries". ACM Transactions on Database Systems. 30 (2): 444. CiteSeerX   10.1.1.18.9591 . doi:10.1145/1071610.1071614. S2CID   904373.
  24. ↑ Gottlob, G.; Koch, C.; Pichler, R.; Segoufin, L. (2005). "The complexity of XPath query evaluation and XML typing". Journal of the ACM. 52 (2): 284. CiteSeerX   10.1.1.598.1938 . doi:10.1145/1059513.1059520. S2CID   6253858.
  25. ↑ "EC/2010/17: Gottlob, Georg. Library and Archive Catalogue". London: The Royal Society. Archived from the original on 10 July 2019.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.