Georg Gottlob: Publications

Efficient Datalog Abduction through Bounded Treewidth

Georg Gottlob, Reinhard Pichler and Fang Wei

In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada pages 1626-1631. AAAI Press, 2007.

Details | BibTeX

On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition

Georg Gottlob, Gianluigi Greco

In Jeffrey K. MacKie-Mason, David C. Parkes and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007 pages 152-161. ACM, 2007.

Details | BibTeX | DOI (10.1145/1250910.1250934)

The Lixto Systems Applications in Business Intelligence and Semantic Web

Robert Baumgartner, Oliver Frölich and Georg Gottlob

In Enrico Franconi, Michael Kifer and Wolfgang May, editors, The Semantic Web: Research and Applications, 4th European Semantic Web Conference, ESWC 2007, Innsbruck, Austria, June 3-7, 2007, Proceedings Vol. 4519 of Lecture Notes in Computer Science, pages 16-26. Springer, 2007.

Details | BibTeX | DOI (10.1007/978-3-540-72667-8_3)

Complexity of Pure Equilibria in Bayesian Games

Georg Gottlob, Gianluigi Greco and Toni Mancini

In Manuela M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007 pages 1294-1299. 2007.

Details | BibTeX | Link (pdf)

Conditional Constraint Satisfaction: Logical Foundations and Complexity

Georg Gottlob, Gianluigi Greco and Toni Mancini

In Manuela M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007 pages 88-93. 2007.

Details | BibTeX | Link (pdf)

Generalized hypertree decompositions: np-hardness and tractable variants

Georg Gottlob, Zoltán Miklós and Thomas Schwentick

In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China pages 13-22. ACM, 2007.

Details | BibTeX | DOI (10.1145/1265530.1265533)

Monadic datalog over finite structures with bounded treewidth

Georg Gottlob, Reinhard Pichler and Fang Wei

In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China pages 165-174. ACM, 2007.

Details | BibTeX | Link

Foundations of Rule-Based Query Answering

François Bry et al.

In Grigoris Antoniou et al. , editors, Reasoning Web, Third International Summer School 2007, Dresden, Germany, September 3-7, 2007, Tutorial Lectures Vol. 4636 of Lecture Notes in Computer Science, pages 1-153. Springer, 2007.

Details | BibTeX | DOI (10.1007/978-3-540-74615-7_1)

A Backtracking-Based Algorithm for Computing Hypertree-Decompositions

Georg Gottlob, Marko Samer

CoRR, Vol. abs/cs/0701083. 2007.

Details | BibTeX | DOI (http://arxiv.org/abs/cs/0701083)

Hypertree width and related hypergraph invariants

Isolde Adler, Georg Gottlob and Martin Grohe

Eur. J. Comb. Vol. 28, No. 8, pages 2167-2181. 2007.

Details | BibTeX | DOI (10.1016/j.ejc.2007.04.013)

A logical approach to multicut problems

Georg Gottlob, Stephanie Tien Lee

Inf. Process. Lett. Vol. 103, No. 4, pages 136-141. 2007.

Details | BibTeX | DOI (10.1016/j.ipl.2007.03.005)

Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning

Georg Gottlob, Reinhard Pichler and Fang Wei

In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA AAAI Press, 2006.

Details | BibTeX

The Lixto Project: Exploring New Frontiers of Web Data Extraction

Julien Carme et al.

In BNCOD pages 1-15. 2006.

Details | BibTeX | DOI (10.1007/11788911_1)

Tractable database design through bounded treewidth

Georg Gottlob, Reinhard Pichler and Fang Wei

In Stijn Vansummeren, editor, Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, Maryland, USA pages 124-133. ACM, 2006.

Details | BibTeX | DOI (10.1145/1142351.1142370)

Data exchange: computing cores in polynomial time

Georg Gottlob, Alan Nash

In Stijn Vansummeren, editor, Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, Maryland, USA pages 40-49. ACM, 2006.

Details | BibTeX | DOI (10.1145/1142351.1142358)

RDF Querying: Language Constructs and Evaluation Methods Compared

Tim Furche et al.

In Pedro Barahona et al. , editors, Reasoning Web, Second International Summer School 2006, Lisbon, Portugal, September 4-8, 2006, Tutorial Lectures Vol. 4126 of Lecture Notes in Computer Science, pages 1-52. Springer, 2006.

Details | BibTeX | DOI (10.1007/11837787_1)

A Formal Comparison of Visual Web Wrapper Generators

Georg Gottlob, Christoph Koch

In Jir\'\i Wiedermann et al. , editors, SOFSEM 2006: Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science, Mer\'∈, Czech Republic, January 21-27, 2006, Proceedings Vol. 3831 of Lecture Notes in Computer Science, pages 30-48. Springer, 2006.

Details | BibTeX | DOI (10.1007/11611257_3)

The DLV system for knowledge representation and reasoning

Nicola Leone et al.

ACM Trans. Comput. Log. Vol. 7, No. 3, pages 499-562. 2006.

Details | BibTeX | DOI (10.1145/1149114.1149117)

Conjunctive Queries over Trees

Georg Gottlob, Christoph Koch and Klaus U. Schulz

CoRR, Vol. abs/cs/0602004. 2006.

Details | BibTeX | Link

Conjunctive queries over trees

Georg Gottlob, Christoph Koch and Klaus U. Schulz

J. ACM, Vol. 53, No. 2, pages 238-272. 2006.

Details | BibTeX | DOI (10.1145/1131342.1131345)

Reasoning under minimal upper bounds in propositional logic

Thomas Eiter, Georg Gottlob

Theor. Comput. Sci. Vol. 369, No. 1-3, pages 82-115. 2006.

Details | BibTeX | DOI (10.1016/j.tcs.2006.07.054)

Web Data Extraction for Business Intelligence: The Lixto Approach

Georg Gottlob

In Gottfried Vossen et al. , editors, Datenbanksysteme in Business, Technologie und Web, 11. Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme" (DBIS), Karlsruhe, 2.-4. März 2005 Vol. 65 of LNI, pages 30-47. GI, 2005.

Details | BibTeX

Asymptotic Conditional Probability in Modal Logic: A Probabilistic Reconstruction of Nonmonotonic Logic

Riccardo Rosati, Georg Gottlob

In Leslie Pack Kaelbling, Alessandro Saffiotti, editors, IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005 pages 1378-1383. Professional Book Center, 2005.

Details | BibTeX | Link (pdf)

The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions

Georg Gottlob, Gianluigi Greco and Francesco Scarcello

In Leslie Pack Kaelbling, Alessandro Saffiotti, editors, IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005 pages 150-155. Professional Book Center, 2005.

Details | BibTeX | Link (pdf)

The Personal Publication Reader

Fabian Abel et al.

In Yolanda Gil et al. , editors, The Semantic Web - ISWC 2005, 4th International Semantic Web Conference, ISWC 2005, Galway, Ireland, November 6-10, 2005, Proceedings Vol. 3729 of Lecture Notes in Computer Science, pages 1050-1053. Springer, 2005.

Details | BibTeX | DOI (10.1007/11574620_75)

Data Integration: a Challenging ASP Application

Nicola Leone et al.

In Chitta Baral et al. , editors, Logic Programming and Nonmonotonic Reasoning, 8th International Conference, LPNMR 2005, Diamante, Italy, September 5-8, 2005, Proceedings Vol. 3662 of Lecture Notes in Computer Science, pages 379-383. Springer, 2005.

Details | BibTeX | DOI (10.1007/11546207_31)

Computing cores for data exchange: new algorithms and practical solutions

Georg Gottlob

In Chen Li, editor, Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA pages 148-159. ACM, 2005.

Details | BibTeX | DOI (10.1145/1065167.1065187)

Information Extraction for the Semantic Web

Robert Baumgartner et al.

In Norbert Eisinger, Jan Maluszynski, editors, Reasoning Web, First International Summer School 2005, Msida, Malta, July 25-29, 2005, Tutorial Lectures Vol. 3564 of Lecture Notes in Computer Science, pages 275-289. Springer, 2005.

Details | BibTeX | DOI (10.1007/11526988_8)

Boosting Information Integration: The INFOMIX System

Nicola Leone et al.

In Andrea Cal\`\i et al. , editors, Proceedings of the Thirteenth Italian Symposium on Advanced Database Systems, SEBD 2005, Brixen-Bressanone (near Bozen-Bolzano), Italy, June 19-22, 2005 pages 55-66. 2005.

Details | BibTeX

The INFOMIX system for advanced integration of incomplete and inconsistent data

Nicola Leone et al.

In Fatma Özcan, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005 pages 915-917. ACM, 2005.

Details | BibTeX | DOI (10.1145/1066157.1066286)

Hypertree Decompositions: Structure, Algorithms, and Applications

Georg Gottlob et al.

In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers Vol. 3787 of Lecture Notes in Computer Science, pages 1-15. Springer, 2005.

Details | BibTeX | DOI (10.1007/11604686_1)

Integrating Semi-structured Data into Business Applications: A Web Intelligence Example

Robert Baumgartner et al.

In Klaus-Dieter Althoff et al. , editors, Professional Knowledge Management, Third Biennial Conference, WM 2005, Kaiserslautern, Germany, April 10-13, 2005, Revised Selected Papers Vol. 3782 of Lecture Notes in Computer Science, pages 469-482. Springer, 2005.

Details | BibTeX | DOI (10.1007/11590019_54)

Complexity of propositional nested circumscription and nested abnormality theories

Marco Cadoli, Thomas Eiter and Georg Gottlob

ACM Trans. Comput. Log. Vol. 6, No. 2, pages 232-272. 2005.

Details | BibTeX | DOI (10.1145/1055686.1055688)

Efficient algorithms for processing XPath queries

Georg Gottlob, Christoph Koch and Reinhard Pichler

ACM Trans. Database Syst. Vol. 30, No. 2, pages 444-491. 2005.

Details | BibTeX | DOI (10.1145/1071610.1071614)

The complexity of XPath query evaluation and XML typing

Georg Gottlob et al.

J. ACM, Vol. 52, No. 2, pages 284-335. 2005.

Details | BibTeX | DOI (10.1145/1059513.1059520)

Pure Nash Equilibria: Hard and Easy Games

Georg Gottlob, Gianluigi Greco and Francesco Scarcello

J. Artif. Intell. Res. (JAIR), Vol. 24, pages 357-406. 2005.

Details | BibTeX | Link (html)

Advances in Databases and Information Systems, 8th East European Conference, ADBIS 2004, Budapest, Hungary, September 22-25, 2004, Proceesing

Georg Gottlob, András A. Benczúr and János Demetrovics, editors

Vol. 3255 of Lecture Notes in Computer Science. Springer. 2004.

Details | BibTeX

Hypergraph Transversals

Georg Gottlob

In Dietmar Seipel, Jose Maria Turull Torres, editors, Foundations of Information and Knowledge Systems, Third International Symposium, FoIKS 2004, Wilhelminenburg Castle, Austria, February 17-20, 2004, Proceedings Vol. 2942 of Lecture Notes in Computer Science, pages 1-5. Springer, 2004.

Details | BibTeX | Link

Second-Order Logic over Finite Structures - Report on a Research Programme

Georg Gottlob

In David A. Basin, Michaël Rusinowitch, editors, Automated Reasoning - Second International Joint Conference, IJCAR 2004, Cork, Ireland, July 4-8, 2004, Proceedings Vol. 3097 of Lecture Notes in Computer Science, pages 229-243. Springer, 2004.

Details | BibTeX | Link

The Lixto Data Extraction Project - Back and Forth between Theory and Practice

Georg Gottlob et al.

In Alin Deutsch, editor, Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 14-16, 2004, Paris, France pages 1-12. ACM, 2004.

Details | BibTeX | Link (pdf) | DOI (10.1145/1055558.1055560)

Conjunctive Queries over Trees

Georg Gottlob, Christoph Koch and Klaus U. Schulz

In Alin Deutsch, editor, Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 14-16, 2004, Paris, France pages 189-200. ACM, 2004.

Details | BibTeX | Link (pdf) | DOI (10.1145/1055558.1055585)

Interactively Adding Web Service Interfaces to Existing Web Applications

Robert Baumgartner et al.

In 2004 Symposium on Applications and the Internet (SAINT 2004), 26-30 January 2004, Tokyo, Japan pages 74-80. IEEE Computer Society, 2004.

Details | BibTeX | Link

Monadic datalog and the expressive power of languages for Web information extraction

Georg Gottlob, Christoph Koch

J. ACM, Vol. 51, No. 1, pages 74-113. 2004.

Details | BibTeX | DOI (10.1145/962446.962450)

Existential second-order logic over graphs: Charting the tractability frontier

Georg Gottlob, Phokion G. Kolaitis and Thomas Schwentick

J. ACM, Vol. 51, No. 2, pages 312-362. 2004.

Details | BibTeX | DOI (10.1145/972639.972646)

Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width

Georg Gottlob, Reinhard Pichler

SIAM J. Comput. Vol. 33, No. 2, pages 351-378. 2004.

Details | BibTeX | DOI (10.1137/S0097539701396807)

Logic-based Web Information Extraction

Georg Gottlob, Christoph Koch

SIGMOD Record, Vol. 33, No. 2, pages 87-94. 2004.

Details | BibTeX | Link (pdf) | DOI (10.1145/1024694.1024711)

2nd International Workshop on Complexity in Automated Deduction (CiAD) - Foreword

Georg Gottlob, Miki Hermann and Michaël Rusinowitch

Theory Comput. Syst. Vol. 37, No. 6, pages 639-640. 2004.

Details | BibTeX | DOI (http://dx.doi.org/10.1007/s00224-004-3706-1)

IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003

Georg Gottlob, Toby Walsh, editors

Morgan Kaufmann. 2003.

Details | BibTeX

XPath Query Processing

Georg Gottlob, Christoph Koch

In Georg Lausen, Dan Suciu, editors, Database Programming Languages, 9th International Workshop, DBPL 2003, Potsdam, Germany, September 6-8, 2003, Revised Papers Vol. 2921 of Lecture Notes in Computer Science, pages 20. Springer, 2003.

Details | BibTeX | Link

XPath Query Evaluation: Improving Time and Space Efficiency

Georg Gottlob, Christoph Koch and Reinhard Pichler

In Umeshwar Dayal, Krithi Ramamritham and T. M. Vijayaraman, editors, Proceedings of the 19th International Conference on Data Engineering, March 5-8, 2003, Bangalore, India pages 379-390. IEEE Computer Society, 2003.

Details | BibTeX | Link

Web Information Acquisition with Lixto Suite

Robert Baumgartner et al.

In Umeshwar Dayal, Krithi Ramamritham and T. M. Vijayaraman, editors, Proceedings of the 19th International Conference on Data Engineering, March 5-8, 2003, Bangalore, India pages 747-749. IEEE Computer Society, 2003.

Details | BibTeX | Link

Visual Programming of Web Data Aggregation Applications

Robert Baumgartner, Georg Gottlob and Marcus Herzog

In Subbarao Kambhampati, Craig A. Knoblock, editors, Proceedings of IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03), August 9-10, 2003, Acapulco, Mexico pages 137-142. 2003.

Details | BibTeX | DOI (http://www.isi.edu/info-agents/workshops/ijcai03/papers/Herzog-ijcai03-herzog.pdf)

The complexity of XPath query evaluation

Georg Gottlob, Christoph Koch and Reinhard Pichler

In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA pages 179-190. ACM, 2003.

Details | BibTeX | DOI (10.1145/773153.773171)

Pure Nash equilibria: hard and easy games

Georg Gottlob, Gianluigi Greco and Francesco Scarcello

In Joseph Y. Halpern, Moshe Tennenholtz, editors, Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), Bloomington, Indiana, USA, June 20-22, 2003 pages 215-230. ACM, 2003.

Details | BibTeX | DOI (10.1145/846241.846269)

A Formal Comparison of Visual Web Wrapper Generators

Georg Gottlob, Christoph Koch

CoRR, Vol. cs.DB/0310012. 2003.

Details | BibTeX | Link

On the complexity of single-rule datalog queries

Georg Gottlob, Christos H. Papadimitriou

Inf. Comput. Vol. 183, No. 1, pages 104-122. 2003.

Details | BibTeX | DOI (10.1016/S0890-5401(03)00012-9)

Guest Editor's Foreword

Georg Gottlob

J. Comput. Syst. Sci. Vol. 66, No. 1, pages 1. 2003.

Details | BibTeX | DOI (10.1016/S0022-0000(02)00026-0)

Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

Georg Gottlob, Nicola Leone and Francesco Scarcello

J. Comput. Syst. Sci. Vol. 66, No. 4, pages 775-808. 2003.

Details | BibTeX | DOI (10.1016/S0022-0000(03)00030-8)

New Results on Monotone Dualization and Generating Hypergraph Transversals

Thomas Eiter, Georg Gottlob and Kazuhisa Makino

SIAM J. Comput. Vol. 32, No. 2, pages 514-537. 2003.

Details | BibTeX | Link

XPath Processing in a Nutshell

Georg Gottlob, Christoph Koch and Reinhard Pichler

SIGMOD Record, Vol. 32, No. 1, pages 12-19. 2003.

Details | BibTeX | Link (pdf) | DOI (10.1145/640990.640992)

XPath processing in a nutshell

Georg Gottlob, Christoph Koch and Reinhard Pichler

SIGMOD Record, Vol. 32, No. 2, pages 21-27. 2003.

Details | BibTeX | DOI (10.1145/776985.776988)

Multiagent Compromises, Joint Fixpoints, and Stable Models

Francesco Buccafurri, Georg Gottlob

In Antonis C. Kakas, Fariba Sadri, editors, Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part I Vol. 2407 of Lecture Notes in Computer Science, pages 561-585. Springer, 2002.

Details | BibTeX | Link

Combining hypertree, bicomp, and hinge decomposition

Georg Gottlob, Martin Hutle and Franz Wotawa

In Frank van Harmelen, editor, Proceedings of the 15th Eureopean Conference on Artificial Intelligence, ECAI'2002, Lyon, France, July 2002 pages 161-165. IOS Press, 2002.

Details | BibTeX

The DLV System

Nicola Leone et al.

In Sergio Flesca et al. , editors, Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings Vol. 2424 of Lecture Notes in Computer Science, pages 537-540. Springer, 2002.

Details | BibTeX | Link

Hypergraph Transversal Computation and Related Problems in Logic and AI

Thomas Eiter, Georg Gottlob

In Sergio Flesca et al. , editors, Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings Vol. 2424 of Lecture Notes in Computer Science, pages 549-564. Springer, 2002.

Details | BibTeX | Link

Monadic Queries over Tree-Structured Data

Georg Gottlob, Christoph Koch

In 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 22-25 July 2002, Copenhagen, Denmark, Proceedings pages 189-202. IEEE Computer Society, 2002.

Details | BibTeX | DOI (10.1109/LICS.2002.1029828)

Visual Data Extraction Through Visual Logic Programming

Georg Gottlob

In Salem Benferhat, Enrico Giunchiglia, editors, 9th International Workshop on Non-Monotonic Reasoning (NMR 2002), April 19-21, Toulouse, France, Proceedings pages 4. 2002.

Details | BibTeX

Monadic Datalog and the Expressive Power of Languages for Web Information Extraction

Georg Gottlob, Christoph Koch

In Lucian Popa, editor, Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, Madison, Wisconsin, USA pages 17-28. ACM, 2002.

Details | BibTeX | Link (pdf) | DOI (10.1145/543613.543617)

New results on monotone dualization and generating hypergraph transversals

Thomas Eiter, Georg Gottlob and Kazuhisa Makino

In STOC pages 14-22. 2002.

Details | BibTeX | DOI (10.1145/509907.509912)

Efficient Algorithms for Processing XPath Queries

Georg Gottlob, Christoph Koch and Reinhard Pichler

In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong, China pages 95-106. Morgan Kaufmann, 2002.

Details | BibTeX | Link (pdf)

Datalog LITE: a deductive query language with linear time model checking

Georg Gottlob, Erich Grädel and Helmut Veith

ACM Trans. Comput. Log. Vol. 3, No. 1, pages 42-79. 2002.

Details | BibTeX | DOI (10.1145/504077.504079)

Fixed-parameter complexity in AI and nonmonotonic reasoning

Georg Gottlob, Francesco Scarcello and Martha Sideri

Artif. Intell. Vol. 138, No. 1-2, pages 55-86. 2002.

Details | BibTeX | DOI (10.1016/S0004-3702(02)00182-0)

Complexity of Nested Circumscription and Nested Abnormality Theories

Marco Cadoli, Thomas Eiter and Georg Gottlob

CoRR, Vol. cs.AI/0207072. 2002.

Details | BibTeX | Link

The DLV System for Knowledge Representation and Reasoning

Nicola Leone et al.

CoRR, Vol. cs.AI/0211004. 2002.

Details | BibTeX | Link

Monadic Datalog and the Expressive Power of Languages for Web Information Extraction

Georg Gottlob, Christoph Koch

CoRR, Vol. cs.DB/0211020. 2002.

Details | BibTeX | Link

New Results on Monotone Dualization and Generating Hypergraph Transversals

Thomas Eiter, Georg Gottlob and Kazuhisa Makino

CoRR, Vol. cs.DS/0204009. 2002.

Details | BibTeX | Link

Hypertree Decompositions and Tractable Queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

J. Comput. Syst. Sci. Vol. 64, No. 3, pages 579-627. 2002.

Details | BibTeX | DOI (10.1006/jcss.2001.1809)

Computing LOGCFL certificates

Georg Gottlob, Nicola Leone and Francesco Scarcello

Theor. Comput. Sci. Vol. 270, No. 1-2, pages 761-777. 2002.

Details | BibTeX | DOI (10.1016/S0304-3975(01)00108-6)

Propositional default logics made easier: computational complexity of model checking

Robert Baumgartner, Georg Gottlob

Theor. Comput. Sci. Vol. 289, No. 1, pages 591-627. 2002.

Details | BibTeX

Second-Order Logic over Strings: Regular and Non-regular Fragments

Thomas Eiter, Georg Gottlob and Thomas Schwentick

In Werner Kuich, Grzegorz Rozenberg and Arto Salomaa, editors, Developments in Language Theory, 5th International Conference, DLT 2001, Vienna, Austria, July 16-21, 2001, Revised Papers Vol. 2295 of Lecture Notes in Computer Science, pages 37-56. Springer, 2001.

Details | BibTeX | Link

Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width

Georg Gottlob, Reinhard Pichler

In Fernando Orejas, Paul G. Spirakis and Jan van Leeuwen, editors, Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings Vol. 2076 of Lecture Notes in Computer Science, pages 708-719. Springer, 2001.

Details | BibTeX | Link

Complexity of Nested Circumscription and Abnormality Theories

Marco Cadoli, Thomas Eiter and Georg Gottlob

In Bernhard Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001 pages 169-174. Morgan Kaufmann, 2001.

Details | BibTeX

The Elog Web Extraction Language

Robert Baumgartner, Sergio Flesca and Georg Gottlob

In Robert Nieuwenhuis, Andrei Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning, 8th International Conference, LPAR 2001, Havana, Cuba, December 3-7, 2001, Proceedings Vol. 2250 of Lecture Notes in Computer Science, pages 548-560. Springer, 2001.

Details | BibTeX | Link

Declarative Information Extraction, Web Crawling, and Recursive Wrapping with Lixto

Robert Baumgartner, Sergio Flesca and Georg Gottlob

In Thomas Eiter, Wolfgang Faber and Miroslaw Truszczynski, editors, Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings Vol. 2173 of Lecture Notes in Computer Science, pages 21-41. Springer, 2001.

Details | BibTeX | Link

Hypertree Decompositions: A Survey

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Jiri Sgall, Ales Pultr and Petr Kolman, editors, Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings Vol. 2136 of Lecture Notes in Computer Science, pages 37-57. Springer, 2001.

Details | BibTeX | Link

Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California, USA ACM, 2001.

Details | BibTeX | Link (pdf) | DOI (10.1145/375551.375579)

Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width

Georg Gottlob, Nicola Leone and Francesco Scarcello

In SEBD pages 147-154. 2001.

Details | BibTeX

The Lixto Wrapper Generation Tool

Georg Gottlob

In SEBD pages 3-10. 2001.

Details | BibTeX

InfoPipes: A Flexible Framework for M-Commerce Applications

Marcus Herzog, Georg Gottlob

In Fabio Casati, Dimitrios Georgakopoulos and Ming-Chien Shan, editors, Technologies for E-Services, Second International Workshop, TES 2001, Rome, Italy, September 14-15, 2001, Proceedings Vol. 2193 of Lecture Notes in Computer Science, pages 175-186. Springer, 2001.

Details | BibTeX | Link

Visual Web Information Extraction with Lixto

Robert Baumgartner, Sergio Flesca and Georg Gottlob

In Peter M. G. Apers et al. , editors, VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy pages 119-128. Morgan Kaufmann, 2001.

Details | BibTeX | Link (pdf)

Supervised Wrapper Generation with Lixto

Robert Baumgartner, Sergio Flesca and Georg Gottlob

In Peter M. G. Apers et al. , editors, VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy pages 715-716. Morgan Kaufmann, 2001.

Details | BibTeX | Link (pdf)

Complexity and expressive power of logic programming

Evgeny Dantsin et al.

ACM Comput. Surv. Vol. 33, No. 3, pages 374-425. 2001.

Details | BibTeX | DOI (10.1145/502807.502810)

Working with ARMs: Complexity Results on Atomic Representations of Herbrand Models

Georg Gottlob, Reinhard Pichler

Inf. Comput. Vol. 165, No. 2, pages 183-207. 2001.

Details | BibTeX | DOI (10.1006/inco.2000.2915)

The complexity of acyclic conjunctive queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

J. ACM, Vol. 48, No. 3, pages 431-498. 2001.

Details | BibTeX | Link

On ACTL Formulas Having Linear Counterexamples

Francesco Buccafurri et al.

J. Comput. Syst. Sci. Vol. 62, No. 3, pages 463-515. 2001.

Details | BibTeX

Existential Second-Order Logic over Graphs: Charting the Tractability Frontier

Georg Gottlob, Phokion G. Kolaitis and Thomas Schwentick

In FOCS pages 664-674. 2000.

Details | BibTeX

On the Complexity of Theory Curbing

Thomas Eiter, Georg Gottlob

In Michel Parigot, Andrei Voronkov, editors, Logic for Programming and Automated Reasoning, 7th International Conference, LPAR 2000, Reunion Island, France, November 11-12, 2000, Proceedings Vol. 1955 of Lecture Notes in Computer Science, pages 1-19. Springer, 2000.

Details | BibTeX | Link

A comparison of structural CSP decomposition methods

Georg Gottlob, Nicola Leone and Francesco Scarcello

Artif. Intell. Vol. 124, No. 2, pages 243-282. 2000.

Details | BibTeX | DOI (10.1016/S0004-3702(00)00078-3)

Existential second-order logic over strings

Thomas Eiter, Yuri Gurevich and Georg Gottlob

J. ACM, Vol. 47, No. 1, pages 77-131. 2000.

Details | BibTeX | DOI (10.1145/331605.331609)

Computer Science Logic, 12th International Workshop, CSL '98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings

Georg Gottlob, Etienne Grandjean and Katrin Seyr, editors

Vol. 1584 of Lecture Notes in Computer Science. Springer. 1999.

Details | BibTeX

On Tractable Queries and Constraints

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Trevor J. M. Bench-Capon, Giovanni Soda and A. Min Tjoa, editors, Database and Expert Systems Applications, 10th International Conference, DEXA '99, Florence, Italy, August 30 - September 3, 1999, Proceedings Vol. 1677 of Lecture Notes in Computer Science, pages 1-15. Springer, 1999.

Details | BibTeX | Link

Computing LOGCFL Certificates

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Jir\'\i Wiedermann, Peter van Emde Boas and Mogens Nielsen, editors, Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings Vol. 1644 of Lecture Notes in Computer Science, pages 361-371. Springer, 1999.

Details | BibTeX | Link

A Comparison of Structural CSP Decomposition Methods

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Thomas Dean, editor, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages pages 394-399. Morgan Kaufmann, 1999.

Details | BibTeX

On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases

Robert Baumgartner, Georg Gottlob

In Thomas Dean, editor, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages pages 64-69. Morgan Kaufmann, 1999.

Details | BibTeX

Working with Arms: Complexity Results on Atomic Representations of Herbrand Models

Georg Gottlob, Reinhard Pichler

In LICS pages 306-315. 1999.

Details | BibTeX | Link

On the Complexity of Single-Rule Datalog Queries

Georg Gottlob, Christos H. Papadimitriou

In Harald Ganzinger, David A. McAllester and Andrei Voronkov, editors, Logic Programming and Automated Reasoning, 6th International Conference, LPAR'99, Tbilisi, Georgia, September 6-10, 1999, Proceedings Vol. 1705 of Lecture Notes in Computer Science, pages 201-222. Springer, 1999.

Details | BibTeX

Fixed-Parameter Complexity in AI and Nonmonotonic Reasoning

Georg Gottlob, Francesco Scarcello and Martha Sideri

In Michael Gelfond, Nicola Leone and Gerald Pfeifer, editors, Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, El Paso, Texas, USA, December 2-4, 1999, Proceedings Vol. 1730 of Lecture Notes in Computer Science, pages 1-18. Springer, 1999.

Details | BibTeX | Link

Hypertree Decompositions and Tractable Queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania pages 21-32. ACM Press, 1999.

Details | BibTeX | Link (html) | DOI (10.1145/303976.303979)

Hypertree Decompositions and Tractable Queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

In SEBD pages 275-289. 1999.

Details | BibTeX

Succinctness as a Source of Complexity in Logical Formalisms

Georg Gottlob, Nicola Leone and Helmut Veith

Ann. Pure Appl. Logic, Vol. 97, No. 1-3, pages 231-260. 1999.

Details | BibTeX

Enhancing Model Checking in Verification by AI Techniques

Francesco Buccafurri et al.

Artif. Intell. Vol. 112, No. 1-2, pages 57-104. 1999.

Details | BibTeX | DOI (10.1016/S0004-3702(99)00039-9)

On the Complexity of Some Inductive Logic Programming Problems

Georg Gottlob, Nicola Leone and Francesco Scarcello

New Generation Comput. Vol. 17, No. 1, pages 53-75. 1999.

Details | BibTeX

The Complexity of Acyclic Conjunctive Queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

In FOCS pages 706-715. 1998.

Details | BibTeX | Link

Existential Second-Order Logic over Strings

Thomas Eiter, Georg Gottlob and Yuri Gurevich

In LICS pages 16-27. 1998.

Details | BibTeX

Hypertree Decompositions and Tractable Queries

Georg Gottlob, Nicola Leone and Francesco Scarcello

CoRR, Vol. cs.DB/9812022. 1998.

Details | BibTeX | Link

On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic

Thomas Eiter, Georg Gottlob

J. Symb. Log. Vol. 63, No. 1, pages 73-82. 1998.

Details | BibTeX

Capturing Relativized Complexity Classes without Order

Anuj Dawar, Georg Gottlob and Lauri Hella

Math. Log. Q. Vol. 44, pages 109-122. 1998.

Details | BibTeX

Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, KGC'97, Vienna, Austria, August 25-29, 1997, Proceedings

Georg Gottlob, Alexander Leitsch and Daniele Mundici, editors

Vol. 1289 of Lecture Notes in Computer Science. Springer. 1997.

Details | BibTeX

Generalized Quantifiers in Logic Programs

Thomas Eiter, Georg Gottlob and Helmut Veith

In Jouko A. Väänänen, editor, Generalized Quantifiers and Computation, 9th European Summer School in Logic, Language, and Information, ESSLLI'97 Workshop, Aix-en-Provence, France, August 11-22, 1997, Revised Lectures Vol. 1754 of Lecture Notes in Computer Science, pages 72-98. Springer, 1997.

Details | BibTeX | Link

The Complexity Class Theta_2^p: Recent Results and Applications in AI and Modal Logic

Thomas Eiter, Georg Gottlob

In Bogdan S. Chlebus, Ludwik Czaja, editors, Fundamentals of Computation Theory, 11th International Symposium, FCT '97, Kraków, Poland, September 1-3, 1997, Proceedings Vol. 1279 of Lecture Notes in Computer Science, pages 1-18. Springer, 1997.

Details | BibTeX

Complexity and Expressive Power of Logic Programming

Evgeny Dantsin et al.

In IEEE Conference on Computational Complexity pages 82-101. 1997.

Details | BibTeX | Link

On the Complexity of Some Inductive Logic Programming Problems

Georg Gottlob, Nicola Leone and Francesco Scarcello

In Nada Lavrac, Saso Dzeroski, editors, Inductive Logic Programming, 7th International Workshop, ILP-97, Prague, Czech Republic, September 17-20, 1997, Proceedings Vol. 1297 of Lecture Notes in Computer Science, pages 17-32. Springer, 1997.

Details | BibTeX

Modular Logic Programming and Generalized Quantifiers

Thomas Eiter, Georg Gottlob and Helmut Veith

In Jürgen Dix, Ulrich Furbach and Anil Nerode, editors, Logic Programming and Nonmonotonic Reasoning, 4th International Conference, LPNMR'97, Dagstuhl Castle, Germany, July 28-31, 1997, Proceedings Vol. 1265 of Lecture Notes in Computer Science, pages 290-309. Springer, 1997.

Details | BibTeX

The dlv System: Model Generator and Advanced Frontends (system description)

Simona Citrigno et al.

In WLP pages 0-. 1997.

Details | BibTeX

Disjunctive Datalog

Thomas Eiter, Georg Gottlob and Heikki Mannila

ACM Trans. Database Syst. Vol. 22, No. 3, pages 364-418. 1997.

Details | BibTeX | Link (html) | DOI (10.1145/261124.261126)

Semantics and Complexity of Abduction from Default Theories

Thomas Eiter, Georg Gottlob and Nicola Leone

Artif. Intell. Vol. 90, No. 1-2, pages 177-223. 1997.

Details | BibTeX | DOI (10.1016/S0004-3702(96)00040-9)

Well-Founded Semantics for Default Logic

Gerhard Brewka, Georg Gottlob

Fundam. Inform. Vol. 31, No. 3/4, pages 221-236. 1997.

Details | BibTeX

Default Logic as a Query Language

Marco Cadoli, Thomas Eiter and Georg Gottlob

IEEE Trans. Knowl. Data Eng. Vol. 9, No. 3, pages 448-463. 1997.

Details | BibTeX | DOI (http://www.informatik.uni-trier.de/~ley/db/journals/tkde/CadoliEG97.html)

On the Indiscernibility of Individuals in Logic Programming

Thomas Eiter, Georg Gottlob and Nicola Leone

J. Log. Comput. Vol. 7, No. 6, pages 805-824. 1997.

Details | BibTeX

Expressiveness of Stable Model Semantics for Disjuncitve Logic Programs with Functions

Thomas Eiter, Georg Gottlob

J. Log. Program. Vol. 33, No. 2, pages 167-178. 1997.

Details | BibTeX

Relativized Logspace and Generalized Quantifiers over Finite Ordered Structures

Georg Gottlob

J. Symb. Log. Vol. 62, No. 2, pages 545-574. 1997.

Details | BibTeX

Abduction from Logic Programs: Semantics and Complexity

Thomas Eiter, Georg Gottlob and Nicola Leone

Theor. Comput. Sci. Vol. 189, No. 1-2, pages 129-177. 1997.

Details | BibTeX | DOI (10.1016/S0304-3975(96)00179-X)

The PARK Semantics for Active Rules

Georg Gottlob, Guido Moerkotte and V. S. Subrahmanian

In Peter M. G. Apers, Mokrane Bouzeghoub and Georges Gardarin, editors, Advances in Database Technology - EDBT'96, 5th International Conference on Extending Database Technology, Avignon, France, March 25-29, 1996, Proceedings Vol. 1057 of Lecture Notes in Computer Science, pages 35-55. Springer, 1996.

Details | BibTeX | Link (html)

Collapsing Oracle-Tape Hierarchies

Georg Gottlob

In IEEE Conference on Computational Complexity pages 33-42. 1996.

Details | BibTeX | Link

Complexity and Expressive Power of KR Formalisms (Invited Talk Abstract)

Georg Gottlob

In KR pages 647-649. 1996.

Details | BibTeX

Extending Object-Oriented Systems with Roles

Georg Gottlob, Michael Schrefl and Brigitte Röck

ACM Trans. Inf. Syst. Vol. 14, No. 3, pages 268-296. 1996.

Details | BibTeX | DOI (10.1145/230538.230540)

Normal Forms for Second-Order Logic over Finite Structures, and Classification of NP Optimization Problems

Thomas Eiter, Georg Gottlob and Yuri Gurevich

Ann. Pure Appl. Logic, Vol. 78, No. 1-3, pages 111-125. 1996.

Details | BibTeX

Approximating the Stable Model Semantics is Hard

Georg Gottlob, Miroslaw Truszczynski

Fundam. Inform. Vol. 28, No. 1-2, pages 123-128. 1996.

Details | BibTeX

Reducing Disjunctive to Non-Disjunctive Semantics by Shift-Operations

Jürgen Dix, Georg Gottlob and V. Wiktor Marek

Fundam. Inform. Vol. 28, No. 1-2, pages 87-100. 1996.

Details | BibTeX

The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

Thomas Eiter, Georg Gottlob

J. Comput. Syst. Sci. Vol. 53, No. 3, pages 497-512. 1996.

Details | BibTeX

Mächtigkeit von Logikprogrammierung über Datenbanken

Thomas Eiter, Georg Gottlob

KI, Vol. 10, No. 3, pages 32-39. 1996.

Details | BibTeX

A Non-Ground Realization of the Stable and Well-Founded Semantics

Georg Gottlob et al.

Theor. Comput. Sci. Vol. 166, No. 1{\&}2, pages 221-262. 1996.

Details | BibTeX | DOI (10.1016/0304-3975(95)00207-3)

Database Theory - ICDT'95, 5th International Conference, Prague, Czech Republic, January 11-13, 1995, Proceedings

Georg Gottlob, Moshe Y. Vardi, editors

Vol. 893 of Lecture Notes in Computer Science. Springer. 1995.

Details | BibTeX

Semantics and Complexity of Abduction from Default Theories

Thomas Eiter, Georg Gottlob and Nicola Leone

In IJCAI (1) pages 870-877. 1995.

Details | BibTeX

Relativized Logspace and Generalized Quantifiers over Finite Structures

Georg Gottlob

In Proceedings, Tenth Annual IEEE Symposium on Logic in Computer Science, 26-29 June 1995, San Diego, California, USA pages 65-78. IEEE Computer Society, 1995.

Details | BibTeX

Complexity Results for Abductive Logic Programming

Thomas Eiter, Georg Gottlob and Nicola Leone

In V. Wiktor Marek, Anil Nerode, editors, Logic Programming and Nonmonotonic Reasoning, Third International Conference, LPNMR'95, Lexington, KY, USA, June 26-28, 1995, Proceedings Vol. 928 of Lecture Notes in Computer Science, pages 1-14. Springer, 1995.

Details | BibTeX

Second Order Logic and the Weak Exponential Hierarchies

Georg Gottlob, Nicola Leone and Helmut Veith

In Jir\'\i Wiedermann, Petr Hájek, editors, Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings Vol. 969 of Lecture Notes in Computer Science, pages 66-81. Springer, 1995.

Details | BibTeX

The Evolving Algebra Semantics of Class and Role Hierarchies

Georg Gottlob, Gerti Kappel and Michael Schrefl

In Leonid Libkin, Bernhard Thalheim, editors, Semantics in Databases, Selected Papers from a Workshop, Prague, Czech Republic, 1995 Vol. 1358 of Lecture Notes in Computer Science, pages 92-113. Springer, 1995.

Details | BibTeX

On the Computational Cost of Disjunctive Logic Programming: Propositional Case

Thomas Eiter, Georg Gottlob

Ann.